冒泡排序以及改进方案

冒泡排序以及改进方案

介绍：

冒泡排序属于一种典型的交换排序（两两比较）。冒泡排序就像是把一杯子里的气泡一个个往上冒一样。它不断比较相邻的元素，如果顺序不对就像水泡一样交换它们的位置，直到整个序列像水泡一样，按照大小顺序排列好。当它发现一轮遍历中没有发生交换，就像是水泡都冒完了一样，就知道排序完成了。

图示：

冒泡排序性能

算法	最好时间	最坏时间	平均时间	额外空间	稳定性
冒泡	O(n）	O(n2)	O(n2)	1	稳定

普通版本的冒泡排序

通过简单的两层遍历，就可以实现了：

for (int i = 0; i < array.length; i++) {for (int j = 0; j < array.length -i -1; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}
}

第一次改进：

当一个数组大小不是很混乱的时候，我们没必要每次都去交换：

例如：2,1,3,4,6 这样的数组，我们在第一次交换的时候就已经排好序了（1,2,3,4,6）,我们无需再基于1,2,3,4,6排序，改进如下：

for (int i = 0; i < array.length; i++) {int flag = false; // 是否发生交换for (int j = 0; j < array.length -i -1; j++) {if (array[j] > array[j + 1]) { // 顺序不对，需要交换// 以下三行交换操作int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true; // 发生了交换}if(!flag) { // 如果没有发生交换，跳出循环,无需比对后面的break;}}}

第二次改进：

最后一次交换位置将整个数组分为了两部分：之前是未排序部分，之后是已排序部分。如此一来，下一次冒泡排序就只需在未排序部分进行冒泡排序即可。 根据这个思路再进行代码改进：

public class BubbleSort {// 冒泡排序算法实现public static void bubbleSort(int[] array) {if (array == null || array.length < 0) {return;}int sortIndex = array.length - 1; // 初始排序边界为数组末尾int lastChange = 0; // 记录最后一次交换的位置for (int i = 0; i < array.length; i++) {boolean flag = false; // 标记是否发生交换for (int j = 0; j < sortIndex; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;lastChange = j; // 更新最后一次交换的位置}}sortIndex = lastChange; // 更新排序边界if (!flag) { // 若未发生交换，说明数组已排序，结束排序break;}}}public static void main(String[] args) {int[] arr = {64, 34, 25, 12, 22, 11, 90};bubbleSort(arr);System.out.println("排序后的数组:");for (int i : arr) {System.out.print(i + " ");}}
}