Chapter10——排序

1、第十章第十章排序排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.8 外部排序外部排序10.1 概概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、什么是排序？一、什么是排序？ 排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。例如：将下列关键字序列52, 49, 80, 36, 14, 58,

2、61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般情况下，假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作操作称作排序排序。排序算法的稳定性：排序算法的稳定性： 如果待排序的序列中，存在多个具有相同关键字的记录，若经过排序这些记录的相对次序保持不变，则称这种排序算法是稳定稳定的；经过排序这些记录的相对次序发生了改变，则称这种排

3、序算法是不稳定不稳定的。二、内部排序和外部排序二、内部排序和外部排序 待排序记录存放在计算机随机存储器中进行的排序过程，为内部排序内部排序； 若待排序记录的数量很大，以至内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程，为外部排序外部排序。三、内部排序的方法三、内部排序的方法内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区 按排序过程中依据的不同原则按排序过程中依据的不同原则 插入排序插入排序 交换排序交换排序 选择排序选择排序 归并排序归并排序 基数排序基数排序 按排序

4、过程所需的工作量按排序过程所需的工作量 简单的排序方法，其时间复杂度为简单的排序方法，其时间复杂度为O(n2) 先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlogn) 基数排序，其时间复杂度为基数排序，其时间复杂度为O(d.n)1. 插入类插入类将无序子序列中的一个或几个记录“插入插入”到有序序列中，从而增加记录的有序子序列的长度。2. 交换类交换类通过“交换交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。3. 选择类选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，

5、以此方法增加记录的有序子序列的长度。4. 归并类归并类通过“归并归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。5. 其它方法其它方法待排记录的数据类型定义如下待排记录的数据类型定义如下:#define MAXSIZE 1000 / 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型关键字类型为整数类型typedef struct KeyType key; / 关键字项关键字项 InfoType otherinfo; / 其它数据项其它数据项 RcdType; / 记录类型记录类型typedef struct RcdType

6、 rMAXSIZE+1; / r0闲置闲置 int length; / 顺序表长度顺序表长度 SqList; / 顺序表类型顺序表类型 10. 2 插插 入入 排排 序序一趟直接插入排序的基本思想： 把把n n个记录的序列划分为已排序部分和个记录的序列划分为已排序部分和未排序部分，即在涉及第未排序部分，即在涉及第i i个记录个记录R Ri i时时, ,（R R1 1, . . . ,R, . . . ,Ri-1i-1）是已排好的有序部分，）是已排好的有序部分，（R Ri i,R,Ri+1i+1, . . . ,R, . . . ,Rn n）属于未排序部分。）属于未排序部分。找出找出RiRi在此

7、有序序列中应插入的位置，将在此有序序列中应插入的位置，将RiRi插入。原位置上的记录至插入。原位置上的记录至RiRi均顺序后移均顺序后移一位。一位。有序序列R1.i-1Ri无序序列 Ri.n有序序列R1.i无序序列 Ri+1.n实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：3将Ri 插入插入(复制)到Rj+1的位置上。2将Rj+1.i-1中的所有记录记录均后移后移 一个位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的具体实现方法导致不同的不同的具体实现方法

8、导致不同的算法描述算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）一、直接插入排序一、直接插入排序利用 “顺序查找顺序查找”实现“在R1.i-1中查找查找Ri的插入位置”算法的实现要点：算法的实现要点：从Ri-1起向前进行顺序查找， 监视哨设置在R0；R0 = Ri; / 设置设置“哨兵哨兵”循环结束表明Ri的插入位置为 j +1R0jRifor (j=i-1; R0.keyRj.key; -j); / 从后往前找从后往前找j=i-1插入位置插入位置 对于在查找过程中找到的那些关键字不小于Ri.key的记录，并在查找的同时

9、实现记录向后移动；for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj ; R0jRij= i-1上述循环结束后可以直接进行“插入”插入位置插入位置令 i = 2，3，, n, 实现整个序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 直接插入排序示例直接插入排序示例 初始状态初始状态 18 12 10 12 30 16 第第1趟（趟（i=2） (12) 12 18 10 12 30 16 第第2趟（趟（i=3） (10) 10 12 18 12 30 16 第第3趟（趟

