首页 > 代码库 > 排序算法1——冒泡排序
排序算法1——冒泡排序
在介绍冒泡排序之前，优先介绍一种算法设计的策略——蛮力法。这是一种简单直接的解决问题的方法，常常直接基于问题的描述和所涉及的定义。由于蛮力法是基于问题的定义来思考的，那么可以说它是一种几乎什么问题都能解决的一般性的方法。当然，缺点也是显而易见的，那就是“笨”，即解决方法的过程既不巧妙，也不高效。而冒泡排序就是蛮力法在排序问题上的一个典型的应用场景。
所谓冒泡排序，即是对于一个给定长度为n的无序数组，由初始位置开始，比较数组相邻两个元素，如果是逆序排列的，就交换它们的位置，重复多次之后，最大数就“沉”到了最下面的位置。第二次再从初始位置开始，将第二大的元素沉到倒数第二个位置。这样一直做n-1次，整个数组就是有序的了。
当然，也可以从数组最后一位开始向前遍历，这样一来，每一次的操作就是将最小的数字“浮”到最上方。这也是“冒泡排序”名字的由来。这两种做法在效率上并无高下之分，全凭个人喜好。我自己偏爱“下沉”的做法。
值得一提的是，在第一轮操作结束之后，第二轮的操作无需比较最后一位，因为最后一位已经是最大的元素了。所以对于一个长度为n的数组，整个算法消耗的时间为： (n-1)+(n-2)+…+1=n(n-1)/2，即时间复杂度为O(n^2)。同时，显而易见，整个算法只消耗一份数组的空间，所以空间复杂度为O(1)。
下面用一个具体的场景来体会一下冒泡排序的过程。
场景：
现有一个无序数组，共7个数：89 45 54 29 90 34 68。使用冒泡排序对这个序列进行升序排序。
基础冒泡排序实现过程：
第一步：
89 45 54 29 90 34 68；
45 89 54 29 90 34 68；
45 54 89 29 90 34 68；
45 54 29 89 90 34 68；
45 54 29 89 90 34 68；
45 54 29 89 34 90 68；
45 54 29 89 34 68 90；
第二步：
45 54 29 89 34 68 90；
45 54 29 89 34 68 90；
45 29 54 89 34 68 90；
45 29 54 89 34 68 90；
45 29 54 34 89 68 90；
45 29 54 34 68 89 90；
第三步：
45 29 54 34 68 89 90；
29 45 54 34 68 89 90；
29 45 54 34 68 89 90；
29 45 54 34 68 89 90；
29 45 54 34 68 89 90；
第四步：
29 45 54 34 68 89 90；
29 45 54 34 68 89 90；
29 45 54 34 68 89 90；
29 45 34 54 68 89 90；
第五步：
29 45 34 54 68 89 90；
29 45 34 54 68 89 90；
29 34 45 54 68 89 90；
第六步：
29 34 45 54 68 89 90；
29 34 45 54 68 89 90；
根据之前的描述，附上基础冒泡排序的代码：
1 // 基础冒泡排序 2 public static void basal(int[] array) { 3 // 外循环，最后一次只剩一个数字未排序，自然有序，无需再排序 4 for (int i = 0; i < array.length - 1; i++) { 5 // 内循环，不计已经沉底的最大数 6 // 即[array.length-i-1,array.length-1]区间已经有序 7 for (int j = 0; j < array.length - 1 - i; j++) { 8 if (array[j] > array[j + 1]) { 9 swap(j, j + 1, array);10 }11 }12 }13 }14 15 // 交换数组中2个值的位置16 private static void swap(int index1, int index2, int[] array) {17 int temp = array[index1];18 array[index1] = array[index2];19 array[index2] = temp;20 }
蛮力法的应用有一个显著的特点，就是在经过适当的努力之后，可以对算法进行一定的改良，从而它的性能，但并不会减弱算法本身的时间复杂度。冒泡排序作为蛮力法的典型应用，自然也有这种特性。
我们首先观察上述示例的实现过程。不难发现，其实在“第五步”结束之后，整个数组已经有序，实际上并不需要执行“第六步”。这种情况不难想象，假定待排序的数组本身已经有序，那么我们难道还需要傻乎乎的执行n(n-1)/2次操作才能将整个数组排序吗？可以设定一个标志位，检查一次比较之后，是否有数据进行了交换，若是没有，那么整个数组就已经有序了，可以直接退出。极端情况下，如刚才提到的，对有序数组进行排序，只需要执行n-1次操作，就可以完成排序。
附上优化冒泡排序1的代码：
1 // 优化冒泡排序1 2 public static void optimized_1(int[] array) { 3 // 内循环数据交换标志 4 boolean hasSwaped = false; 5 for (int i = 0; i < array.length - 1; i++) { 6 for (int j = 0; j < array.length - 1 - i; j++) { 7 if (array[j] > array[j + 1]) { 8 swap(j, j + 1, array); 9 hasSwaped = true;10 }11 }12 // 如果某次内循环，没有发生任何一次数据交换，13 // 表示整个数组已经完全有序，没有必要继续做外循环，直接退出14 if (!hasSwaped) {15 break;16 }17 }18 }
其实还有更进一步的优化方法。再仔细观察上述的实现过程，可以发现，在“第二步”结束的时候，我们本来期待的，是89、90有序，但实际上倒数第三位68，其实是第三大的，那么是不是有方法可以确定68是第三大的呢？若是可以，我们在执行“第三步”的时候，就可以将68、89、90作为已经有序，从而减少一整轮的操作。
方法是存在的。我们可以想象，冒泡排序中，整个的大数“下沉”的过程，实际上是层层下沉的，也就是说，只要最大数不在最后一位，那么总会存在最后一次会出现数据交换。那么如果交换出现在倒数第二次，而不是最后一次会是什么情况？最大数一定会出现在数组的最后一位，而次大数，作为排除掉最大数的最大值，一定会经过层层下沉，来到倒数第二的位置。以此类推。换一句话说，我们记原本数组一轮的遍历是在[0,n]区间，那么下一轮的遍历是在[0,n-1]区间。现在记数组本轮遍历的最后一次交换发生在lastSwapPos位置，那么下一轮的遍历就是在[0, lastSwapPos]区间。
结合第1种优化方法，附上优化冒泡排序2的代码：
1 // 优化冒泡排序2 2 public static void optimized_2(int[] array) { 3 int lastSwapPos = array.length - 1; 4 int lastSwapPosTemp = array.length - 1; 5 for (int i = 0; i < array.length - 1; i++) { 6 lastSwapPos = lastSwapPosTemp; 7 // 因为大数一定是不断下沉的，所以只要最大数不在遍历的终点上，最后一次一定会执行交换、 8 // 换言之，若是最后一次交换未执行，而是在倒数第二次处执行了交换，一定可以保证倒数第二个数是次大数 9 // 因此可以将倒数第三个数作为下一次交换的终点10 // 依次类推，可以保证[lastSwapPos,array.length-1-i]是有序的，且其中任意一个数都比前面的数字大11 // 所以内循环的退出条件，可以由j<array.length-1-i转变为j<lastSwapPos12 for (int j = 0; j < lastSwapPos; j++) {13 if (array[j] > array[j + 1]) {14 swap(j, j + 1, array);15 lastSwapPosTemp = j;16 }17 }18 // 一次都未交换的情况19 if (lastSwapPos == lastSwapPosTemp) {20 break;21 }22 }23 }
如果存在描述或者代码错误的情况，欢迎指正，谢谢！
排序算法1——冒泡排序