1、排序一 冒泡排序
要点
冒泡排序是一种交换排序。
什么是交换排序呢？
交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。
算法思想
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端，故名。
假设有一个大小为 N 的无序序列。冒泡排序就是要每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。
图-冒泡排序示例图
以上图为例，演示一下冒泡排序的实际流程：
假设有一个无序序列 { 4. 3. 1. 2, 5 }
第一趟排序：通过两两比较，找到第一小的数值 1 ，将其放在序列的第一位。
第二趟排序：通过两两比较，找到第二小的数值 2 ，将其放在序列的第二位。
第三趟排序：通过两两比较，找到第三小的数值 3 ，将其放在序列的第三位。
至此，所有元素已经有序，排序结束。
要将以上流程转化为代码，我们需要像机器一样去思考，不然编译器可看不懂。
假设要对一个大小为 N 的无序序列进行升序排序（即从小到大）。
(1) 每趟排序过程中需要通过比较找到第 i 个小的元素。
所以，我们需要一个外部循环，从数组首端(下标 0) 开始，一直扫描到倒数第二个元素（即下标 N - 2) ，剩下最后一个元素，必然为最大。
(2) 假设是第 i 趟排序，可知，前 i-1 个元素已经有序。现在要找第 i 个元素，只需从数组末端开始，扫描到第 i 个元素，将它们两两比较即可。
所以，需要一个内部循环，从数组末端开始（下标 N - 1），扫描到 (下标 i + 1)。
核心代码
int temp = 0; // 用来交换的临时数
// 要遍历的次数
for ( int i = 0; i < list.length - 1; i++) {
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
for ( int j = list.length - 1; j > i; j--) {
// 比较相邻的元素，如果前面的数大于后面的数，则交换
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
}
}
System.out.format("第 %d 趟：\t", i);
printAll(list);
}
}
算法分析
冒泡排序算法的性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 交换排序 | 冒泡排序 | O(N2) | O(N2) | O(N) | O(1) | 稳定 | 简单 |
时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin = N - 1, Mmin = 0。所以，冒泡排序最好时间复杂度为O(N)。
若初始文件是反序的，需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
Cmax = N(N-1)/2 = O(N2)
Mmax = 3N(N-1)/2 = O(N2)
冒泡排序的最坏时间复杂度为O(N2)。
因此，冒泡排序的平均时间复杂度为O(N2)。
总结起来，其实就是一句话：当数据越接近正序时，冒泡排序性能越好。
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。
所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
优化
对冒泡排序常见的改进方法是加入标志性变量exchange，用于标志某一趟排序过程中是否有数据交换。
如果进行某一趟排序时并没有进行数据交换，则说明所有数据已经有序，可立即结束排序，避免不必要的比较过程。
核心代码
public void bubbleSort_2( int[] list) {
int temp = 0; // 用来交换的临时数
boolean bChange = false; // 交换标志
// 要遍历的次数
for ( int i = 0; i < list.length - 1; i++) {
bChange = false;
// 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
for ( int j = list.length - 1; j > i; j--) {
// 比较相邻的元素，如果前面的数大于后面的数，则交换
if (list[j - 1] > list[j]) {
temp = list[j - 1];
list[j - 1] = list[j];
list[j] = temp;
bChange = true;
}
}
// 如果标志为false，说明本轮遍历没有交换，已经是有序数列，可以结束排序
if ( false == bChange)
break;
System.out.format("第 %d 趟：\t", i);
printAll(list);
}
}
完整参考代码
JAVA版本
代码实现
View Code 运行结果
第 0 趟： 0 2 9 9 7 1 9 2 6 8
第 1 趟： 0 1 2 9 9 7 2 9 6 8
第 2 趟： 0 1 2 2 9 9 7 6 9 8
第 3 趟： 0 1 2 2 6 9 9 7 8 9
第 4 趟： 0 1 2 2 6 7 9 9 8 9
第 5 趟： 0 1 2 2 6 7 8 9 9 9
排序后: 0 1 2 2 6 7 8 9 9 9
参考资料
《数据结构习题与解析》（B级第3版）
2、排序二 快速排序
要点
快速排序是一种交换排序。
快速排序由C. A. R. Hoare在1962年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。
然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
详细的图解往往比大堆的文字更有说明力，所以直接上图：
上图中，演示了快速排序的处理过程：
初始状态为一组无序的数组：2、4、5、1、3。
经过以上操作步骤后，完成了第一次的排序，得到新的数组：1、2、5、4、3。
新的数组中，以2为分割点，左边都是比2小的数，右边都是比2大的数。
因为2已经在数组中找到了合适的位置，所以不用再动。
2左边的数组只有一个元素1，所以显然不用再排序，位置也被确定。（注：这种情况时，left指针和right指针显然是重合的。因此在代码中，我们可以通过设置判定条件left必须小于right，如果不满足，则不用排序了）。
而对于2右边的数组5、4、3，设置left指向5，right指向3，开始继续重复图中的一、二、三、四步骤，对新的数组进行排序。
核心代码
// 以最左边的数(left)为基准
int base = list[left];
while (left < right) {
// 从序列右端开始，向左遍历，直到找到小于base的数
while (left < right && list[right] >= base)
right--;
// 找到了比base小的元素，将这个元素放到最左边的位置
list[left] = list[right];
// 从序列左端开始，向右遍历，直到找到大于base的数
while (left < right && list[left] <= base)
left++;
// 找到了比base大的元素，将这个元素放到最右边的位置
list[right] = list[left];
}
// 最后将base放到left位置。此时，left位置的左侧数值应该都比left小；
// 而left位置的右侧数值应该都比left大。
list[left] = base;
return left;
}
private void quickSort( int[] list, int left, int right) {
// 左下标一定小于右下标，否则就越界了
if (left < right) {
// 对数组进行分割，取出下次分割的基准标号
int base = division(list, left, right);
System.out.format("base = %d:\t", list[base]);
printPart(list, left, right);
// 对“基准标号“左侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, left, base - 1);
// 对“基准标号“右侧的一组数值进行递归的切割，以至于将这些数值完整的排序
quickSort(list, base + 1, right);
}
}
算法分析
快速排序算法的性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 交换排序 | 快速排序 | O(Nlog2N) | O(N2) | O(Nlog2N) | O(Nlog2N) | 不稳定 | 较复杂 |
时间复杂度
当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。
而当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。
所以，数据越随机分布时，快速排序性能越好；数据越接近有序，快速排序性能越差。
空间复杂度
快速排序在每次分割的过程中，需要 1 个空间存储基准值。而快速排序的大概需要 Nlog2N次 的分割处理，所以占用空间也是 Nlog2N 个。
算法稳定性
在快速排序中，相等元素可能会因为分区而交换顺序，所以它是不稳定的算法。
完整参考代码
JAVA版本
代码实现
View Code
运行结果
base = 1: 0 1 4 5 2 6 9 7 8 3
base = 4: 3 2 4 6 9 7 8 5
base = 3: 2 3
base = 6: 5 6 7 8 9
base = 7: 7 8 9
base = 8: 8 9
排序后: 0 1 2 3 4 5 6 7 8 9
参考资料
《数据结构习题与解析》（B级第3版）
3、排序三 直接插入排序
要点
直接插入排序是一种最简单的插入排序。
插入排序：每一趟将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，知道全部插入完成。
在讲解直接插入排序之前，先让我们脑补一下我们打牌的过程。
先拿一张5在手里，
再摸到一张4，比5小，插到5前面，
摸到一张6，嗯，比5大，插到5后面，
摸到一张8，比6大，插到6后面，
。。。
最后一看，我靠，凑到全是同花顺，这下牛逼大了。
以上的过程，其实就是典型的直接插入排序，每次将一个新数据插入到有序队列中的合适位置里。
很简单吧，接下来，我们要将这个算法转化为编程语言。
假设有一组无序序列 R0, R1, ... , RN-1。
(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
(2) 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。
(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。
所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。
核心代码
// 打印第一个元素
System.out.format("i = %d:\t", 0);
printPart(list, 0, 0);
// 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
for ( int i = 1; i < list.length; i++) {
int j = 0;
int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置
// 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
for (j = i - 1; j >= 0 && temp < list[j]; j--) {
list[j + 1] = list[j];
}
list[j + 1] = temp;
System.out.format("i = %d:\t", i);
printPart(list, 0, i);
}
}
算法分析
直接插入排序的算法性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 插入排序 | 直接插入排序 | O(N2) | O(N2) | O(N) | O(1) | 稳定 | 简单 |
时间复杂度
当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。
所以，数据越接近正序，直接插入排序的算法性能越好。
空间复杂度
由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。
算法稳定性
直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。
完整参考代码
JAVA版本
代码实现
View Code
运行结果
i = 0: 6
i = 1: 3 6
i = 2: 3 3 6
i = 3: 3 3 5 6
i = 4: 3 3 5 6 6
i = 5: 3 3 3 5 6 6
i = 6: 1 3 3 3 5 6 6
i = 7: 0 1 3 3 3 5 6 6
i = 8: 0 1 3 3 3 5 6 6 6
i = 9: 0 1 3 3 3 4 5 6 6 6
排序后: 0 1 3 3 3 4 5 6 6 6
参考资料
《数据结构习题与解析》（B级第3版）
http://www.cnblogs.com/huangxincheng/archive/2011/11/20/2255695.html
4、排序四 希尔排序
要点
希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
该方法因DL．Shell于1959年提出而得名。
希尔排序的基本思想是：
把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
我们来通过演示图，更深入的理解一下这个过程。
在上面这幅图中：
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
核心代码
int gap = list.length / 2;
while (1 <= gap) {
// 把距离为 gap 的元素编为一个组，扫描所有组
for ( int i = gap; i < list.length; i++) {
int j = 0;
int temp = list[i];
// 对距离为 gap 的元素组进行排序
for (j = i - gap; j >= 0 && temp < list[j]; j = j - gap) {
list[j + gap] = list[j];
}
list[j + gap] = temp;
}
System.out.format("gap = %d:\t", gap);
printAll(list);
gap = gap / 2; // 减小增量
}
}
算法分析
希尔排序的算法性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 插入排序 | 希尔排序 | O(Nlog2N) | O(N1.5) |
| O(1) | 不稳定 | 较复杂 |
时间复杂度
步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。
算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。
Donald Shell 最初建议步长选择为N/2并且对步长取半直到步长达到1。虽然这样取可以比O(N2)类的算法（插入排序）更好，但这样仍然有减少平均时间和最差时间的余地。可能希尔排序最重要的地方在于当用较小步长排序后，以前用的较大步长仍然是有序的。比如，如果一个数列以步长5进行了排序然后再以步长3进行排序，那么该数列不仅是以步长3有序，而且是以步长5有序。如果不是这样，那么算法在迭代过程中会打乱以前的顺序，那就
不会以如此短的时间完成排序了。
| 步长序列 | 最坏情况下复杂度 |
| | |
| | |
| | |
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...)，该序列的项来自
这两个算式。
这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。
算法稳定性
由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。
直接插入排序和希尔排序的比较
直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
完整参考代码
JAVA版本
代码实现
范例代码中的初始序列和本文图示中的序列完全一致。
View Code
运行结果
gap = 5: 4 1 2 3 5 9 8 6 5 7
gap = 2: 2 1 4 3 5 6 5 7 8 9
gap = 1: 1 2 3 4 5 5 6 7 8 9
排序后: 1 2 3 4 5 5 6 7 8 9
参考资料
《数据结构习题与解析》（B级第3版）
维基百科-希尔排序：http://zh.wikipedia.org/zh-cn/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
5、排序五 简单选择排序
要点
简单选择排序是一种选择排序。
选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
简单排序处理流程
(1) 从待排序序列中，找到关键字最小的元素；
(2) 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
(3) 从余下的 N - 1 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。
如图所示，每趟排序中，将当前第 i 小的元素放在位置 i 上。
核心代码
// 需要遍历获得最小值的次数
// 要注意一点，当要排序 N 个数，已经经过 N-1 次遍历后，已经是有序数列
for ( int i = 0; i < list.length - 1; i++) {
int temp = 0;
int index = i; // 用来保存最小值得索引
// 寻找第i个小的数值
for ( int j = i + 1; j < list.length; j++) {
if (list[index] > list[j]) {
index = j;
}
}
// 将找到的第i个小的数值放在第i个位置上
temp = list[index];
list[index] = list[i];
list[i] = temp;
System.out.format("第 %d 趟:\t", i + 1);
printAll(list);
}
}
算法分析
简单选择排序算法的性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 选择排序 | 简单选择排序 | O(N2) | O(N2) | O(N2) | O(1) | 不稳定 | 简单 |
时间复杂度
简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N - 1) / 2。
而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为 0.
当序列反序时，移动次数最多，为3N (N - 1) / 2。
所以，综合以上，简单排序的时间复杂度为 O(N2)。
空间复杂度
简单选择排序需要占用 1 个临时空间，在交换数值时使用。
完整参考代码
JAVA版本
代码实现
View Code
运行结果
第 1 趟: 0 5 2 8 1 2 3 8 4 1
第 2 趟: 0 1 2 8 5 2 3 8 4 1
第 3 趟: 0 1 1 8 5 2 3 8 4 2
第 4 趟: 0 1 1 2 5 8 3 8 4 2
第 5 趟: 0 1 1 2 2 8 3 8 4 5
第 6 趟: 0 1 1 2 2 3 8 8 4 5
第 7 趟: 0 1 1 2 2 3 4 8 8 5
第 8 趟: 0 1 1 2 2 3 4 5 8 8
第 9 趟: 0 1 1 2 2 3 4 5 8 8
排序后: 0 1 1 2 2 3 4 5 8 8
参考资料
《数据结构习题与解析》（B级第3版）
6、排序六 堆排序
堆的概念
在介绍堆排序之前，首先需要说明一下，堆是个什么玩意儿。
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。
堆中有两个父结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
要点
首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。
以上思想可归纳为两个操作：
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
先通过详细的实例图来看一下，如何构建初始堆。
设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
构造了初始堆后，我们来看一下完整的堆排序处理：
还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。
相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。
核心代码
int temp = array[parent]; // temp保存当前父节点
int child = 2 * parent + 1; // 先获得左孩子
while (child < length) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
// 如果父结点的值已经大于孩子结点的值，则直接结束
if (temp >= array[child])
break;
// 把孩子结点的值赋给父结点
array[parent] = array[child];
// 选取孩子结点的左孩子结点,继续向下筛选
parent = child;
child = 2 * child + 1;
}
array[parent] = temp;
}
public void heapSort( int[] list) {
// 循环建立初始堆
for ( int i = list.length / 2; i >= 0; i--) {
HeapAdjust(list, i, list.length - 1);
}
// 进行n-1次循环，完成排序
for ( int i = list.length - 1; i > 0; i--) {
// 最后一个元素和第一元素进行交换
int temp = list[i];
list[i] = list[0];
list[0] = temp;
// 筛选 R[0] 结点，得到i-1个结点的堆
HeapAdjust(list, 0, i);
System.out.format("第 %d 趟: \t", list.length - i);
printPart(list, 0, list.length - 1);
}
}
算法分析
堆排序算法的总体情况
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 选择排序 | 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 | 较复杂 |
时间复杂度
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。
当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。
因为堆排序的时间复杂度是O(n+klog2n)，若k≤n/log2n，则可得到的时间复杂度为O(n)。
算法稳定性
堆排序是一种不稳定的排序方法。
因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，
因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。
完整参考代码
JAVA版本
代码实现
以下范例是对上文提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 进行排序。
View Code
运行结果
第 1 趟: 8 7 6 5 2 1 4 3 0 9
第 2 趟: 7 5 6 3 2 1 4 0 8 9
第 3 趟: 6 5 4 3 2 1 0 7 8 9
第 4 趟: 5 3 4 0 2 1 6 7 8 9
第 5 趟: 4 3 1 0 2 5 6 7 8 9
第 6 趟: 3 2 1 0 4 5 6 7 8 9
第 7 趟: 2 0 1 3 4 5 6 7 8 9
第 8 趟: 1 0 2 3 4 5 6 7 8 9
第 9 趟: 0 1 2 3 4 5 6 7 8 9
排序后: 0 1 2 3 4 5 6 7 8 9
参考资料
《数据结构习题与解析》（B级第3版）
7、排序七 归并排序
要点
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的基本思想
将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知：
归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
我们先来考虑第二步，如何合并？
在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。
这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。
先将他们合并到一个局部的暂存数组R2中，带合并完成后再将R2复制回R中。
为了方便描述，我们称 R[low, mid] 第一段，R[mid+1, high] 为第二段。
每次从两个段中取出一个记录进行关键字的比较，将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。
经过这样的过程，R2已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
核心代码
int temp[maxn];
int num=0;///统计逆序对数的。
void Merge(int a[],int left ,int mid,int right)
{
int i=left,j=mid+1,n=0,length=right-left;///i开始为左半部分最左边，j为右半部分最左边。temp数组是从下标0开始存数。
while(i<=mid&&j<=right){
if(a[i]>a[j]){///左边比右边大。
temp[n++]=a[j++];
num+=mid-i+1;///从i到mid都是比a[j]大。
}
else{
temp[n++]=a[i++];
}
}
if(i>mid){///这里说明的是左边全部填满了(因为前面的判断条件是i<=mid，那就是天右边了。
while(j<=right){
temp[n++]=a[j++];
}
}
else{
while(i<=mid){
temp[n++]=a[i++];
}
}
for(int k=0;k<=length;k++){///最后赋值到原数组必须要有的。
a[left+k]=temp[k];
}
}
void mergesort(int a[],int left,int right)
{
if(left<right){
int mid=(left+right)/2;
mergesort(a,left,mid);
mergesort(a,mid+1,right);
Merge(a,left,mid,right);
}
}
掌握了合并的方法，接下来，让我们来了解 如何分解。
在某趟归并中，设各子表的长度为gap，则归并前R[0...n-1]***有n/gap个有序的子表：R[0...gap-1], R[gap...2*gap-1], ... , R[(n/gap)*gap ... n-1]。
调用Merge将相邻的子表归并时，必须对表的特殊情况进行特殊处理。
若子表个数为奇数，则最后一个子表无须和其他子表归并（即本趟处理轮空）：若子表个数为偶数，则要注意到最后一对子表中后一个子表区间的上限为n-1。
核心代码
int i = 0;
// 归并gap长度的两个相邻子表
for (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {
Merge(array, i, i + gap - 1, i + 2 * gap - 1);
}
// 余下两个子表，后者长度小于gap
if (i + gap - 1 < length) {
Merge(array, i, i + gap - 1, length - 1);
}
}
public int[] sort( int[] list) {
for ( int gap = 1; gap < list.length; gap = 2 * gap) {
MergePass(list, gap, list.length);
System.out.print("gap = " + gap + ":\t");
this.printAll(list);
}
return list;
}
算法分析
归并排序算法的性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 归并排序 | 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 | 较复杂 |
时间复杂度
归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。
空间复杂度
由前面的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。
算法稳定性
在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。
归并排序和堆排序、快速排序的比较
若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。
若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。
若从平均情况下的排序速度考虑，应该选择快速排序。
完整参考代码
Java版本
View Code
运行结果
gap = 1: 1 9 3 5 2 4 6 8 7
gap = 2: 1 3 5 9 2 4 6 8 7
gap = 4: 1 2 3 4 5 6 8 9 7
gap = 8: 1 2 3 4 5 6 7 8 9
排序后: 1 2 3 4 5 6 7 8 9
参考资料
《数据结构习题与解析》（B级第3版）
8、排序八 基数排序
要点
基数排序与本系列前面讲解的七种排序方法都不同，它不需要比较关键字的大小。
它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。
不妨通过一个具体的实例来展示一下，基数排序是如何进行的。
设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以0~9来表示的。
所以我们不妨把0~9视为10个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是0，将这个数存入编号为0的桶中。
分类后，我们在从各个桶中，将这些数按照从编号0到编号9的顺序依次将所有数取出来。
这时，得到的序列就是个位数上呈递增趋势的序列。
按照个位数排序： {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。
接下来，可以对十位数、百位数也按照这种方法进行排序，最后就能得到排序完成的序列。
完整参考代码
（1）LSD法实现
实现代码
public class RadixSort {
// 获取x这个数的d位数上的数字
// 比如获取123的1位数，结果返回3
public int getDigit( int x, int d) {
int a[] = {
1, 1, 10, 100
}; // 本实例中的最大数是百位数，所以只要到100就可以了
return ((x / a[d]) % 10);
}
public void radixSort( int[] list, int begin, int end, int digit) {
final int radix = 10; // 基数
int i = 0, j = 0;
int[] count = new int[radix]; // 存放各个桶的数据统计个数
int[] bucket = new int[end - begin + 1];
// 按照从低位到高位的顺序执行排序过程
for ( int d = 1; d <= digit; d++) {
// 置空各个桶的数据统计
for (i = 0; i < radix; i++) {
count[i] = 0;
}
// 统计各个桶将要装入的数据个数
for (i = begin; i <= end; i++) {
j = getDigit(list[i], d);
count[j]++;
}
// count[i]表示第i个桶的右边界索引
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i - 1];
}
// 将数据依次装入桶中
// 这里要从右向左扫描，保证排序稳定性
for (i = end; i >= begin; i--) {
j = getDigit(list[i], d); // 求出关键码的第k位的数字， 例如：576的第3位是5
bucket[count[j] - 1] = list[i]; // 放入对应的桶中，count[j]-1是第j个桶的右边界索引
count[j]--; // 对应桶的装入数据索引减一
}
// 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
for (i = begin, j = 0; i <= end; i++, j++) {
list[i] = bucket[j];
}
}
}
public int[] sort( int[] list) {
radixSort(list, 0, list.length - 1, 3);
return list;
}
// 打印完整序列
public void printAll( int[] list) {
for ( int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int[] array = {
50, 123, 543, 187, 49, 30, 0, 2, 11, 100
};
RadixSort radix = new RadixSort();
System.out.print("排序前:\t\t");
radix.printAll(array);
radix.sort(array);
System.out.print("排序后:\t\t");
radix.printAll(array);
}
}
排序后: 0 2 11 30 49 50 100 123 187 543
算法分析
基数排序的性能
| 排序类别 | 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 复杂性 | ||
| 平均情况 | 最坏情况 | 最好情况 | |||||
| 基数排序 | 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |
时间复杂度
通过上文可知，假设在基数排序中，r为基数，d为位数。则基数排序的时间复杂度为O(d(n+r))。
我们可以看出，基数排序的效率和初始序列是否有序没有关联。
空间复杂度
在基数排序过程中，对于任何位数上的基数进行“装桶”操作时，都需要n+r个临时空间。
算法稳定性
在基数排序过程中，每次都是将当前位数上相同数值的元素统一“装桶”，并不需要交换位置。所以基数排序是稳定的算法。
京公网安备 11010502036488号