第3章 排序算法
使一串记录，按照其中的某个或某些关键字的大小，递增或递减排列起来的操作叫作排序。排序算法就是如何使记录按照要求排列的方法。排序算法在很多领域都得到了足够的重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域，考虑到数据的各种限制和规范，要想得到满足实际需要的优秀算法，需要经过大量的推理和分析。
例如：随机输入一个序列的n个数，序列为：a1,a2,a3,…,an，通过算法实现输出：n个数的排列顺序为：a1',a2',a3',…,an'，使得a1'≤a2'≤a3'≤…≤an'（根据实际需求也可以实现从大到小的排序，方法不唯一）。
1）关于排序算法的一些术语说明：
稳定性：如果a原本在b前面，而a=b，那么排序之后a仍然在b的前面。
不稳定性：如果a原本在b的前面，而a=b，那么排序之后a可能会出现在b的后面。
内排序：所有排序操作都在内存中完成。
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。
时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
2）相关排序算法的对比如下：
注释：n表示数据规模；k表示“桶”的个数；In-place表示占用常数内存，不占用额外内存；Out-place表示占用额外内存。
3）算法根据稳定性分类如下：
3.1 如何实现冒泡排序
难度系数：★★★☆☆
被考查系数：★★★☆☆
分析与解答：
冒泡排序，顾名思义就是整个过程就像气泡一样往上升，单向冒泡排序的基本思想是（假设由小到大排序）：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个时为止。算法原理如下：
1）比较相邻的元素，如果第一个比第二个大，那么就交换这两个元素。
2）对每一对相邻元素做同样的工作，从第一对开始到最后一对结束，最后的元素应该会是最大的数。
3）除了最后一个元素外，针对其他的元素重复以上的步骤。
4）对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较为止。
以数组array（36, 25, 48, 12, 25, 65, 43, 57）为例，具体排序过程如下：
初始状态：[36 25 48 12 25 65 43 57]
1趟排序：[25 36 12 25 48 43 57] 65]
2趟排序：[25 12 25 36 43 48] 57 65]
3趟排序：[12 25 25 36 43] 48 57 65]
4趟排序：[12 25 25 36] 43 48 57 65]
5趟排序：[12 25 25] 36 43 48 57 65]
6趟排序：[12 25] 25 36 43 48 57 65]
7趟排序：[12] 25 25 36 43 48 57 65]
根据以上的实现原理，实现代码如下：
程序的运行结果为
在传统的冒泡排序基础上，可以进一步改进冒泡排序算法，通过设置一个标志bool，用于记录每趟排序中最后一次交换的位置。由于bool标志之后的记录均已交换到位，因此下一趟排序时只要扫描到bool位置即可，不需要再对bool后的循环排序。改进后的冒泡排序算法2如下：
程序的运行结果为
因为传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，所以可以考虑在每趟排序中进行正向和反向两遍冒泡的方法，一次得到最大者和最小者，从而可使排序趟数将近减少一半。再次改进后的冒泡排序法3如下：
程序的运行结果为
以上介绍的冒泡排序法中，它们执行的效率：
传统冒泡排序法＜改进后冒泡排序法2＜改进后冒泡排序法3。
算法性能分析：
最佳情况：T（n）=O（n），当输入的数据为正序时，则是最佳情况。
最差情况：T（n）=O（n2），当输入的数据是反序时，则是最差情况，需依次从头到尾重新排序。
平均情况：T（n）=O（n2）。
3.2 如何实现插入排序
难度系数：★★★☆☆
被考查系数：★★★☆☆
分析与解答：
插入排序的基本思想：对于给定的一组记录，初始时假设第一个记录自成一个有序序列，其余的记录为无序序列。接着从第二个记录开始，按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，直至最后一个记录插入到有序序列中为止。
以数组array（38, 65, 97, 76, 13, 27, 49）为例，直接插入排序具体步骤如下：
第一步插入38以后：[38] 65 97 76 13 27 49
第二步插入65以后：[38 65] 97 76 13 27 49
第三步插入97以后：[38 65 97] 76 13 27 49
第四步插入76以后：[38 65 76 97] 13 27 49
第五步插入13以后：[13 38 65 76 97] 27 49
第六步插入27以后：[13 27 38 65 76 97] 49
第七步插入49以后：[13 27 38 49 65 76 97]
根据以上的实现原理，实现代码如下：
程序的运行结果为
可以对传统的插入排序算法进行改进，在查找插入位置时使用二分查找的方式。改进后的插入排序算法如下：
程序的运行结果为
算法性能分析：
最佳情况：T（n）=O（n），输入数组按升序排列。
最坏情况：T（n）=O（n2），输入数组按降序排列。
平均情况：T（n）=O（n2）。
3.3 如何实现归并排序
难度系数：★★★★☆
被考查系数：★★★☆☆
分析与解答：
归并排序是利用递归与分治技术将数据序列划分成越来越小的子表，再对子集排序，最后用递归方法将排好序的子表合并成为越来越大的有序序列。归并排序中，“归”代表的是递归的意思，即递归的将数组折半的分离为两个子数组，如数组：[2, 6, 1, 0]，会先折半，分为[2, 6]和[1, 0]两个子数组，然后再折半将数组分离，分为[2]、[6]、[1]和[0]。“并”就是将分开的数据按照从小到大或者从大到小的顺序再放到一个数组中。如上面的[2]和[6]合并到一个数组中是[2, 6]，[1]和[0]合并到一个数组中是[0, 1]，然后再将[2, 6]和[0, 1]合并到一个数组中即为[0, 1, 2, 6]。
具体而言，归并排序算法的原理如下：对于给定的一组记录（假设共有n个记录），首先将数组一分为二，对于每个子数组采用同样的方法递归地划分为更小的数组，直到子数组的大小为1（大小为1的子数组是有序的）。接着需要把相邻的两个子数组进行归并（归并后的子数组还是有序的）为更大的数组，直到归并后的数组大小跟原数组相同时算法结束。
所以，归并排序的关键就是两步：第一步，划分子表；第二步，合并半子表。以数组array（49,38, 65, 97, 76, 13, 27）为例，排序过程如下：
1）数组初始序列为：[24,13,26,1,2,27,38,15]
2）第一趟划分子数组：[24,13,26,1]，[2,27,38,15]
3）对子数组继续划分：[24,13]，[26,1]，[2,27]，[38,15]
4）对子数组继续划分：[24]，[13]，[26]，[1]，[2]，[27]，[38]，[15]
5）归并：[13,24]，[1，26]，[2,27]，[15，38]
6）继续归并：[1，13，24,26]，[2,15,27,38]
7）继续归并：[1，2，13，15，24, 26, 27,38]
根据以上的实现原理，实现代码如下：
程序的运行结果为
算法性能分析：
最佳情况：T（n）=O（nlogn）。
最差情况：T（n）=O（nlogn）。
平均情况：T（n）=O（nlogn）。
3.4 如何实现快速排序
难度系数：★★★★★
被考查系数：★★★★☆
分析与解答：
快速排序是一种非常高效的排序算法，它采用“分而治之”的思想，把大的问题拆分为小的问题，小的问题再拆分为更小的问题。其原理如下：对于一组给定的记录，通过一趟排序后，将原序列分为两部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后两部分的记录进行快速排序，递归该过程，直到序列中的所有记录均有序为止。
对于给定数组数组是A[0]…A[N-1]，首先任意选取一个数据（通常选用数组的第一个元素）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。由此可见，一趟快速排序的算法是：
1）设置两个变量i、j，并初始化为：i=0，j=N-1；
2）以第一个数组元素作为关键数据（假设这个关键数据为key）；
3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3）、4）步，直到i=j；3），4）步中，没找到符合条件的值，即步骤3中A[j]不小于key，步骤4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i，j指针位置不变。另外，i=j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
以数组array（49, 38, 65, 97, 76, 13, 27, 49）为例。
第一趟排序过程如下：
初始状态：[49 38 65 97 76 13 27 49]
第一次交换后：[27 38 65 97 76 13 49 49]
第二次交换后：[27 38 49 97 76 13 65 49]
j向左扫描，位置不变，第三次交换后：[27 38 13 97 76 49 65 49]
i向右扫描，位置不变，第四次交换后：[27 38 13 49 76 97 65 49]
j向左扫描 [27 38 13 49 76 97 65 49]
整个排序过程如下：
初始状态：[49 38 65 97 76 13 27 49]
一趟排序之后：[27 38 13] 49 [76 97 65 49]
二趟排序之后：[13] 27 [38] 49 [49 65]76 [97]
三趟排序之后：13 27 38 49 49 [65]76 97
最后的排序结果：13 27 38 49 49 65 76 97
根据以上的实现原理，实现代码如下：
程序的运行结果为
快速算法是通过分治递归来实现的，其效率在很大程度上取决于参考元素的选择，可以选择数组的中间元素，也可以随机得到三个元素，然后选择中间的那个元素（三数中值法）。另外还有一点，就是当分割时，如果分割出来的子序列的长度很小（小于20）的话，那么通常递归的排序效率就没有诸如插入排序或希尔排序那么快了。因此可以先判断数组的长度，如果小于10的话，那么直接用插入排序，而不是递归调用快速排序。
算法性能分析：
最佳情况：T（n）=O（nlog2n）。
最差情况：T（n）=O（n2）。
平均情况：T（n）=O（nlog2n）。
3.5 如何实现选择排序
难度系数：★★★☆☆
被考查系数：★★★☆☆
分析与解答：
选择排序是一种简单直观的排序算法，它的基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录与第一个记录的位置进行交换；接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换；重复该过程，直到进行比较的记录只有一个时为止。算法原理如下：
每一趟在n-i+1（i=1,2,…,n-1）个记录中选择关键字最小的记录作为有序序列中第i个记录，其中最便捷的是简单选择排序，其过程如下：通过n-i 次关键字间的比较，从（n-i+1）个记录中选择出关键字最小的记录，并与第i个记录交换位置。
以数组array（38, 65, 97, 76, 13, 27, 49）为例，具体步骤如下：
第一趟排序后：13 [65 97 76 38 27 49]
第二趟排序后：13 27 [97 76 38 65 49]
第三趟排序后：13 27 38 [76 97 65 49]
第四趟排序后：13 27 38 49 [97 65 76]
第五趟排序后：13 27 38 49 65 [97 76]
第六趟排序后：13 27 38 49 65 76 [97]
最后排序结果：13 27 38 49 65 76 97
根据以上的实现原理，实现代码如下：
程序的运行结果为
选择排序、快速排序、希尔排序和堆排序都不是稳定的排序算法，而冒泡排序、插入排序和归并排序都是稳定的排序算法。
引申：请简单描述顺序查找和二分查找（也称为折半查找）算法。
顺序查找是在一个已知无（或有）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构，而且表中元素要按关键字有序排列。实现代码如下：
程序的运行结果为
3.6 如何细实现希尔排序
难度系数：★★★★☆
被考查系数：★★★☆☆
分析与解答：
希尔排序也被称为“缩小增量排序”，它的基本原理如下：首先将待排序的数组元素分成多个子序列，使得每个子序列的元素个数相对较少，然后对各个子序列分别进行直接插入排序，待整个待排序序列“基本有序后”，最后再对所有元素进行一次直接插入排序。具体步骤如下：
1）选择一个步长序列t1,t2,…,tk，满足ti＞tj（i＜j），并且tk=1；
2）对待排序列进行k趟排序，其中k是步长序列个数；
3）每趟排序，根据对应的步长ti，将待排序列分割成ti个子序列，分别对各个子序列进行直接插入排序。
注意，当步长因子为1时，所有元素作为一个序列来处理，其长度为n。以数组array（26, 53, 67, 48, 57, 13, 48, 32, 60, 50），步长序列为（5, 3, 1）为例。具体步骤如下：
根据以上的实现原理，实现代码如下：
程序的运行结果为
算法性能分析：
最佳情况：T（n）=O（nlogn）。
最坏情况：T（n）=O（nlogn）。
平均情况：T（n）=O（nlogn）。
3.7 如何实现堆排序
难度系数：★★★★★
被考查系数：★★★★★
分析与解答：
堆是一种特殊的树形数据结构，其每个结点都有一个值，通常提到的堆都是指一棵完全二叉树，根结点的值小于（或大于）两个子结点的值。同时，根结点的两棵子树也分别是一个堆。
堆排序是一种树形选择排序，在排序过程中，将R[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆一般分为大顶堆和小顶堆两种。如果根结点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值，那么这个堆被称之为大顶堆。此时，堆顶元素必为最大值。如果根结点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值，那么这个堆被称之为小顶堆。此时，堆顶元素必为最小值。
堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，再将堆的最后一个元素与堆顶元素（即二叉树的根结点）进行交换后，堆的最后一个元素即为最大记录；接着将前（n-1）个元素（即不包括最大记录）重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录，重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。
堆排序主要包括两个过程：一是构建堆；二是交换堆顶元素与最后一个元素的位置。算法原理如下：
1）将初始待排关键字序列R[1…n]构建成大顶堆，此堆为初始的无序区；
2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区R[1…n-1]和新的有序区R[n],且满足R[1…n-1]≤R[n]；
3）由于交换后新的堆顶R[1]可能违反大顶堆的性质，因此需要对当前无序区R[1…n-1]调整为大顶堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区R[1…n-2]和新的有序区R[n-1,n-1]。不断重复此过程直到有序区的元素个数为（n-1），则整个排序过程完成。
根据以上的实现原理，实现代码如下：
程序的运行结果为
算法性能分析：
最佳情况：T（n）=O（nlogn）。
最差情况：T（n）=O（nlogn）。
平均情况：T（n）=O（nlogn）。
3.8 如何实现计数排序
难度系数：★★★★☆
被考查系数：★★★☆☆
分析与解答：
计数排序（Counting sort）是一种稳定的排序算法。计数排序需要使用一个额外的数组countArr，其中第i个元素是待排序数组arr中值等于i的元素个数。然后根据数组countArr将arr中的元素排到正确的位置。注意，它只能对整数进行排序。算法原理如下：
1）找出待排序的数组中最大和最小的元素；
2）统计数组中每个值为i的元素出现的次数，存入数组countArr的第i项，countArr[i]表示数组中等于i的元素出现的次数；
3）从待排序列arr的第一个元素开始，将arr[i]放到正确的位置，即前面有几个元素小于等于它，它就放在第几个位置。
根据以上的实现原理，实现代码如下：
程序的运行结果为
算法性能分析：
当输入的元素是n 个0～k之间的整数时，它的运行时间是O（n+k）。计数排序不是比较排序，所以排序的速度快于任何比较排序算法。
最佳情况：T（n）=O（n+k）。
最差情况：T（n）=O（n+k）。
平均情况：T（n）=O（n+k）。
3.9 如何实现桶排序
难度系数：★★★★☆
被考查系数：★★★☆☆
分析与解答：
桶排序（Bucket sort）的工作原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序，有可能再使用别的排序算法或是以递归方式继续使用桶排序。算法原理如下：
1）设置一个定量的数组当作空桶；
2）遍历输入数据，并且把数据一个个放到对应的桶里去；
3）对每个非空的桶进行排序；
4）从非空的桶里把排好序的数据合并起来。
根据以上的实现原理，实现代码如下：
程序的运行结果为
算法性能分析：
桶排序最好情况下使用线性时间O（n），它的时间复杂度取决于对各个桶之间数据进行排序的时间复杂度，因为其他部分的时间复杂度都为O（n）。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况：T（n）=O（n+k）。
最差情况：T（n）=O（n2）。
平均情况：T（n）=O（n+k）。