当前位置：首页 > news >正文

数据结构学习笔记：冒泡排序(Java)

news 2026/8/28 12:20:36

1.原始版本

算法思想

对于待排序列，从左到右依次将相邻元素两两比较，将更大的元素交换到右边。每遍历一次后，待排序列中的最大元素将被移动到最右侧，进入已排序列。同时还有若干个较大的元素被向右移动了数次。不断重复，待排序列逐渐缩小直至排列完毕。

当然，也可以在遍历中将更小元素向左冒泡。从算法上二者效率一致，但由于CPU特性，正序读取数组的效率更高。

以下是一次循环的图示：

代码

public static void bubbleSort(int[] array) { // maxIndex为待排序列的右边界 for (int maxIndex = array.length - 1; maxIndex > 0; maxIndex--) { for (int i = 0; i < maxIndex; i++) { if (array[i] > array[i + 1]) { swap(array, i , i + 1); } } } } private static void swap(int[] array, int a, int b) { int temp = array[a]; array[a] = array[b]; array[b] = temp; }

2. 优化1

优化思想

对于长度为n的序列，原方法必然要进行n-1次遍历。若在某次遍历的过程中，没有出现交换操作，说明整个序列已经排好了，不必进行后续的循环了。

可以设置flag作为标记提高效率。

代码

public static void bubbleSort2(int[] array) { boolean flag = true; // flag为true表示还未排好 for (int maxIndex = array.length - 1; maxIndex > 0 && flag; maxIndex--) { flag = false; for (int i = 0; i < maxIndex; i++) { if (array[i] > array[i + 1]) { flag = true; // 发生交换，说明可能还未排好，设置flag为true swap(array, i , i + 1); } } } }

3. 优化2

优化思想

若当前的待排序列右侧若干个元素已经是排好的，那么在一次遍历中这些元素不会被交换，下次遍历可以跳过这些元素，遍历更小的区间。下次遍历的右边界为本次遍历最后一次发生交换的位置。

代码

public static void bubbleSort3(int[] array) { int newIndex; // 用于记录下次遍历的右边界 int maxIndex = array.length - 1; // 待排序列的右边界 do { newIndex = 0; for (int i = 0; i < maxIndex; i++) { if (array[i] > array[i + 1]) { newIndex = i; // 下次遍历的区间可能为[0, i] swap(array, i, i + 1); } } maxIndex = newIndex + 1; // 由于循环条件为i<maxIndex，所以要加1 } while (newIndex > 0); // newIndex==0说明没有交换，排序完成 }

PS：遍历后newIndex为0说明没有交换，结束循环，即优化1的思想