第七章 排序

一 基本概念

填空题

1. 所谓排序，就是要整理文件中的记录，使得它按照给定的关键字递增（或递减）的次序排列。
2. 若整个待排序数据都在内存中处理，不涉及数据的内，外存交换，则称这种排序为内部排序（简称内排序）；反之为外排序。按所用排序策略的不同，内部排序方法又可以分为五类：插入，选择，交换，归并和分配排序。

解答题

评价排序算法的标准主要有两条：执行算法需要的时间，以及算法所需要的附加空间。另外，算法本身的复杂度也是考虑的重要因素之一。

二 插入排序

单选题，填空题，解答题

直接插入排序的基本思想是：假设待排序的记录存储在数组R[1…n]中，在排序过程的某一时刻，R被划分成两个子区间，R[1…i-1]和R[i…n]，其中前一个为已排好序的有序区，而后一个为无序区，开始时有序区中只含有一个元素R[1]，无序区为R[2..n]。排序过程中，只需要每次从无序区中取出第一个元素，把它插入到有序区的适当位置，使之成为新的有序区，依次这样经过n-1次插入后，无序区为空，有序区中包含了全部n个元素，至此排序完毕。

解答题

直接插入排序算法中的R[0]有两个作用，一个作用是在进入查找循环之前保存R[i]的副本，但主要还是用来在查找循环中“监视”数组下标变量j是否越界，一旦越界（即j=0）,R[0].key自比较，使循环条件不成立而结束循环。因此，常把R[0]称为哨兵。

单选题，填空题，解答题

希尔排序的基本思想是：先取定一个小于n的整数d1作为第一个增量，把数组R中的全部元素分成d1个组，所有下标距离为d1的倍数的元素放在同一组中，即R[1]，R[1+d1]，R[1+2d1]，…为第一组，R[2]，R[2+d2]，…，为第二组，…，接着在各组内进行直接插入排序，然后再取d2（d2<d1）为第二个增量，重复上述分组和排序，直到所取的增量dt=1（dt<dt-1<…d2<d1），把所有的元素放在同一组中进行直接插入排序为止。

三 交换排序

单选题，填空题，解答题

1. 冒泡排序过程具体描述为：首先将R[n].key和R[n-1].key进行比较，若R[n].key<R[n-1].key，则交换R[n]和R[n-1]，使轻者上浮，重者下沉；接着比较R[n-1].key和R[n-2].key，同样使轻者上浮，重者下沉，依此类推，直到比较R[2].key和R[1].key，若反序则交换，第一趟排序结束，此时，记录R[1]的关键字最小。然后再对R[n]~R[2]的记录进行第二趟排序，使次小关键字的元素被上浮到R[2]中，重复进行n-1趟后，整个冒泡排序结束。
2. 快速排序的基本思想是：首先在当前无序区R[low … high]中任取一个记录作为排序比较的基准（不妨设为x），用此基准将当前无序区划分为两个较小的无序区R[low … i-1]和R[i+1 .. high]，并使左边的无序区中所有的关键字均小于等于基准关键字，右边无序区中所有记录的关键字均大于等于基准的关键字，而基准记录x则位于最终排序的位置i上，即R[low .. i-1]中关键字<= x.key <=R[i+1..high]中的关键字。这个过程称为一趟快速排序（或一次划分）。当R[low .. i-1]和R[i+1 .. high]均非空时，分别对它们进行上述划分，直到所有的无序区中的记录均已排好序为止。

四 选择排序

单选题，填空题，解答题

直接选择排序的基本思想是：每次从待排序的无序区中选择出关键字值最小的记录，将该记录与该区中的第一个记录交换位置。初始时，R[1…n]为无序区，有序区为空。第一趟排序是在无序区R[1.. n]中选出最小的记录，将它与R[1]交换，R[1]为有序区；第二趟排序是在无序区R[2 .. n]中选出最小的记录与R[2]交换，此时R[1..2]为有序区；依此类推，做n-1趟排序后，区间R[1.. n]中记录按递增有序。

解答题

堆排序是一种树形选择排序，它的基本思想是：在排序过程中，将记录数组R[1.. n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）记录。堆的定义如下：n个记录的关键字序列k1, k2, …, kn称为堆，当且仅当满足以下关系：

ki<=k2i且ki<=k2i+1，或ki>=k2i且ki>=k2i+1(1<=i<=[n/2])

前者称为小根堆，后者称为大根堆。堆排序正是利用大根堆（或小根堆）来选取当前无序区中关键字最大（或最小）的记录实现排序的。每一趟排序的操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中最后一个记录交换，这正好与选择排序相反。

五 归并排序

单选题，填空题，解答题

归并排序的基本思想是：首先将待排序文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到[n/2]个长度为2的有序子文件；然后再把这[n/2]个有序的子文件两两归并，如此反复，直到最后得到一个长度为n的有序文件为止，这种排序方法称为二路归并排序。

六 分配排序

单选题，填空题，解答题

1. 箱排序又称桶排序，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0], R[1], …, R[n-1]，把关键字等于k的记录全部都装入第k个箱子里（分配），然后按序号依次将各非空的箱子首尾连接起来。
2. 基数排序的思想是：首先按关键字的最低位$k_i ^(d-1)$进行箱排序，然后再按关键字的$k_i^[d-2]$进行箱排序，…，最后按最高位$k_i^0$进行箱排序。在d趟箱排序中，需要设置箱子的个数就是基数rd。

七 内部排序方法的分析比较

单选题，填空题

（1） 时间复杂度

1. 直接插入，直接选择，冒泡排序算法的时间复杂度为O(n^2)。
2. 快速，归并，堆排序算法的时间复杂度为O(nlog2n)。
3. 希尔排序算法的时间复杂度很难计算，有几种较接近的答案：O(nlog2n)或O(n^1.25)。
4. 基数排序算法的时间复杂度为O(d*(rd+n))，其中rd是基数，d是关键字的位数，n是元素个数。

（2） 稳定性

1. 直接插入，冒泡，归并和基数排序算法是稳定的。
2. 直接选择，希尔，快速和堆排序算法是不稳定的。

（3） 辅助空间，空间复杂度

1. 直接插入，直接选择，冒泡，希尔和堆排序算法需要辅助空间为O(1)。
2. 快速排序算法需要辅助空间为O(log2n)。
3. 归并排序算法需要辅助空间为O(n)。
4. 基数排序算法需要辅助空间为O(n+rd)。

解答题，选取排序方法时需要考虑的主要因素有：

1. 待排序的记录个数
2. 记录本身的大小和存储结构
3. 关键字的分布情况
4. 对排序稳定性的要求
5. 时间和空间复杂度等

解答题，排序方法的选取

1. 若待排序的一组记录数目n较小（如n<=50）时，可采用插入排序或选择排序。
2. 若n较大时，则采用快速排序，堆排序或归并排序。
3. 若待排序记录按关键字基本有序时，则适宜用直接插入排序或冒泡排序。
4. 当n很大，而且关键字位数较少时，采用链式基数排序较好。
5. 关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。