本文目录导读：
我来为你介绍Java实现冒泡排序的几种方式,从基础到优化。
基础冒泡排序实现
public class BubbleSort {
/**
* 基础冒泡排序
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr) {
// 边界检查
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
// 外层循环控制排序轮数
for (int i = 0; i < n - 1; i++) {
// 内层循环进行相邻元素比较
for (int j = 0; j < n - 1 - i; j++) {
// 如果前一个元素大于后一个，交换位置
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
/**
* 交换数组中的两个元素
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
优化版冒泡排序
public class OptimizedBubbleSort {
/**
* 优化冒泡排序（加入提前结束标志）
*/
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
boolean swapped; // 标记是否发生交换
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapped = true; // 发生交换
}
}
// 如果本轮没有发生交换，说明已经有序，提前结束
if (!swapped) {
break;
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
完整测试案例
import java.util.Arrays;
public class BubbleSortDemo {
public static void main(String[] args) {
// 测试数据
int[][] testArrays = {
{64, 34, 25, 12, 22, 11, 90},
{5, 1, 4, 2, 8},
{1, 2, 3, 4, 5}, // 已排序数组
{5, 4, 3, 2, 1}, // 逆序数组
{3, 3, 3, 3, 3}, // 相同元素
{1} // 单个元素
};
System.out.println("=== 冒泡排序测试 ===\n");
for (int i = 0; i < testArrays.length; i++) {
int[] arr = testArrays[i].clone(); // 复制数组
System.out.println("测试" + (i + 1) + " - 原始数组: " + Arrays.toString(testArrays[i]));
bubbleSort(arr);
System.out.println("排序后数组: " + Arrays.toString(arr));
System.out.println("排序结果: " + (isSorted(arr) ? "正确 ✓" : "错误 ✗"));
System.out.println();
}
}
/**
* 基础冒泡排序实现
*/
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false; // 优化：提前结束标志
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// 如果没有发生交换，说明已经排好序
if (!swapped) {
break;
}
}
}
/**
* 判断数组是否已排序（升序）
*/
private static boolean isSorted(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
return false;
}
}
return true;
}
}
泛型版本（支持任意可比较类型）
import java.util.Arrays;
public class GenericBubbleSort<T extends Comparable<T>> {
/**
* 泛型冒泡排序
*/
public void sort(T[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
// 使用compareTo方法比较
if (arr[j].compareTo(arr[j + 1]) > 0) {
T temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
// 测试字符串排序
GenericBubbleSort<String> stringSorter = new GenericBubbleSort<>();
String[] words = {"banana", "apple", "cherry", "date", "elderberry"};
System.out.println("字符串排序:");
System.out.println("排序前: " + Arrays.toString(words));
stringSorter.sort(words);
System.out.println("排序后: " + Arrays.toString(words));
// 测试整数排序
GenericBubbleSort<Integer> intSorter = new GenericBubbleSort<>();
Integer[] numbers = {64, 34, 25, 12, 22, 11, 90};
System.out.println("\n整数排序:");
System.out.println("排序前: " + Arrays.toString(numbers));
intSorter.sort(numbers);
System.out.println("排序后: " + Arrays.toString(numbers));
}
}
性能比较
public class BubbleSortPerformance {
public static void main(String[] args) {
// 测试不同大小的数组
int[] sizes = {100, 1000, 5000};
for (int size : sizes) {
System.out.println("数组大小: " + size);
// 生成随机数组
int[] arr1 = generateRandomArray(size);
int[] arr2 = arr1.clone();
// 测试基础冒泡
long startTime = System.currentTimeMillis();
basicBubbleSort(arr1);
long basicTime = System.currentTimeMillis() - startTime;
// 测试优化冒泡
startTime = System.currentTimeMillis();
optimizedBubbleSort(arr2);
long optimizedTime = System.currentTimeMillis() - startTime;
System.out.println("基础冒泡: " + basicTime + "ms");
System.out.println("优化冒泡: " + optimizedTime + "ms");
System.out.println();
}
}
// 基础冒泡排序
public static void basicBubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// 优化冒泡排序
public static void optimizedBubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
private static int[] generateRandomArray(int size) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = (int)(Math.random() * 10000);
}
return arr;
}
}
冒泡排序的特点
时间复杂度：
- 最好情况：O(n)（已排序）
- 最坏情况：O(n²)（逆序）
- 平均情况：O(n²)
空间复杂度：O(1)（原地排序）
稳定性：稳定（相等元素不交换位置）
适用场景：
- 数据规模较小
- 数据基本有序
- 对稳定性有要求
这就是Java实现冒泡排序的完整示例,包含了基础实现、优化版本、泛型版本和性能测试。
