第七章排序从来处来往去处去次序之美美在规矩利在行方概述插入排序 交换排序 选择排序 归并排序 表排序 基数排序各种内排序方法的比较 外排序概述■ 排序：将一组杂乱无章的数据按一定的规律顺次 排列起来■ 数据表(datalist):它是待排序数据记录的有限集 合■ 排序码(key):通常数据记录有多个属性域，即多 个数据成员组成，其中有一个属性域可用来区分 记录，作为排序依据该域即为排序码口每个数据表用哪个属性域作为排序码，要视具 体的应用需要而定□本章所涉及排序码的值允许重复■排序算法的稳定性：如果在记录序列中有两个记 录r[i]和5,它们的排序码值k[ij == k[j],且在排序 之前，记录门“排在r[j]前面如果在排序之后，记 录邙]仍在记录的前面，则称这个排序方法是 稳定的,否则称这个排序方法是不稳定的■内排序与外排序□内排序是指在排序期间数据记录全部存放在内 存的排序；□外排序是指在排序期间全部记录个数太多，不 能同时存放在内存，必须根据排序过程的要求, 不断在内、外存之间移动的排序■排序的时间开销：排序的时间开销是衡量算法好 坏的最重要的标志内排序的时间开销可用算法 执行中的排序码比较次数与数据移动次数来衡量; 外排序的时间开销要看读写外存的次数。
算法运行时间代价的大略估算一般都按平均情况 进行估算对于那些受记录排序码序列初始排列 及记录个数影响较大的，需要按最好情况和最坏 情况分别进行估算算法执行时所需的附加存储：评价算法好坏的另 一标准■从排序过程中数据的总体变化趋势来看，排序方 法的处理可以分为两大类1)有序区增长：将数据表分成有序区和无序区，在 排序过程中逐步扩大有序区，缩短无序区，直到 有序区扩大到整个数据表为止如插入排序、选 择排序、起泡排序、堆排序、归并排序等2)有序程度增长：数据表不能明确区分有序区和无 序区，随着排序过程的执行，逐步调整表中元素 的排列，使得表中的有序程度不断提高，直到完 全有序如快速排序、希尔排序、基数排序等待排序数据表的结构定义const int DefaultSize = 100; typedef int DataType;typedef struct Element {DataType key; otherdata;〃表元素定义〃排序码〃其他数据成员）；typedef struct dataList { 〃数据表定义Element elem[DefaultSize]; 〃存宿羲组int n; 前元素个数插入排序(Insert Sorting)■基本方法是：每步将一个待排序的记录，按其排序码值的大小，插入到前面已经排好序的一组记录的适当位置上,直到记录全部插入为止。
直接插入排序(Insert Sort)■直接插入排序的基本思想是：当插入第个记录时,前面的elem[0h …,elem[i-l]已经排好序这时，用的排序码与…的排序码顺序比较，找到插入位置即将插入,原来位置上的记录向后顺移1 0 1 2 3 4 5 6 7t 25 > 21 ,无需移动t49>25,无需移动t 37 < 5252, 49后移直接插入排序的算法void InsertSort ( dataList& L ) {Element w； inti";for (i = 1; i < L.n; i++ ) 〃插入n-1 趟if ( L.elem[i].key < L.elem[i-l].key ) {w = L.elem[i]; L.elem[i] = L.elem[i-1];for(j = i-l; j>O;j—) 〃从后向前比较if ( w.key < L.elem[j-l].key ) 〃比j-l元素小L.elem[j] = L.elem[j-1]; 〃让j-1 元素后移 else break;L.elem[j] = w;法分析■ 设待排序记录个数为〃，则该算法的主程序执行 趟。
排序码比较次数和记录移动次数与记录 排序码的初始排列有关■ 最好情况下，排序前记录已按排序码的值从小到 大有序，每趟只需与前面有序记录序列的最后一 个记录比较1次，移动0次记录，总的排序码比 较次数为"-1,记录移动次数为Oo■ 最坏情况下，第i趟时第，个记录必须与前面i 个记录都做排序码比较，并且每做1次比较就要 做1次数据移动■ 因此，在最坏情况下，总排序码比较次数KCN和 记录移动次数RMN分别为n-lKCN = i =双11 - D n2/29i=lRMN = £ (i + 2) = (n + 4)(n -1)/2n2/2• ]■ 在平均情况〒的排序码比较次数和记录移动次数 约为4/4因此，直接插入排序的时间复杂度为 O(n2)o■ 直接插入排序是一种稳定的排序方法■ 直接插入排序需要一个附加记录暂存待插记录折半插入排序(Binary Insertsort)-折半插入排序的基本思想是：设在顺序表中有一 个记录序列 elem[0]9 elem[l],elem[w-l]o 其中, elem[0]5 elem[l]^…,elem[i-l]是已经排序的数据 记录在插入时，不是利用顺序查找从后 向前寻找插入位置，而是利用折半查找法寻找elem[f]的插入位置。
折半插入排序的算法void BinaryInsSort ( dataList& L ) { Element w; int i, k, left, right, mid; for (i = 1; i < L.n; i++ ) { 159-15left = 0; right = i-1; w = L.elem[i];while (left <= right) {〃在内寻找elem[i]插入位置mid = (left+right )/2; 〃中间位置if ( w.key < L.elem[mid].key ) 〃小于中点值right = mid-1; 〃*蓊区间else left = mid+1; 〃右缩区间)for ( k = i-1; k >= left; k--)L.elem[k+1] = L.elem[k]; 〃空出 left 位置L.elem[left] = w;} // for算法分析- 折半搜索比顺序搜索查找快，所以折半插入排序 就平均性能来说比直接插入排序要快 它所需的排序码比较次数与待排序记录序列的初 始排列无关,仅依赖于记录个数 在插入第，个记录时，需要经过|_1吗，」+1次排序码比较，才能确定它应插入的位置。
因此，将〃个记录元素（为推导方便，设为〃 =2匕 k = log2n ）,折半插入排序所进行的排序码比较 次数为：n-1*[1峭」+1)=!+2+土・+3 h—卜k+k 1 —1~ K i=l 2° 21 22 2k-1= 1*22"+3*22+・・・ + k*2i= (k-l)* 2k +1 = n^(log2n-l) + l = n^log2n-n + l■ 这是折半查找算法分析得到的结果折半查找的 时间复杂度为O(nk)g2n)，这是指排序码比较次数 的时间开销，但记录移动次数就不同了■ 折半插入排序的记录移动次数比直接插入排序多 一点，依赖于记录元素的初始排列■ 折半插入排序是一个稳定的排序方法■ 折半插入排序需要一个附加记录暂存待插记录希尔排序(Shell Sort).希尔排序方法又称为缩小增量排序该方法的基本思想是：设待排序记录序列有n个记 录，首先取一个整数gap vn作为间隔，将全部记录 分为gap个子序列，所有距离为gap的记录放在同 一个子序列中，在每一个子序列中分别施行直接插 入排序■然后缩小间隔gap,例如取gap = [gap/2」，重复上 述的子序列划分和排序工作。
直到最后取gap = 1, 将所有记录放在同一个序列中排序为止16V21.21 后移08 < 25. 25后移52 > 49.无需移动37 > 25.无需移动0 1 2 3 4 5 6 7i = 2 gap=249 > 16 21 < 49 52 > 49无需移动 49后移无需移动25* > 08 25 = 25 37 > 25无需移动无需移动无需移动结果i = 3 gap=l国同闻同0 12 316 <0816后移国园国国国国阂国4 5 6 725 <49 37 < 5249后移 52, 49后移国同同阂■开始时gap的值较大，子序列中的记录较少，排 序速度较快；随着排序进展，gap值逐渐变小， 子序列中记录个数逐渐变多，由于前面工作的基 础，大多数记录已基本有序，所以排序速度仍然 很快希尔排序的算法void ShellSort ( dataList& L ) {Elementw； gap = L.n / 2;while ( gap != 0 ) { 〃宿环，直到gap为零for (i = gap; i < L.n; i++ ) {w = L.elem[i]; 〃直接插入排序for (j = i; j >= gap; j = j-gap )if ( w.key < L.elem[j - gap] .key )L.elem[j] = L.elem[j-gap];else break;L.elem[j] = w;)gap = gap / 2;)算法分析■ 开始时gap的值较大，子序列中的记录较少，排 序速度较快；随着排序进展，gap值逐渐变小， 子序列中记录个数逐渐变多，由于前面工作的基 础，大多数记录已基本有序，所以排序速度仍然 很快。
■ gap取法有多种最初shell提出取gap = |_n/2」， gap = Lgap/2j,直至!]gap = lo knuth 提出取 gap = [gap/3」+L■ 对特定的待排序记录序列，可以准确地估算排序 码的比较次数和记录移动次数■ 但想要弄清排序码比较次数和记录移动次数与增 量选择间的依赖关系，并给出完整的数学分析， 还没有人能够做到Knuth利用大量实验统计资 料得出：当n很大时，排序码平均比较次数和记 录平均移动次数约在ni・25到1.6出・25的范围内■ 后来Hibbard提出一个稍微不同的增量序列，让 gap = 2T 7, 3 J 最坏情况下结果更好，运行时间在理论上证明可达到O(n3/2),但实 际模拟结果可达到O(n5”■ 希尔排序是个不稳定的排序方法交换排序(Exchange Sort)■ 基本思想是两两比较待排序记录的排序码，如发 生逆序(即排列顺序与排序后的次序正好相反)则 交换之直到所有记录都排好序为止起泡排序(Bubble Sort)■ 起泡排序的基本思路是：设待排序记录序列中的记录个数为〃最多作“T趟起泡，2,…，n-lo在第，趟.中从后向前,j = 〃一2,…，i,顺次两两。