数据结构第7章

1、JYP1第第7 7章章 排序排序 数据元素之间的次序是一种重要的关系。本数据元素之间的次序是一种重要的关系。本章学习最典型的排序算法，特别讨论内、外排序章学习最典型的排序算法，特别讨论内、外排序的不同策略。还介绍排序结果的顺序化方法。的不同策略。还介绍排序结果的顺序化方法。JYP27.1 引言引言 在数据结构中，数据元素之间的次序是一种重要在数据结构中，数据元素之间的次序是一种重要的关系。的关系。 排序的应用：排序的应用： 查询结果需要按用户指定的属性排序。查询结果需要按用户指定的属性排序。 在已排序的数组中查找记录可最多用在已排序的数组中查找记录可最多用O(log2n)时时间。间。 核对两个

2、已按学号排序的学生记录表可用核对两个已按学号排序的学生记录表可用O(m+n)时间完成。时间完成。JYP3 记录记录 表示数据元素，具有一个或多个数据字表示数据元素，具有一个或多个数据字段。段。 关键字关键字 用于区分记录的字段。用于区分记录的字段。 表表 记录的有限集合。记录的有限集合。 给定一个记录表（给定一个记录表（R0, R1, , Rn-1），设记录），设记录Ri的的关键字值为关键字值为Ki。 关键字上存在一种关键字上存在一种次序关系次序关系 和一种和一种相等关系相等关系 =，使得对于任意两个关键字值使得对于任意两个关键字值x和和y，x = y，或，或x y，或或y x。关系。关系 满

3、足满足传递性传递性。用。用xy表示表示x = y或或x y。JYP4 排序排序 确定一种置换确定一种置换p，使得记录表（，使得记录表（Rp(0), Rp(1), , Rp(n-1)）的关键字满足性质）的关键字满足性质Kp(0)Kp(1)Kp(n-1)。 简单而言，排序就是按关键字非递减次序排列简单而言，排序就是按关键字非递减次序排列记录。记录。 如果在输入记录表中如果在输入记录表中Ki = Kj（i j），且在排），且在排序后序后Ri在在Rj之前，则称相应的排序方法是之前，则称相应的排序方法是稳定稳定的。的。否则就是不稳定的。否则就是不稳定的。 根据整个排序过程能否在内存中完成，可将排根据整个

4、排序过程能否在内存中完成，可将排序方法分为序方法分为内排序内排序和和外排序外排序。JYP5记录的类定义：记录的类定义：template class Element public: KeyType getKey( ) const return key;/ 取记录的关键字值 void setKey(KeyType k) key = k; / 修改记录的关键字 / 其它操作private: KeyType key;/ 关键字 / 其它字段 ; 假设在假设在KeyType被实例化时，相应实参类型的被实例化时，相应实参类型的、= 和和 = 等已定义。等已定义。JYP67.2 插入排序插入排序 插入排序插

5、入排序的基本步骤：将记录的基本步骤：将记录R插入一个已排好插入一个已排好序的记录序列序的记录序列R0, R1, , Ri（K0K1Ki）中，使）中，使得新的有得新的有i + 2个记录的序列也是排好序的。个记录的序列也是排好序的。 函数函数Insert实现了此步骤：实现了此步骤：template void insert(const Element e, Element *list, int i) / 将e插入已排好序的 list0,listi中， /使结果序列也排好序。list至少可容纳i+2个记录。 while (i = 0) & (e.getKey( ) listi.getKey(

6、) / 稳定 listi+1 = listi; i-; / listi+1 总是可用于存放记录 listi+1 = e;JYP7 插入排序从序列插入排序从序列R0开始，连续插入记录开始，连续插入记录R1, R2, , Rn-1。 n 个 记 录 可 以 通 过个 记 录 可 以 通 过 n 1 次 插 入 排 序 ， 如 函 数次 插 入 排 序 ， 如 函 数InsertionSort所示：所示：template void InsertionSort(Element *list, const int n) for (int j = 1; j n; j+) insert (listj, lis

7、t, j 1); JYP8 分析：分析：在最坏情况下，在最坏情况下，insert(e, list, i)在插入前要在插入前要作作i+1次比较。次比较。InsertionSort对对i = j1 = 0, 1, , n2调用调用insert，其最坏情况时间复杂性是，其最坏情况时间复杂性是O( ) = O(n2) 插入排序的实际时间与输入表的相对无序状态有插入排序的实际时间与输入表的相对无序状态有关。关。 记录记录Ri是是左出序左出序的当且仅当的当且仅当Ki 。20) 1(niimax0jijKmax0jijKJYP9 插入步骤中的循环只对左出序记录迭代。设插入步骤中的循环只对左出序记录迭代。设k

8、是是左出序记录个数，则插入排序的时间是左出序记录个数，则插入排序的时间是O(k+1)n)。当当k = 0，插入排序的时间为，插入排序的时间为O(n)。 这说明，当输入表中左出序记录很少时，插入排这说明，当输入表中左出序记录很少时，插入排序的实际性能十分理想。序的实际性能十分理想。max0jijKJYP10 例例7.1 设设n = 5，输入关键字为，输入关键字为5, 4, 3, 2, 1，则每次，则每次插入后表中记录的排列如下：插入后表中记录的排列如下：max0jijK 这时插入排序的性能达到最坏情况。这时插入排序的性能达到最坏情况。 JYP11 例例7.2 设设n = 5，输入关键字为，输入关