10、（i=4） (12) 10 12 12 18 30 16 第第4趟（趟（i=5） (30) 10 12 12 18 30 16 第第5趟（趟（i=6） (16) 10 12 12 16 18 30待排序记录序列为待排序记录序列为(18(18，1212，1010，1212，3030，1616）简单插入排序每一趟执行后的序列状态简单插入排序每一趟执行后的序列状态: :监视哨监视哨void InsertionSort ( SqList &L ) / 对顺序表对顺序表 L 作直接插入排序作直接插入排序 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-

11、1.key) / InsertSortL.r0 = L.ri; / 复制为监视哨复制为监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移记录后移L.rj+1 = L.r0; / 插入到正确位置插入到正确位置内部排序的时间分析时间分析：实现内部排序的基本操作基本操作有两个：(2) “移动移动”记录。(1) “比较比较”序列中两个关键字的大小；对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录

12、序列中逆序有序）：“比较”的次数：112nni02) 1)(4() 1(2nnini“移动”的次数：“移动”的次数：2) 1)(4() 1(2nnini对于直接插入排序：其其时间复杂度时间复杂度为为O(n2)适用于当待排序记录的数量很小时 一般情况下，待排序记录是随机的，即一般情况下，待排序记录是随机的，即待排序列中的记录可能出现的各种排列的概待排序列中的记录可能出现的各种排列的概率相同，则可取最小值和最大值的平均值，率相同，则可取最小值和最大值的平均值，作为直接插入排序时所需进行关键字的比较作为直接插入排序时所需进行关键字的比较次数和移动记录的次数，约为次数和移动记录的次数，约为n24. 因

13、为 R1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找折半查找实现“在R1.i-1中查找查找Ri的插入位置”，如此实现的插入排序为折半插折半插入入排序。二、折半插入排序二、折半插入排序void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移记录后移L.rhigh+1 = L.r0; / 插入插入low = 1; high = i-1;while (low=high) m = (lo

14、w+high)/2; / 折半折半if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区插入点在低半区else low = m+1; / 插入点在高半区插入点在高半区14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r对于折半插入排序，其，其时间复杂度时间复杂度为为O(n2)折半插入排序适用于当待排序记录的数量很大时，可大幅度降低关键字的比较次数。 三、希尔排序三、希尔排序

15、(又称缩小增量排序又称缩小增量排序) 基本思想：对待排记录序列先作基本思想：对待排记录序列先作“宏宏观观”调整，再作调整，再作“微观微观”调整。调整。 所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃跳跃式式”的插入排序。即先将整个待排记录序列分的插入排序。即先将整个待排记录序列分割成若干子序列分别进行直接插入排序，割成若干子序列分别进行直接插入排序，待整个序列中的记录待整个序列中的记录“基本有序基本有序”时，再时，再对全体记录进行一次直接插入排序。对全体记录进行一次直接插入排序。 具体做法为：具体做法为：将记录序列分成若干子序列，分别对每个子将记录序列分成若干子序列，分别对每个子序列进

16、行插入排序。序列进行插入排序。其中，其中，d d 称为增量，它的值在排序过程中从大到称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序小逐渐缩小，直至最后一趟排序减为减为 1 1。例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 初始关键字初始关键字 49 38 65 97 76 13 27 49 55 04 49 13 38 27 65 49 97 55 76 04 二趟排序结果二趟排序结果 13 04 49 38 27 49 55 65 97 76设增量设增量

17、d =5设增量设增量 d =3设增量设增量 d =1一趟排序结果一趟排序结果 13 27 49 55 04 49 38 65 97 76 13 55 38 76 27 04 65 49 49 97三趟排序结果三趟排序结果 04 13 27 38 49 49 55 65 76 97void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 记录后移，查找插入位置记录后移，查找插入位置 L.rj+d

18、k = L.r0; / 插入插入 / if / ShellInsertvoid ShellSort (SqList &L, int dlta, int t) / 增量为增量为dlta 的希尔排序的希尔排序 for (k=0; k Ri+1.key,Ri.key Ri+1.key,则交换则交换RiRi和和Ri+1Ri+1的位置。第一趟全部比较完毕的位置。第一趟全部比较完毕后后RnRn是序列中最大的记录。是序列中最大的记录。 再从再从R1R1开始两两比较开始两两比较RiRi和和Ri+1 Ri+1 (i=1,2,.,n-2) (i=1,2,.,n-2) 的关键字的大小，若的关键字的大小，若R

19、i.key Ri+1.keyRi.key Ri+1.key则交换则交换RiRi和和Ri+1Ri+1的位置。第二趟全部比较完毕后的位置。第二趟全部比较完毕后Rn-1Rn-1是序是序列中次大记录。列中次大记录。 如此反复，进行如此反复，进行n-1n-1趟冒泡排序后所有待排序趟冒泡排序后所有待排序的的n n个记录序列按关键字有序。个记录序列按关键字有序。假设在排序过程中，记录序列R1.n的状态为：第 i 趟起泡排序无序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1无序序列R1.n-i有序序列 Rn-i+1.n比较相邻记录，将关关键字最大的记录交换键字最大的记录交换到 n-i+1 的位置上冒

20、泡排序示例冒泡排序示例初始状态 65 97 76 13 27 49 58 第1趟（j=16）65 76 13 27 49 58 97第2趟（j=15）65 13 27 49 58 76 97第3趟（j=14）13 27 49 58 65 76 97第4趟（j=13）13 27 49 58 65 76 97第5趟（j=12）13 27 49 58 65 76 97第6趟（j=1） 13 27 49 58 65 76 97设待排记录序列的关键字为设待排记录序列的关键字为(65,97,76,13,27,49,58)(65,97,76,13,27,49,58)冒泡排序每一趟执行后的序列状态如下：冒泡排

21、序每一趟执行后的序列状态如下：冒泡排序算法冒泡排序算法void bubblesort(Elem R , int n) / 设待排记录放在设待排记录放在R1R1到到RnRn中中 for(i=1;in;i+) for(j=1;jRj+1.key) Swap(Rj, Rj+1); /交换元素交换元素 冒泡排序的改进冒泡排序的改进按前面给出的算法，对具有个按前面给出的算法，对具有个n n记录的记录的待排序序列要执行待排序序列要执行n-1n-1趟冒泡排序。从上例趟冒泡排序。从上例中我们发现，执行到第中我们发现，执行到第3 3趟后记录序列已经趟后记录序列已经有序，后面的有序，后面的3 3趟冒泡趟冒泡“空跑

22、空跑”没有发没有发生交换。因此应该对算法加以改进：能生交换。因此应该对算法加以改进：能“记住记住”每趟加工时是否发生了每趟加工时是否发生了“交换交换”，若某一趟未发生若某一趟未发生“交换交换”，表示此时记录，表示此时记录序列已经有序，应结束排序过程。序列已经有序，应结束排序过程。改进的冒泡排序算法改进的冒泡排序算法void bubblesort(Elem R , int n) i=n; flag=1; while(i1)&flag); flag=0; for(j=1;jRj+1.key)Swap(Rj, Rj+1); flag=1; i -; 冒泡排序的进一步改进冒泡排序的进一步改进按

23、前面给出的改进算法，按前面给出的改进算法，一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。因此应该对算法进但并不是每趟都如此。因此应该对算法进一步加以改进：一步加以改进： “ “记住记住”本趟进行过交换本趟进行过交换的最后一个记录的位置，那么，在下一躺的最后一个记录的位置，那么，在下一躺起泡时，就可减少比较次数。起泡时，就可减少比较次数。注意注意: :2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key 1) / while / Bu

24、bbleSorti = n;i = lastExchangeIndex; / 本趟进行过交换的本趟进行过交换的 / 最后一个记录的位置最后一个记录的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /记下记下进行交换的记录位置进行交换的记录位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;时间分析时间分析: :最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况（关键字在

25、记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）： 需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini起泡排序总的起泡排序总的时间复杂度时间复杂度为为O(nO(n2 2) ) 目标：目标：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴关键字小于枢轴的记录均移动移动至该记录之前至该记录之前，反之，凡关键字大于枢轴关键字大于枢轴的记录均移动至该记录之后移动至该记录之后。致使一趟排序一趟排序之后，记录的无序序列Rs.t将分分割成两部分割成

26、两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 枢轴枢轴 (i+1jt)。二、一趟快速排序（一次划分）二、一趟快速排序（一次划分）52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 为枢轴为枢轴 将 Rhigh.key 和 枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字 将 Rlow.key 和 枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字high23low8014low52例如例如R052lowhighlowhighhighhigh 可见，经过“一次划分一次划分” ，将关键字序

27、列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t， 之后逐渐减小 high，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -hi

28、gh; RlowRhigh; while (lowhigh & Rlow.key=pivotkey) +low; RlowRhigh; return low; / 返回枢轴所在位置返回枢轴所在位置 / Partitionint Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 枢轴枢轴 while (lowhigh) while(low=pivotkey) - high; / 从右向左搜索从右向左搜索Rlow = Rhigh;while (lowhigh &

29、; Rlow.key=pivotkey) + low; / 从左向右搜索从左向右搜索Rhigh = Rlow;Rlow = R0; return low;三、快速排序三、快速排序 首先对无序的记录序列进行“一次划分一次划分”，之后分别分别对分割所得两个子序列“递归递归”进行进行快速排序快速排序。无 序 的 记 录 序 列无序记录子序列(1)无序子序列(2)枢轴枢轴一次划分分别进行快速排序void QSort (RedType & R, int s, int t ) / 对记录序列对记录序列Rs.t进行快速排序进行快速排序 if (s t-1) / 长度大于长度大于1 / QSort p

30、ivotloc = Partition(R, s, t); / 对对 Rs.t 进行一次划分进行一次划分 QSort(R, s, pivotloc-1); / 对低子序列递归排序，对低子序列递归排序，pivotloc是枢轴位置是枢轴位置 QSort(R, pivotloc+1, t); / 对高子序列递归排序对高子序列递归排序void QuickSort( SqList & L) / 对顺序表进行快速排序对顺序表进行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和 L.length

31、。四、快速排序的时间分析四、快速排序的时间分析假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间： 其中 Tpass(n)为对 n 个记录进行一次划分所需时间。 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)nkavgavgavgknTkTnCnnT1)() 1(1)(设 Tavg(1)b则可得结果：) 1ln() 1)(22()(nncbnTavg结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为： 若待排记录的初始状

32、态为按关键字有序若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。 为避免出现这种情况，需在进行一次划分之前，进行“予处理予处理”，即： 先对 R(s).key, R(t).key 和 R(s+t)/2.key，进行相互比较，然后取取关键字为 “三者之中三者之中”的记录为枢轴为枢轴记录。10.4 选选 择择 排排 序序简简 单单 选选 择择 排排 序序堆堆 排排 序序树树 形形 选选 择择 排排 序序一、简单选择排序一、简单选择排序基本思想基本思想： 一躺简单选择排序的操作为：通过一躺简单选择排序的操作为：通过n-in-i次关

33、键字间的比较，从次关键字间的比较，从n-i+1n-i+1个记录个记录中选出关键字最小的记录，并和第中选出关键字最小的记录，并和第i i（1in)1in)个记录交换之。个记录交换之。 对对L.r1.n中记录进行简单选择排中记录进行简单选择排序的算法为：序的算法为：令令i从从1至至n-1,进行进行n-1趟选趟选择操作。择操作。 假设排序过程中，待排记录序列的状态为：有序序列R1.i-1无序序列 Ri.n 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R1.i无序序列 Ri+1.n简单选择排序简单选择排序初始状态初始状态 2 7 2 4 3 1 第第1趟（趟（i=1）1 7 2 4 3 2第

