排序是科学计算和数据处理必不可少的一个环节，今天起我们就来聊聊排序。
本文将介绍三个初级排序算法
- 冒泡排序
- 选择排序
- 插入排序
先来看下图这样的一组初始数据，每一个矩形的高度都与其下方的数字成比例，数值越大则矩形的高度就越高。
初始数据
假设有如下两个问题，我们该如何求解。
- 找出最(小/大)值
- 找出第k(小/大)的值
显然，在乱序的数组中这两个问题都不太容易求解，但如果数据是有序的就会容易很多。
冒泡排序
冒泡排序是最容易想到的排序算法。以对N个元素的数组进行升序排序为例，其基本思路如下：
- 从数组内的前两个元素开始，将这两个元素进行比较，如果前一个元素大于后一个元素，则交换两者的位置
- 接着取数组中的第2-3个元素进行比较，若第2个元素大于第3个元素，则交换两者的位置
- 循环往复，直到数组中的最后两个元素，此时，若第N-1个元素大于第N个元素，则交换它们的位置。经过一轮的比较与交换，我们已经得到了数组中最大的元素，并将其安置在了数组的第N位。
- 经过前三个步骤，我们将数组中最大的元素放到了第N位，下边只用排序数组中的前N-1个元素即可。此时我们将N的值减1，并判断新N的值，若新N>0，则循环1-3步骤；若新N=0，则代表我们已经完成了排序。
冒泡排序的过程(剪辑版)如下图所示，你也可以点击这里查看完整的冒泡排序过程。
冒泡排序剪辑版
我们知道，水杯中出现气泡时，越大的气泡浮力越大，上升速度也就越快，最先到达水面，冒牌排序中每轮遴选较大元素放置末尾的行为与水中气泡上升的现象十分相似，因此得名冒泡排序。
冒泡排序代码
public static void bubbleSort(Integer arr[]) {
int compareCount = 0;//比较次数
int swapCount = 0;//交换次数
long before = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) { //外层循环，与数组元素个数相关
for (int j = 1; j < arr.length - i; j++) { //内层循环，只需在前 n-1 个元素内进行相邻比较
compareCount++;
if (arr[j - 1] > arr[j]) {
swapCount++;
swap(arr, j - 1, j);
}
}
}
long after = System.currentTimeMillis();
System.out.println("冒泡排序耗时："+(after-before)+"ms,"+"比较次数："+compareCount+",交换次数："+swapCount);
}
使用上述代码对以下两组数据排序时，其比较次数一致，仅交换次数不同。但显而易见的是，第二组本身就是有序的，也就是说上边的代码中，存在冗余比较。
3 5 1 6 10 9 11
1 3 5 7 9 10 11
原有数组 3 5 1 6 10 9 11
冒泡排序耗时：0ms 比较次数：21,交换次数：3
排序后 1 3 5 6 9 10 11
---
原有数组 1 3 5 6 9 10 11
冒泡排序耗时：0ms 比较次数：21,交换次数：0
排序后 1 3 5 6 9 10 11
针对这样的问题，我们可以采用如下思路对冒泡排序的代码进行优化。
- 当某轮内循环没有发生元素交换时，表明数组已然有序，无需再进行后续的比较，此时可直接中止循环
冒泡排序优化代码
public static void bubbleSortOpt(Integer arr[]) {
int compareCount = 0;//比较次数
int swapCount = 0;//交换次数
long before = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) { //外层循环，与数组元素个数相关
boolean isSwap = false; //交换标记，每轮外循环开始时，将其置位false
for (int j = 1; j < arr.length - i; j++) { //内层循环，只需在前 n-1 个元素内进行相邻比较
compareCount++;
if (arr[j - 1] > arr[j]) {
isSwap = true;//若内循环内发生交换，则将交换标志置位true
swapCount++;
swap(arr, j - 1, j);
}
}
if (!isSwap) {//判断循环标记，若未发生交换，则跳出循环
break;
}
}
long after = System.currentTimeMillis();
System.out.println("冒泡排序耗时："+(after-before)+"ms,"+"比较次数："+compareCount+",交换次数："+swapCount);
}
原有数组 3 5 1 6 10 9 11
冒泡排序耗时：0ms 比较次数：15,交换次数：3
排序后 1 3 5 6 9 10 11
---
原有数组 1 3 5 6 9 10 11
冒泡排序耗时：0ms 比较次数：5,交换次数：0
排序后
选择排序
选择排序的思路同样很简单，以对含有N个元素的数组进行升序排序为例，其步骤如下所示：
- 假设首元素是最小的，并记录其索引值为minIndex，遍历数组，分别与其比较，若数组中第i个元素的数值小于第minIndex个元素的数组，则将i赋值与minIndex。
- 遍历结束后，我们得到了数值最小的元素的索引值，将其与首元素进行交换，交换后的首元素即为数组中数值最小的元素。
- 经过前边两个步骤，此时数组中可分为首元素和与第2个元素开始到末尾的N-1个元素。判断N-1，若N-1>0,则将第二个元素视作首元素，重复步骤1-2；若N-1=0，则表明数组已然有序，中止循环。
选择排序的过程(剪辑版)如下图所示，你也可以点击这里查看完整的选择排序过程。
选择排序剪辑版
根据这个思路，不难写出其代码
public static void selectSort(Integer arr[]) {
int compareCount = 0;
int swapCount = 0;
long before = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i+1; j < arr.length - i; j++) {
compareCount++;
if (arr[j]<arr[minIndex]){
minIndex = j;
}
}
if (minIndex!=i){
swapCount++;
swap(arr,i,minIndex);
}
}
long after = System.currentTimeMillis();
System.out.println("选择排序耗时：" + (after - before) + "ms," + "比较次数：" + compareCount + ",交换次数：" + swapCount);
}
插入排序
插入排序是我们需要了解是最后一个简单排序算法，其思路与我们打扑克牌时的起牌手法相似。
- 假设我们用左手持牌，右手起牌，每次起牌完成后，左手中的手牌均为有序的。
- 开始起牌时，左手手牌为空，此时从牌堆顶取一张牌，直接放入左手
- 在起后边的牌时，我们拿右手中刚起到的那张新牌，与左手中的所有手牌进行比较，并放入到合适的位置。
- 按从大到小的顺序分别拿左手中的手牌与新牌进行比较
- 在从大到小的比较过程中，若左手当前手牌比新牌大，则取交换着两张牌的位置，并以左手当前手牌作为新牌，与剩余的左手手牌进行比较
- 若左手的当前手牌小于等于新牌，则将新牌插入到当前手牌之后，并将此后的手牌依次向后挪动
使用插入排序来排序手中扑克牌
需要注意的是，在插入排序时，我们将数组分为了两部分，一部分是"左手"中的有序子数组，另一部分是"牌堆"中无序的子数组。初始时，我们将数组中的第一个元素视作已排序子数组，并将第二个元素至最后一个元素视作无序子数组。我们每次从无序子数组中取出首元素p，从后往前分别与有序子数组中的元素q进行比较，若p小于q的数值，则将p与q交换，并继续用p与子数组中剩下的元素进行比较和交换，直到p不小q时，完成此轮插入，此时有序子数组的长度+1，无序子数组的长度-1。
插入排序的过程(剪辑版)如下图所示，你也可以点击这里查看完整的插入排序过程。
插入排序剪辑版
插入排序代码
public static void insertSort(Integer arr[]) {
int compareCount = 0;
int swapCount = 0;
long before = System.currentTimeMillis();
//外层循环，i表示有序子数组与无序子数组间的界限，i之前的元素为有序的，i及i之后的元素为无序的
for (int i = 1; i < arr.length; i++) {
//内层循环，将i到0之间的元素两两比较，若i<i-1，则交换两者的位置
for (int j = i; j > 0; j--) {
compareCount++;
if (arr[j] < arr[j - 1]) {
swapCount++;
swap(arr, j, j - 1);//两两交换
}
}
}
long after = System.currentTimeMillis();
System.out.println("选择排序耗时：" + (after - before) + "ms," + "比较次数：" + compareCount + ",交换次数：" + swapCount);
}
我们知道频繁的两两交换也是有性能损耗的，对于插入排序，我们通过如下的思路进一步优化：
- 在新牌插入过程中，先在左手手牌的后方将新牌的空间给预留出来，从大到小，依次比较当前手牌与新牌。
- 若当前手牌大于新牌，则将当前手牌向后挪动一下（注意，此时并不拿新牌与当前手牌交换），将左手手牌后方的空间挤压到当前手牌的前方
- 若当前手牌小于新牌，则将新牌放到这里
有了这个思路，我们便可以将此前频繁的两两交换，换为单个元素后移，从而减少了一定的性能开销。
优化插入排序
public static void insertSortOpt(Integer arr[]) {
long before = System.currentTimeMillis();
for (int i = 1; i < arr.length; i++) {
//使用临时变量保存新牌
int temp =arr[i];
int j = i;
//从大到小，依次取左手中的牌与temp进行比较，若左手当前手牌大于temp，则将当前手牌后移一位
while(j>0 && temp<arr[j-1]){
arr[j] = arr[j -1];
j--;//继续下一张较大的牌
}
arr[j] = temp;//最终将temp插入左手手牌中合适的位置
}
long after = System.currentTimeMillis();
System.out.println("插入排序耗时：" + (after - before) + "ms");
}
在规模较大的问题中，这种方式带来的好处非常明显。
10W条数据
插入排序耗时：12296ms
优化插入排序耗时：2742ms
测试
| 排序算法 | 问题规模（待排序元素个数） | 解题时间1 | 解题时间2 | 解题时间3 | 平均解题时间 |
|---|---|---|---|---|---|
| 优化冒泡排序 | 1W | 293ms | 293ms | 278ms | 288ms |
| 选择排序 | 1W | 28ms | 43ms | 52ms | 41ms |
| 优化插入排序 | 1W | 22ms | 36ms | 28ms | 28.7ms |
| 优化冒泡排序 | 5W | 7806ms | 7428ms | 8011ms | 7748.3ms |
| 选择排序 | 5W | 603ms | 617ms | 606ms | 608.7ms |
| 优化插入排序 | 5W | 598ms | 606ms | 600ms | 601.3ms |
| 优化冒泡排序 | 10W | 28801ms | 30978ms | 29308ms | 29725.7ms |
| 选择排序 | 10W | 2609ms | 2649ms | 2658ms | 2638.7ms |
| 优化插入排序 | 10W | 2693ms | 2712ms | 2685ms | 2696.7ms |
经过测试，可以看到冒泡排序的耗时最多。插入排序在规模较小的数组中明显快于选择排序，在规模较大的数组中与选择排序相当，从此也证明了我们此前算法分析环节中得到的结论。
小结
本文介绍了三个基础的排序算法，在这里先对它们做一个总结，希望能让大家对排序及算法效率有一个直观的感受。
| 排序算法 | 核心思路 | 最好情况(有序) | 最坏情况(逆序) | 时间复杂度O | 特点 |
|---|---|---|---|---|---|
| 优化冒泡排序 | 相邻元素两两比较并交换 | 比较n-1次，交换0次 | 比较n(n-1)/2次，交换n(n-1)/2次 | O(n²) | 简单易懂，效率较低 |
| 直接选择排序 | 已知位次找第k(大/小)元素 | 比较n(n-1)/2次，交换0次 | 比较n(n-1)/2次，交换n次 | O(n²) | 运行时间与原始数据无关；交换次数最少 |
| 优化插入排序 | 扑克牌起牌法 | 比较n-1次，交换0次 | 比较n(n-1)/2次，后移(n-1)(n-2)/2次 | O(n²) | 运行时间与原始数据强相关；对部分有序数据或小规模数据极为友好 |
选择排序和插入排序的异同点：
- 插入排序与选择排序一样，当前索引左边的所有元素都是有序的。但在选择排序中，当前索引左边的元素位置是固定的(与最终位置一致)；而插入排序当前索引左边的元素位置未必固定，为了给后边更小的元素腾出空间，它们可能会被移动，当索引到达数组的右端时，排序完成。
- 选择排序的运行时间与原始数据无关（比较次数恒定）；插入排序的运行时间与原始数据强相关，当对一个有序或接近有序的数组排序时，会比随机顺序或逆序的数组快很多。
参考书目
《算法导论》 - CLRS
《算法》第四版 - Sedgewick
《数据结构与算法分析》 - Weiss
网友评论