9、键字为2, 3, 4, 5, 1，则每次，则每次插入后表中记录的排列如下：插入后表中记录的排列如下：max0jijK 这时只有这时只有R4是左出序的。对于是左出序的。对于j=1, 2, 3，每次插入，每次插入的时间只需的时间只需O(1)；而对于；而对于j=4， 插入时间为插入时间为O(n)。 JYP12 插入排序是稳定的。插入排序是稳定的。 由于算法简单，对于较小的由于算法简单，对于较小的n（例如（例如n20），插），插入排序几乎是最快的。入排序几乎是最快的。 插入排序的改进：插入排序的改进： 1 二分插入排序二分插入排序 2 链表插入排序链表插入排序max0jijKJYP137.3 希尔希尔

10、排序排序 希尔排序希尔排序又称为又称为减少增量减少增量排序。以插入排序为基排序。以插入排序为基础，并利用插入排序在最好情况下的性能，改善整础，并利用插入排序在最好情况下的性能，改善整个排序的性能。个排序的性能。 观察输入序列观察输入序列 8, 7, 6, 5, 1, 2, 3, 4，其中左出序记录，其中左出序记录有有7个。个。 在插入排序中，首次在插入排序中，首次交换交换8和和7，只能减少，只能减少1个左出个左出序记录。序记录。 如果首次如果首次交换交换8和和1，则可减少，则可减少2个左出序记录。个左出序记录。JYP14 根据以上观察，可以根据以上观察，可以跨越式跨越式地交换记录：地交换记录：

11、 将整个记录表划分为若干个子表，其相邻记录相将整个记录表划分为若干个子表，其相邻记录相隔隔incr个位置，个位置，incr称为增量。称为增量。 利用插入排序对每个子表排序，以快速减少整个利用插入排序对每个子表排序，以快速减少整个表中的左出序记录。表中的左出序记录。 每完成一次上述过程，增量减少，继续利用插入每完成一次上述过程，增量减少，继续利用插入排序对按新增量划分的每个子表排序。排序对按新增量划分的每个子表排序。 最后一次增量必须为最后一次增量必须为1，这等同于普通的插入排序，这等同于普通的插入排序，但由于前面的预处理，整个记录表已基本有序，此但由于前面的预处理，整个记录表已基本有序，此次插

12、入排序有望快速完成。次插入排序有望快速完成。JYP15 例例7.3 设设n = 8，输入序列为，输入序列为8, 7, 6, 5, 1, 2, 3, 4，取，取incr = 4, 2, 1。处理过程如下所示：。处理过程如下所示：JYP16 增量的一个较有效的选择是从增量的一个较有效的选择是从 incr = n/3 + 1开始，开始，按按incr = incr/3 + 1减少增量。减少增量。 由于跨越式交换，希尔排序是不稳定的。由于跨越式交换，希尔排序是不稳定的。 为了反映增量，对为了反映增量，对InsertionSort及其调用的及其调用的insert作少量修改，得到用于希尔排序的作少量修改，得