34、第2趟（趟（i=2）1 2 7 4 3 2 第第3趟（趟（i=3）1 2 2 4 3 7第第4趟（趟（i=4）1 2 2 3 4 7 第第5趟（趟（i=5）1 2 2 3 4 7待排序记录序列的关键字序列为（待排序记录序列的关键字序列为（2 2，7 7，2 2，4 4，3 3，1 1）简单选择排序每一趟执行后的序列状态：简单选择排序每一趟执行后的序列状态：简单选择排序的算法描述如下：void SelectSort (Elem R, int n ) / 对记录序列对记录序列R1.n作简单选择排序。作简单选择排序。 for (i=1; in; +i) / 选择第选择第 i 小的记录，并交换到位小的

35、记录，并交换到位 / SelectSortj = SelectMinKey(R, i); / 在在 Ri.n 中选择关键字最小的记录中选择关键字最小的记录if (i!=j) RiRj; / 与第与第 i 个记录交换个记录交换时间性能分析时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数关键字间的比较次数 总计为：移动记录的次数移动记录的次数，最小值为 0, 最大值为3(n-1) 。2) 1()(11nninni其时间复杂度为其时间复杂度为O(nO(n2 2) )二、树形选择排序二、树形选择排序 树形选择排序树形选择排序又称又称锦标赛排序锦标赛排序，是，是一种按照锦标赛

36、的思想进行选择排序的一种按照锦标赛的思想进行选择排序的方法。方法。基本思想：基本思想： 首先对首先对n n个记录的关键字进行两两个记录的关键字进行两两比较，然后在其中比较，然后在其中n/2n/2个较小者之间再个较小者之间再进行两两比较，如此重复，直至选出最进行两两比较，如此重复，直至选出最小关键字的记录为止。小关键字的记录为止。384965977613274938651327381313选出选出最小关键字最小关键字13例：例： 49 38 65 97 76 13 27 493849659776274938657627382727 将叶结点中的最小关键字将叶结点中的最小关键字(13)改为最大改为

37、最大值，然后修改该叶子结点到根的路径上各值，然后修改该叶子结点到根的路径上各结点的关键字，则根结点的关键字即为次结点的关键字，则根结点的关键字即为次小关键字。由此选出小关键字。由此选出次小关键字次小关键字27。38496597764938657649384938 同理，可依次选出从小到大的所有关同理，可依次选出从小到大的所有关键字。居键字。居第三的关键字为第三的关键字为38。 树形选择排序的时间复杂度分析：树形选择排序的时间复杂度分析： 由于含由于含n个叶子结点的完全二叉树的深度个叶子结点的完全二叉树的深度为为 log2n +1次，则在树形选择排序中，除了最次，则在树形选择排序中，除了最小关键

38、字之外，每选择一个次小关键字仅需进小关键字之外，每选择一个次小关键字仅需进行行 log2n 次比较，因此，次比较，因此，树形选择排序的树形选择排序的时间时间复杂度复杂度为为O(nlog2n)。 这种排序方法尚有辅助存储空间较多，和这种排序方法尚有辅助存储空间较多，和“最大值最大值”进行多余的比较等特点。进行多余的比较等特点。 为了弥补这一缺点，可采用另一形式的选为了弥补这一缺点，可采用另一形式的选择排序择排序堆排序。堆排序。三、堆排序三、堆排序堆是满足下列性质的数列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr堆的定义堆的定义:12, 36, 27, 65, 40,

39、34, 98, 81, 73, 55, 49例如例如:是是小顶堆小顶堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆(小顶堆小顶堆)(大顶堆大顶堆)rir2i r2i+1 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不 堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序对记录序列进行排序的一种排序方法。列进行排序的一种排序方法。例如：例如：建大顶堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 1

40、2, 81, 49, 73, 36, 27, 40, 55, 64, 98 交换 98 和 12重新调整为大顶堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 经过筛选 如何由一个无序序列如何由一个无序序列“建堆建堆”？实现堆排序需要解决两个问题实现堆排序需要解决两个问题: 如何在输出堆顶元素之后，调如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？整剩余元素成为一个新的堆？定义堆类型为定义堆类型为:typedef SqList HeapType; / 堆采用顺序表表示之堆采用顺序表

41、表示之如何在输出堆顶元素之后，调整如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？剩余元素成为一个新的堆？ 假设在输出堆顶元素之后，以假设在输出堆顶元素之后，以堆中最后一个元素替代之，此时，堆中最后一个元素替代之，此时，根结点的左右子树均为堆，则仅需根结点的左右子树均为堆，则仅需自上至下进行调整即可。自堆顶至自上至下进行调整即可。自堆顶至叶子的调整过程为叶子的调整过程为“筛选筛选”。 所谓“筛选筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整调整”根根结点结点使整个二叉树也成为一个堆。堆堆筛选筛选98814973556412362740例如例如:是大顶堆是大顶堆12但在但在 98

42、98 和和 12 12 进行互换之后，它就进行互换之后，它就不不是堆了，是堆了，因此，需要对它进行“筛选”。98128173641298比较比较比较void HeapAdjust (RcdType &R, int s, int m) / 已知已知 Rs.m中记录的关键字除中记录的关键字除 Rs 之外均之外均 / 满足堆的特征，本函数自上而下调整满足堆的特征，本函数自上而下调整 Rs 的的 / 关键字，使关键字，使 Rs.m 也成为一个大顶堆也成为一个大顶堆 / HeapAdjustrc = Rs; / 暂存暂存 Rs for ( j=2*s; j= Rj.key ) break; /

43、再作再作“根根”和和“子树根子树根”之间的比之间的比较，较， / 若若“=”成立，则说明已找到成立，则说明已找到 rc 的插的插 / 入位置入位置 s ，不需要继续往下调整，不需要继续往下调整Rs = Rj; s = j; / 否则记录上移，尚需继续往下调整否则记录上移，尚需继续往下调整if ( jm & Rj.keyRj+1.key ) +j; / 左左/右右“子树根子树根”之间先进行相互比较之间先进行相互比较 / 令令 j 指示关键字较大记录的位置指示关键字较大记录的位置10.5 归归 并并 排排 序序 归并排序的过程基于下列基本基本思想思想进行： 将两个或两个以上的有序子序列 “

44、归并” 为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻位置相邻的记录有序子序列归并为一个一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列将有序的记录序列 SRi.m 和和 SRm+1.n / 归并为有序的记录序列归并为有序的记录序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n;

45、 +k) / 将将SR中记录由小到大地并入中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 将剩余的将剩余的 SRi.m 复制到复制到 TRif (j=n) TRk.n = SRj.n; / 将剩余的将剩余的 SRj.n 复制到复制到 TR归并排序的算法归并排序的算法 如果记录无序序列 Rs.t 的两部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。 由此，应该先分别对这两部

46、分进行 2-路归并排序。2-2-路归并排序的过程路归并排序的过程初始状态初始状态 25 57 4837 1292 86第趟归并第趟归并 25 57 37 48 12 92 86第趟归并第趟归并 25 374857 128692第趟归并第趟归并 12 253748578692待排记录序列为待排记录序列为(25,57,48,37,12,92,86)(25,57,48,37,12,92,86)路归并排序每一趟执行后的序列状态路归并排序每一趟执行后的序列状态: :void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 将将SRs.t 归并

47、排序为归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort m = (s+t)/2; / 将将SRs.t平分为平分为SRs.m和和SRm+1.tMsort (SR, TR2, s, m); / 递归地将递归地将SRs.m归并为有序的归并为有序的TR2s.mMsort (SR, TR2, m+1, t); /递归地递归地SRm+1.t归并为有序的归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将将TR2s.m和和TR2m+1.t归并到归并到TR1s.tvoid MergeSort (SqList &L) / 对

48、顺序表对顺序表 L 作作2-路归并排序路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort 容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。 基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序10.6 基基 数数 排排 序序一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1,Kid-1) ) 有序有序是

49、指： 其中其中: : K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足满足下列(词典词典)有序有序关系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) ) 实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法: :最低位优先最低位优先LSD法法最高位优先最高位优先MSD法 先对先对K0进行排序进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，.， 依次类推，直至最后直至最后对最次位关键字排序完成为止对