13、到用于希尔排序的InsertionSort2以以及及insert2。JYP17template void insert2(const Element e, Element *list, int i, int incr) while (i =0) & (e.getKey( ) listi.getKey( ) listi+incr = listi; i -= incr;/ listi+incr总可以存放记录 listi+incr = e; template void InsertionSort2(Element *list, const int n, int incr, int start

14、) / start表示子表开始下标 for (int j = start; j n; j += incr) insert2 (listj + incr, list, j, incr); JYP18 进一步可得希尔排序函数进一步可得希尔排序函数ShellSort： template void ShellSort(Element *list, int n) int incr = n; do / 对每个增量 incr = incr/3 + 1; for (int start = 0; start 1); JYP19 大规模实验研究表明：大规模实验研究表明： 当记录个数当记录个数n很大时，希尔排序对记

15、录的移动次数很大时，希尔排序对记录的移动次数在在n1.25到到1.6n1.25的范围之内。的范围之内。 这比插入排序有实质性的改进。这比插入排序有实质性的改进。JYP207.4 快速快速排序排序 插入排序将控制当前插入的基准记录插入排序将控制当前插入的基准记录Ri插入相对插入相对于已排好序的子表于已排好序的子表 (R0, , Ri1) 的正确位置，而的正确位置，而快快速排序速排序将基准记录将基准记录Ri放在相对于整个记录表的正确放在相对于整个记录表的正确位置。位置。 设输入表为设输入表为 (Rleft, , Rright)，如果，如果Ri放在位置放在位置s(i)，则有则有KjKs(i)（j s

16、(i)）。）。JYP21 因此，根据因此，根据Ri的关键字大小，整个记录表被划分的关键字大小，整个记录表被划分为左子表为左子表 (Rleft, , Rs(i)1)和右子表和右子表 (Rs(i)+1, , Rright)，如下图所示：如下图所示： 由于左、右子表的记录分别在位置由于左、右子表的记录分别在位置s(i)的左、右的左、右边，可独立地对这两个子表排序。边，可独立地对这两个子表排序。JYP22 基准记录可任意选取，在此选第一个记录基准记录可任意选取，在此选第一个记录Rleft。 划分记录表：划分记录表： 从左到右扫描，找到关键字大于等于从左到右扫描，找到关键字大于等于Kleft的记录的记录

17、Ri； 从右到左扫描，找到关键字小于等于从右到左扫描，找到关键字小于等于Kleft的记录的记录Rj； 交换交换Ri和和Rj； 继续上述过程，直到继续上述过程，直到i，j错位。错位。JYP23算法算法QuickSort给出了实现细节：给出了实现细节：template void QuickSort (Element *list, const int left, const int right) / 排序listleft,listright，任选listleft为基准记 / 录，假设listleft.keylistright+1.key。 if (left right) int i = left,

18、j = right +1, pivot = listleft.getKey( ); do do i+; while (listi.getKey( ) pivot); if (i j) InterChange(list, i, j); while (i j);JYP24 InterChange(list, left, j); QuickSort(list, left, j 1);/ 排序左子表 QuickSort(list, j + 1, right);/ 排序右子表 其中函数其中函数InterChange(list, a, b)交换记录交换记录lista和和listb。 调用调用QuickSo

19、rt(list, 0, n 1)可对表可对表list的第的第0到第到第n 1个记录排序。个记录排序。 为了简化边界判断，假设记录为了简化边界判断，假设记录listn的关键字不的关键字不小于其余关键字。小于其余关键字。JYP25 例例7.4 设输入表记录的关键字为设输入表记录的关键字为(26, 5, 37, 1, 61, 11, 59, 15, 48, 19)，每次调用，每次调用QuickSort时记录表的状态时记录表的状态如下：如下：JYP26 分析：分析：用于划分记录表的时间是用于划分记录表的时间是O(n) ，设下面，设下面的的c都是常数。都是常数。 （1）用）用Tworst(n)表示快速排

20、序的最坏时间复杂性。表示快速排序的最坏时间复杂性。在最坏情况下，两个子表的长度分别为在最坏情况下，两个子表的长度分别为n1和和0，因，因此此 Tworst(n)cn + Tworst(n1) cn + c(n1) + Tworst(n2) c = cn(n+1)/2 = O(n2)nii1JYP27 （2）用）用Topt(n)表示快速排序的最佳时间复杂性。表示快速排序的最佳时间复杂性。在最佳情况下，两个子表的长度相同，每个子表的在最佳情况下，两个子表的长度相同，每个子表的长度最多是长度最多是n/2，因此，因此 Topt(n)cn + 2Topt(n/2) cn + 2(cn/2 + 2Topt

21、(n/4) 2cn + 4Topt(n/4) cn log2n + nTopt(1) = O(n log n) JYP28 （3）根据下面的引理）根据下面的引理7.1，快速排序的平均时间复，快速排序的平均时间复杂性也是杂性也是O(n log n)。而且，实验结果表明，快速排。而且，实验结果表明，快速排序的平均性能最好。序的平均性能最好。 引理引理7.1：设设Tavg(n)为快速排序的平均时间复杂性，为快速排序的平均时间复杂性，则存在常数则存在常数k，使得对于，使得对于n2，Tavg(n) knlogen 成成立。立。 证明：证明：在调用在调用QuickSort(list, 0, n 1)中，中

22、，K0被放被放在位置在位置j。两个子表的长度为。两个子表的长度为j和和n1j，相应的平均，相应的平均时间是时间是Tavg(j) + Tavg(n1j)。由于。由于j可按同等概率取可按同等概率取值值0到到n1，因此，因此 JYP29 Tavg(n)cn + = cn + ，n2(7.1) 设设Tavg(0)b和和Tavg(1)b，b为常数，为常数，k=2(b+c)。 对对n应用归纳法可证，应用归纳法可证，Tavg(n) knlogen（n 2）。）。)1()(101jnTjTavgnjavgn)(102jTnjavgnJYP30 当当n = 2，由，由(7.1)式可得：式可得：Tavg(2) 2

23、c + 2b 2kloge2。假设对于。假设对于2n m，Tavg(n)knlogen。则。则 Tavg(m)cm + = cm + cm + (7.2)(102jTmjavgm)(1224jTmjavgmmb1224logmjemkmbjjJYP31 由于由于jlogej是是j的递增函数，由的递增函数，由 (7.2) 式可得式可得 Tavg(m)cm + = cm + = cm + = kmlogem + (cm + )memkmbxdxx224log42log2422mmmmkmbe24logkmembmkm24kmmbJYP32 当当m2， cm + 0，所以，所以 Tavg(m)kml

24、ogem 24kmmbJYP33 对基本快速排序算法的改进：对基本快速排序算法的改进： 基准记录的选择：选当前记录表的第一、中间和基准记录的选择：选当前记录表的第一、中间和最后一个记录中关键字为中间值的记录。最后一个记录中关键字为中间值的记录。 用排序小记录表较快的方法如插入排序代替快速用排序小记录表较快的方法如插入排序代替快速排序。排序。 当需要排序的记录表小于一定长度时，快速排序当需要排序的记录表小于一定长度时，快速排序已使整个表接近于排好序，这时对整个记录表调用已使整个表接近于排好序，这时对整个记录表调用一次插入排序可使所有记录就序。一次插入排序可使所有记录就序。JYP34快速排序的最大

25、递归深度是快速排序的最大递归深度是n。递归排序两个子表。递归排序两个子表中较小的，再用循环代替第二个递归，可使递归深中较小的，再用循环代替第二个递归，可使递归深度最多是度最多是O(log n)，如函数，如函数ImpQuickSort所示：所示：template void ImpQuickSort (Element *list, const int left, const int right) / 排序listleft,listright，任选listleft为 / 基准记录，设listleft.key listright+1.key while (left right) int i = lef

26、t, j = right+1, pivot = listleft.getKey( ); do do i+; while (listi.getKey( ) pivot); if (i j) InterChange(list, i, j); while (i = j left) / 左子表较小 ImpQuickSort(list, left, j 1); left = j + 1; else / 右子表较小 ImpQuickSort(list, j + 1, right); right = j 1; JYP36 设设S(n)为为ImpQuickSort所需的栈空间，每层递归所需的栈空间，每层递归调

27、用需要栈空间为调用需要栈空间为c，则，则 S(n) c + S(n/2) 2c + S(n/4) clog2n + S(1) = O(log n)。 不难看出，快速排序是不稳定排序。不难看出，快速排序是不稳定排序。 JYP377.5 归并归并排序排序 7.5.1 迭代归并排序迭代归并排序 归并排序的基础是归并，即将两个已排序的表归归并排序的基础是归并，即将两个已排序的表归并为一个已排序的表。并为一个已排序的表。 在迭代归并排序中，需要归并的两个表：在迭代归并排序中，需要归并的两个表： (initListl, , initListm) (initListm+1, , initListn) 生成的

28、结果表是生成的结果表是 (mergedListl, , mergedListn)。JYP38 函数函数merge：template void merge(Element *initList, Element *mergedList, const int l, const int m, const int n) for (int i1 = l, iResult = l, i2 = m +1; i1 = m & i2 = n; iResult+) if ( initListi1.getKey ( ) m) for (int t = i2; t = n; t+) mergedListiRes

29、ult+t-i2 = initListt; else for (int t = i1; t = m; t+) mergedListiResult+t-i1 = initListt; 对对merge的分析：的分析：for循环最多迭代循环最多迭代nl+1次。循次。循环之外的环之外的if语句总共最多移动语句总共最多移动nl+1个记录。个记录。 因此，总时间是因此，总时间是O(nl+1)。 所需的辅助空间是所需的辅助空间是O(nl+1)。JYP40 迭代归并排序的基本思想：迭代归并排序的基本思想： 将有将有n个记录的输入表解释为个记录的输入表解释为n个已排序表，每个个已排序表，每个表的长度为表的长度为

30、1。 成对归并这些表，得到成对归并这些表，得到n/2个已排序表，每个表的个已排序表，每个表的长度为长度为2（如果（如果n是奇数，则最后一个表的长度为是奇数，则最后一个表的长度为1）。）。 再归并这再归并这n/2个表，如此继续直到只剩下一个已排个表，如此继续直到只剩下一个已排序的表。序的表。JYP41 例例7.5 对输入表对输入表 (26, 5, 77, 61, 11, 59, 15, 48, 19)，的，的每一遍扫描中归并子表的过程：每一遍扫描中归并子表的过程：JYP42 可见，需要对输入表进行多次归并扫描。设扫描可见，需要对输入表进行多次归并扫描。设扫描时输入表中已排序子表的长度为时输入表中

31、已排序子表的长度为len（最后一个子表（最后一个子表的长度可能小于的长度可能小于len），则经过一次归并扫描后已排），则经过一次归并扫描后已排序子表的长度变为序子表的长度变为2len，如下所示：，如下所示：JYP43 用用i作为扫描指针，指向需归并的两个子表的前一作为扫描指针，指向需归并的两个子表的前一个的第一记录，并随着归并的完成向右移动。个的第一记录，并随着归并的完成向右移动。 如果如果in2len，则至少还有两个长度都是，则至少还有两个长度都是len的子表的子表需要归并，否则需要作特殊边界处理。需要归并，否则需要作特殊边界处理。JYP44函数函数MergePass：template vo

32、id MergePass(Element *initList, Element *resultList, const int n, const int len) / 一遍归并扫描。将表initList的相邻子表归并到表resultList for (int i = 0; i = n 2len; i += 2len) merge(initList, resultList, i, i+len1, i+2len1); / 剩下的记录数 2len if (i+len1 n1) / 归并最后两个长短不一的子表 merge(initList, resultList, i, i+len1, n1); els

33、e for (int t = i; t = n1; t+) resultListt = initListt; / 复制最后一个子表JYP45函数函数MergeSort反复调用反复调用MergePass完成排序：完成排序：template void MergeSort(Element *list, const int n) Element *tempList = new Element n; for (int l = 1; l n; l* = 2) / l是当前被归并子表的长度 MergePass(list, tempList, n, l); l*=2; MergePass(tempList,

34、list, n, l); / 最后一遍可能只是复制 delete tempList;JYP46 对对MergeSort的分析：的分析：对输入表进行多次扫描。对输入表进行多次扫描。第第1遍归并长度为遍归并长度为1的表，第的表，第2遍归并长度为遍归并长度为2的表。的表。第第i遍扫描归并长度为遍扫描归并长度为2i-1的表。总共需要的表。总共需要 log2n 次扫次扫描。每遍扫描的时间为描。每遍扫描的时间为O(n)。 归并排序的总时间为归并排序的总时间为O(n log n)。 不难看出，归并排序是稳定排序。不难看出，归并排序是稳定排序。JYP477.5.2 递归递归归并归并排序排序 递归归并排序的基本

35、思想：递归归并排序的基本思想： 将记录表划分成大致等长的左、右子表。将记录表划分成大致等长的左、右子表。 递归排序这些子表。递归排序这些子表。 再归并已排序的子表，从而使整个记录表就序。再归并已排序的子表，从而使整个记录表就序。JYP48 例例7.6 对输入表对输入表 (26, 5, 77, 61, 11, 59, 15, 48, 19) 进进行递归归并排序过程中的子表划分：行递归归并排序过程中的子表划分：JYP49 将子表从一个数组归并到另一个数组需要复制数将子表从一个数组归并到另一个数组需要复制数据。采用链表表示可避免数据复制。据。采用链表表示可避免数据复制。 假设每个元素至少有两个字段：

36、假设每个元素至少有两个字段：link和和key，其结，其结构定义如下：构定义如下：template class Element private: KeyType key;/ 关键字 int link; / 其它字段public: Element( ) link = -1;/ -1表示空指针; JYP50 假设：假设： 所有访问所有访问Element私有数据成员的的函数已声明为私有数据成员的的函数已声明为Element的友元。的友元。 listi.key和和listi.link分别是记录分别是记录i的的key和和link字段字段的值（的值（0in1）。）。 初始时初始时listi.link =

37、1（0in1），即每个记录构），即每个记录构成一个只含其本身的链表。成一个只含其本身的链表。JYP51 函数函数ListMerge(list, start1, start2) 将两个由将两个由start1和和start2指向的按关键字非递减次序链接的链表归并为指向的按关键字非递减次序链接的链表归并为一个按关键字非递减次序链接的链表，并返回首记一个按关键字非递减次序链接的链表，并返回首记录指针：录指针：template int ListMerge(Element *list, const int start1, const int start2) / 将分别由start1和start2指向的已排

38、序链表归并为 / 一个已排序链表，并返回其首记录的下标。记录 / 之间通过整型下标链接。 int iResult, iStart, i1, i2; if (liststart1.key = liststart2.key) / 定位结果表的首记录 iStart = iResult = start1; i1 = liststart1.link; i2 = start2; JYP52else iStart = iResult = start2; i2 = liststart2.link; i1 = start1; while (i1 -1 & i2 -1) / 归并 if (listi1.k

39、ey = listi2.key) listiResult.link = i1; iResult = i1; i1 = listi1.link; else listiResult.link = i2; iResult = i2; i2 = listi2.link; if (i1= -1) listiResult.link = i2; / 链接剩余部分 else listiResult.link = i1; return iStart;JYP53 函数函数rMergeSort利用利用ListMerge实现递归归并排序，实现递归归并排序，并返回已排好序链表的首记录指针：并返回已排好序链表的首记录指针

40、：template int rMergeSort(Element *list, const int left, const int right) / 将listleft, , listright按key排序。返回已/ 排序链表的首记录下标。 if (left = right) return left;/ 最多只含一个记录 int mid = (left + right)/2; / 分别排序左、右半部分，并归并所得的两个已排序链表 return ListMerge(list, rMergeSort(list, left, mid), rMergeSort(list, mid+1, right);

41、 当需要对当需要对list0, , listn1排序时，可调用排序时，可调用rMergeSort(list, 0, n1)。此排序也是稳定的。此排序也是稳定的。JYP547.6 堆堆排序排序 堆排序只需要堆排序只需要O(1)的辅助空间，同时其最坏和平的辅助空间，同时其最坏和平均时间复杂性也都是均时间复杂性也都是O(n log n)。 堆排序通过最大堆的插入和删除操作实现排序：堆排序通过最大堆的插入和删除操作实现排序： 首先将首先将n个记录插入一个初始为空的堆，个记录插入一个初始为空的堆， 接着逐个从堆中取出记录。接着逐个从堆中取出记录。 然而，还可以通过函数然而，还可以通过函数adjust更快

42、地构建具有更快地构建具有n个个记录的堆。记录的堆。 给定一棵二叉树给定一棵二叉树T，其左、右子树都满足最大堆，其左、右子树都满足最大堆的性质，但其根结点却不一定满足，函数的性质，但其根结点却不一定满足，函数adjust调调整整T使得整个二叉树都满足最大堆性质。使得整个二叉树都满足最大堆性质。JYP55template void adjust (Element *tree, const int root, const int n) / 结点下标不大于n Element e = treeroot; int k = e.getKey( ); for (int j = 2*root; j = n; j

43、 *= 2) if (j n) / j一定有右兄弟 if (treej.getKey( ) = treej.getKey( ) break; / 如果k不小于左、右子女 / 中的较大者，则e可放在j的双亲处 treej/2 = treej; / 将第j个记录上移 treej/2 = e; 设以设以root为根的树深为为根的树深为d，其计算时间为，其计算时间为O(d)。JYP56 算法算法HeapSort首先利用函数首先利用函数adjust构建最大堆，构建最大堆，如下图所示：如下图所示：JYP57 接着对记录表接着对记录表list作作n 1遍处理，每次将当前最遍处理，每次将当前最大堆的第一个记录

44、与最后一个交换，并将当前最大大堆的第一个记录与最后一个交换，并将当前最大堆记录数减少堆记录数减少1，重新调整。，重新调整。 由于第一个记录的关键字总是堆中最大的，经过由于第一个记录的关键字总是堆中最大的，经过交换该记录一定是就序的。交换该记录一定是就序的。 调用调用HeapSort(list, n)即可对即可对list1, , listn排序。排序。 JYP58template void HeapSort (Element *list, const int n) / 按关/ 键字非递减次序排序list1, , listn for (int i = n /2; i = 1; i-) / 将lis

45、t转化为最大堆 adjust(list, i, n); for (i = n 1; i = 1; i-) / 排序list Element t = listi+1; listi+1 = list1; list1 = t; / 交换list1和listi+1 adjust(list, 1, i); / 重建堆 JYP59 例例7.7 用用HeapSort对对(26, 5, 77, 1, 61, 11, 59, 15, 48, 19)的排序过程：的排序过程：JYP60JYP61JYP62JYP63JYP64 分析：分析：设设2k1n 2k，则与记录表对应的完全二，则与记录表对应的完全二叉树有叉树有

46、k层，第层，第i层的结点数层的结点数2i1。第一个。第一个for循环对循环对每个有子女的结点调用每个有子女的结点调用adjust一次。该循环的时间一次。该循环的时间不大于各层结点数与该层结点可移动的最大距离的不大于各层结点数与该层结点可移动的最大距离的积之和，即积之和，即 第二个第二个for循环调用循环调用adjust共共n1次，最大深度为次，最大深度为 log2(n+1) 。 因此，堆排序的总计算时间是因此，堆排序的总计算时间是O(n log n)。 而且，只需要而且，只需要O(1)辅助空间。辅助空间。)(22/2/22)(211111111111nOniniiikkiiikikkiikki

47、iJYP657.7 基数基数排序排序 当当n个记录的关键字个记录的关键字listi.key（0in）的取值是）的取值是0到到n1范围内的整数时，可以用下列代码对其排序：范围内的整数时，可以用下列代码对其排序： for (int i = 0; i n; i+) resultlisti.key = listi; 这里用关键字值来确定记录在最终就序数组中的这里用关键字值来确定记录在最终就序数组中的位置。这就是最基本的位置。这就是最基本的箱排序箱排序。 其中，我们为其中，我们为n个关键字值安排个关键字值安排n个箱子，并根据个箱子，并根据关键字值将记录分配到对应的箱中。关键字值将记录分配到对应的箱中。

48、此方法效率极高，无论记录关键字的初始顺序如此方法效率极高，无论记录关键字的初始顺序如何，只需要何，只需要O(n) 时间即可完成排序。时间即可完成排序。JYP66 在实际应用中，一个箱子可以存放多个记录，同在实际应用中，一个箱子可以存放多个记录，同时关键字的取值范围不必与时关键字的取值范围不必与n直接关联。直接关联。 为了有效地利用箱排序的思想，可以将关键字解为了有效地利用箱排序的思想，可以将关键字解释为多个子关键字：释为多个子关键字：K0, , Kd1（K0是最高位，是最高位，Kd1是最低位）。是最低位）。 如果记录表如果记录表R0, , Rn-1中的任意两个记录中的任意两个记录Ri和和Rj（

49、0i j n）都满足）都满足 则称该记录表相对于关键字则称该记录表相对于关键字 (K0, , Kd1) 已排好序。已排好序。 ),.,(),.,(1010djjdiiKKKKJYP67 例如，排序例如，排序100张关键字值为张关键字值为0到到99的卡片可看成的卡片可看成对两个子关键字对两个子关键字K0和和K1的排序，其中的排序，其中K0对应十位，对应十位，K1对应个位。对应个位。 我们按最低位优先（简称我们按最低位优先（简称LSD）策略应用箱排序解）策略应用箱排序解决此问题：决此问题： 首先根据首先根据K1将卡片逐张分配到将卡片逐张分配到0号箱到号箱到9号箱中。号箱中。 接着，将接着，将8号箱

50、的卡片放在号箱的卡片放在9号箱的之前，号箱的之前，将，将0号箱的卡片放在号箱的卡片放在1号箱的之前。号箱的之前。 再根据再根据K0按照稳定排序的要求将卡片逐张分配到按照稳定排序的要求将卡片逐张分配到0号箱到号箱到9号箱中，按照从号箱中，按照从0到到9的箱号顺序收集即得的箱号顺序收集即得到已排序的卡片。到已排序的卡片。JYP68 可见，如果关键字是十进制数，可将其中的每个可见，如果关键字是十进制数，可将其中的每个十进制位看成一个子关键字，并按十进制位看成一个子关键字，并按LSD策略用策略用10个个箱子对每个子关键字进行箱排序。箱子对每个子关键字进行箱排序。 一般地，在一般地，在基数排序基数排序中

51、，用基数中，用基数r分解关键字。分解关键字。 当当r = 10，则得到上述十进制分解。，则得到上述十进制分解。 如果关键字是长度为如果关键字是长度为d的小写英文标识符，则可的小写英文标识符，则可分解为分解为d个子关键字个子关键字 (K0, , Kd1)，其中，其中，Ki a, b, , z （0i d），），r = 26。 基数基数r排序需要排序需要r个箱子。个箱子。JYP69 假设记录表是假设记录表是R0, , Rn-1。关键字用基数。关键字用基数r分解，分解，每个分解为每个分解为d位，每位的取值是位，每位的取值是0到到r 1，则需要，则需要r个个箱子。箱子。 记录元素的类定义如下：记录元素

52、的类定义如下：class Element public:private: int keyd;/ 关键字数组，d是常数 / 其它字段 int link;JYP70 每个箱子中的记录链接成队列，每个箱子中的记录链接成队列，fi和和ei（0i r）分别指向第）分别指向第i个箱子的首、尾记录。个箱子的首、尾记录。 函数函数RadixSort给出了用给出了用LSD策略实现基数策略实现基数r排序的排序的细节：细节：int RadixSort (Element *list, const int d, const int n) / 按关键字key0,keyd-1排序(list0,listn-1)，/ 0key

53、i radix，radix是常数 int fradix, eradix; / radix个队列的首、尾指针 for (int i = 0; i = 0; i-) / 对keyi排序 for (int j = 0; j r; j+) fj = -1; / 初始化所有箱子 for ( ;current -1 ;current = listcurrent.link) /分配记录 int k = listcurrent.keyi; if (fk = -1) fk = current; else listek.link = current; ek = current; for (j = 0; fj =

54、-1; j+);/ 找到第一个非空队列 current = fj; int last = ej; for (int k = j+1; k r; k+) / 拼接剩余队列 if (fk -1) listlast.link = fk; last = ek; listlast.link = -1; / for (i = d -1; i = 0; i-) 结束 return f0; / 返回已就序链表的第一个记录下标JYP72 分析：分析：RadixSort对数据作对数据作d遍扫描，每遍扫描用遍扫描，每遍扫描用O(n+r) 时间，总计算时间是时间，总计算时间是O(d(n+r)。 例例7.8 设需要排序

55、的设需要排序的10个数的取值范围是个数的取值范围是0, 999。数的每一位作为一个子关键字，数的每一位作为一个子关键字，d =3，r =10。排序。排序过程如后面两页所示。过程如后面两页所示。JYP73JYP74JYP75JYP767.8 基于链表和映射表排序结果的顺序化基于链表和映射表排序结果的顺序化 对于基于链表的排序结果，有时需要按次序就地对于基于链表的排序结果，有时需要按次序就地重新排列，使它们在物理上也是顺序的。重新排列，使它们在物理上也是顺序的。 设记录表设记录表R0, , Rn-1经排序后的结果是一个按关经排序后的结果是一个按关键字非递减次序链接的链表，且键字非递减次序链接的链表

56、，且first是链表的首记是链表的首记录指针。录指针。 将记录将记录R0和和Rfirst交换。如果交换。如果first 0，则表中应有，则表中应有一个记录一个记录Rx，其，其link字段值为字段值为0。如果能够修改。如果能够修改Rx的的link字段，使其指向原位于字段，使其指向原位于R0的记录的新位置的记录的新位置first，则剩余记录则剩余记录R1, , Rn-1也是按关键字非递减次序链也是按关键字非递减次序链接的。接的。JYP77 但在单链表中，我们无法快速确定结点但在单链表中，我们无法快速确定结点R0的前驱的前驱Rx。于是可将。于是可将R0的的link字段设置为字段设置为first，表示

57、原位，表示原位于于R0的记录已移到的记录已移到Rfirst。 这样，这样，R0还作为还作为R1, , Rn-1链表中的链表中的虚拟结点虚拟结点。借助此虚拟结点，我们可找到剩余记录链表的首结借助此虚拟结点，我们可找到剩余记录链表的首结点。点。 重复上述过程重复上述过程n1次即可完成重新排列。次即可完成重新排列。 一般地，设记录表一般地，设记录表R0, , Ri-1已在物理上按序排已在物理上按序排列，列，Rfirst是剩余记录是剩余记录Ri, , Rn-1链表的首记录，记录链表的首记录，记录Ri和和Rfirst交换后，将新交换后，将新Ri记录的记录的link字段设置为字段设置为first，表示原位

58、于表示原位于Ri的记录已移到的记录已移到Rfirst。JYP78 同时，注意到作为剩余记录同时，注意到作为剩余记录Ri, , Rn-1链表的首链表的首记录下标的记录下标的first总是大于或等于总是大于或等于i，我们可以经过虚，我们可以经过虚拟结点，找到剩余记录链表的首记录下标。拟结点，找到剩余记录链表的首记录下标。 函数函数list实现了上述方法：实现了上述方法：template void list(Element *list, const int n, int first) / 重新排序由first指向的链表中的记录，使list0,listn-1 / 中的关键字按非递减次序排列 for (

59、int i = 0; i n 1; i+) / 找到应放到位置i的记录。由于位置0, 1, , i-1的记录已 / 就位，该记录下标一定i while (first i) first = listfirst.link;/ 经过虚拟结点JYP79 int q = listfirst.link; / listq 是按非递减次序的下一个/ 记录，可能是虚拟记录 if (first != i) / 交换listi 和listfirst，并将listi.link/ 设置为原listi的新位置 Element t = listi; listi = listfirst; listfirst = t; lis

60、ti.link = first; first = q; JYP80 例例7.9 对对 (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 进行链进行链表排序后，所得链表如下所示：表排序后，所得链表如下所示：JYP81 list的的for循环每次迭代后记录表的状态如下，变循环每次迭代后记录表的状态如下，变化用粗体字表示，虚拟结点的化用粗体字表示，虚拟结点的link字段用带下划线字段用带下划线的字体表示：的字体表示：JYP82JYP83JYP84JYP85JYP86 对对list的分析：的分析：设有设有n个记录，个记录，for循环迭代循环迭代n1次。次。每次最多交换每次最多交换2个记录，需要个记录，需