50、最次位关键字排序完成为止。最高位优先最高位优先MSD法 先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位直至对最主位关键字关键字 K0 排序完成为止排序完成为止。 排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。最低位优先最低位优先LSD法法例如例如: :学生记录含三个关键字:系别系别、班号班号和班内的序列号班内的序列号，其中以系别为最主位关键字。 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,20

51、2,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字假如多关键字的记录序列中，每个关键字的取值范围相同，则按的取值范围相同，则按LSD法进行排序时，可法进行排序时，可以采用以采用“分配分配- -收集收集”的方法，其好处是不需要的方法，其好处是不需要进行关键字间的比较。进行关键字间的比较。对于数字型或字符型的对于数字型或字符型的单关键字单关键字，可以，可以看看成成是由多个数位或多个字符构成的是由多个数位或多个字符构

52、成的多关键字多关键字，此时可以此时可以采用采用这种这种“分配分配- -收集收集”的办法的办法进行排进行排序序，称作基数排序法称作基数排序法。例如：例如：对下列这组关键字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数” 取值分别为 0, 1, , 9 “分配分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集收集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, , 9 “分配分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集收集” ” 在一起； 最后按其“百位数”重复一遍上述操作。在计算机上实现

53、基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： 待排序记录以指针相链，构成一个链表；待排序记录以指针相链，构成一个链表； “分配分配” ” 时，按当前时，按当前“关键字位关键字位”所取值，所取值，将记录分配到不同的将记录分配到不同的 “ “链队列链队列” ” 中，每个队列中记中，每个队列中记录的录的 “ “关键字位关键字位” ” 相同；相同； “收集收集”时，按当前关键字位取值从小到大时，按当前关键字位取值从小到大将各队列首尾相链成一个链表将各队列首尾相链成一个链表; ; 对每个关键字位均重复对每个关键字位均重复 2) 和和 3) 两步。两步。例如：p3

54、69367167239237138230139进行第一次分配进行第一次分配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138369239139369 239139138进行第二次分配进行第二次分配p230237138239139p230367167237138369239139f3 r3f6 r6230 237138239139367 167369367167369进行第二次收集 进行第三次收集之后便得到记录的有序序列进行第三次收集之后便得到记录的有序序列f1 r1p230237138239139367167369进行第三次分配进行第三次分配f2 r2f3 r3138 13