数据结构：第10章内排序

1、第第1010章章 内内 排排 序序10.6 10.6 基数排序基数排序本章小结本章小结 10.1 10.1 排序的基本概念排序的基本概念10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.7 10.7 各种内排序方法的比较和选择各种内排序方法的比较和选择10.1 10.1 排序的基本概念排序的基本概念 所谓排序所谓排序,就是要整理表中的记录就是要整理表中的记录,使之按关键字使之按关键字递增递增(或递减或递减)有序排列。其确切定义如下：有序排列。其确切定义如下： 输入：输入：n个记录个记录,R0,R

2、1,Rn-1,其相应的关键字分别为其相应的关键字分别为k0,k1,kn-1。 输出：输出：Ri0,Ri1,Rin-1,使得使得ki0ki1kin-1(或或ki0ki1kin-1)。 当待排序记录的关键字均不相同时当待排序记录的关键字均不相同时, ,排序的结果排序的结果是惟一的是惟一的, ,否则排序的结果不一定惟一。如果待排序否则排序的结果不一定惟一。如果待排序的表中的表中, ,存在有多个关键字相同的记录存在有多个关键字相同的记录, ,经过排序后经过排序后这些具有相同关键字的记录之间的相对次序保持不这些具有相同关键字的记录之间的相对次序保持不变变, ,则称这种则称这种排序方法是稳定排序方法是稳定

3、的；反之的；反之, ,若具有相同若具有相同关键字的记录之间的相对次序发生变化关键字的记录之间的相对次序发生变化, ,则称这种则称这种排排序方法是不稳定序方法是不稳定的。的。 在排序过程中在排序过程中, ,若整个表都是放在内存中处理若整个表都是放在内存中处理, ,排序时不涉及数据的内、外存交换排序时不涉及数据的内、外存交换, ,则称之为则称之为内排序内排序；反之反之, ,若排序过程中要进行数据的内、外存交换若排序过程中要进行数据的内、外存交换, ,则则称之为称之为外排序外排序。 待排序的顺序表类型的类型定义如下：待排序的顺序表类型的类型定义如下： typedef int KeyType; /*定

4、义关键字类型定义关键字类型*/ typedef struct /*记录类型记录类型*/ KeyType key; /*关键字项关键字项*/ InfoType data; /*其他数据项其他数据项,类型为类型为 InfoType*/ RecType; /*排序的记录类型定义排序的记录类型定义*/ RecType RN; 数组数组R中存放着待排序的记录中存放着待排序的记录10.2 10.2 插入排序插入排序 插入排序的基本思想是：每次将一个待排序的记插入排序的基本思想是：每次将一个待排序的记录录, ,按其关键字大小插入到前面已经排好序的子表中按其关键字大小插入到前面已经排好序的子表中的适当位置的适

5、当位置, ,直到全部记录插入完成为止。直到全部记录插入完成为止。 三种插入排序方法：三种插入排序方法： (1)(1)直接插入排序直接插入排序 (2)(2)二分插入排序二分插入排序 (2)(2)希尔排序。希尔排序。10.2.1 10.2.1 直接插入排序直接插入排序 假设待排序的记录存放在数组假设待排序的记录存放在数组R0.n-1中中,排序过排序过程的某一中间时刻程的某一中间时刻,R被划分成两个子区间被划分成两个子区间R0.i-1和和Ri.n-1,其中：前一个子区间是已排好序的有序区其中：前一个子区间是已排好序的有序区,后后一个子区间则是当前未排序的部分一个子区间则是当前未排序的部分,不妨称其为

6、无序不妨称其为无序区。区。直接插入排序的基本操作是将当前无序区的第直接插入排序的基本操作是将当前无序区的第1个记录个记录Ri插入到有序区插入到有序区R0.i-1中适当的位置上中适当的位置上,使使R0.i变为新的有序区。变为新的有序区。这种方法通常称为增量法这种方法通常称为增量法,因因为它每次使有序区增加为它每次使有序区增加1个记录。个记录。例例49 38 65 97 76 13 27i=2 (38 49) 65 97 76 13 27i=3 (38 49 65) 97 76 13 27i=4 (38 49 65 97) 76 13 27i=5 (38 49 65 76 97) 13 27i=6

7、 (13 38 49 65 76 97) 27i=1 ( ) (13 38 49 65 76 97) 27jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果： 0 1 2 3 4 5 6void InsertSort(RecType R , int n) /*对对R0.n-1按递增有序进按递增有序进行直接插入排序行直接插入排序*/ int i,j;RecType temp; for (i=1;i=0 & temp.keyRj.key) Rj+1=Rj; /*将关键字大于将关键字大于Ri.key的记录后移的记录后移*/ j-; Rj+1=temp;

8、 /*在在j+1处插入处插入Ri*/ 10.2.2 二分插入排序二分插入排序由于插入排序是在一个有序表中进行查找和插入，若由于插入排序是在一个有序表中进行查找和插入，若查找时采用二分查找方法，则直接插入排序就变成了查找时采用二分查找方法，则直接插入排序就变成了二分插入排序。二分插入排序。void InsertSort1(RecType R , int n) int i, j, low, high, mid; RecType temp; for (i=1;in;i+) temp=Ri; low=0; high=i-1; while (low=high) mid=(low+high)/2; if

9、(temp.key=high+1; j-) Rj+1=Rj; /*将关键字大于将关键字大于Ri.key的记录后移的记录后移*/ Rhigh+1=temp; 10.2.3 10.2.3 希尔排序希尔排序 希尔排序也是一种插入排序方法希尔排序也是一种插入排序方法,实际上是一种分实际上是一种分组插入方法。其基本思想是：先取定一个小于组插入方法。其基本思想是：先取定一个小于n的整的整数数d1作为第一个增量作为第一个增量,把表的全部记录分成把表的全部记录分成d1个组个组,所所有距离为有距离为d1的倍数的记录放在同一个组中的倍数的记录放在同一个组中,在各组内进在各组内进行直接插入排序；然后行直接插入排序；

10、然后,取第二个增量取第二个增量d2(d1),重复上重复上述的分组和排序述的分组和排序,直至所取的增量直至所取的增量dt=1(dtdt -1d20) for (i=d;i=0 & Rj.keyRj+d.key) temp=Rj; /*Rj与与Rj+d交换交换*/ Rj=Rj+d; Rj+d=temp; j=j-d; d=d/2; /*递减增量递减增量d*/ 例例10.2 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用希尔排序方法进行排。说明采用希尔排序方法进行排序的过程序的过程。 9 8 7 6 5 4 3 2

11、1 0 初始状态初始状态 (连线部分为下一趟作准备连线部分为下一趟作准备) 4 3 2 1 0 9 8 7 6 5 d=5 (d=5 执行结果执行结果) 0 1 2 3 4 5 6 7 8 9 d=2 (d=2 执行结果执行结果) 0 1 2 3 4 5 6 7 8 9 d=1 (d=1 执行结果执行结果) 子序列的构成不是简单的子序列的构成不是简单的“逐段分割逐段分割”，而是，而是将相隔某个增量的记录组成一个子序列将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度希尔排序可提高排序速度分组后分组后n n值减小，值减小，n n更小，而更小，而T(nT(n)=O(n)=O(n),),所以所

12、以T(nT(n) )从总体上看是减小了从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一关键字较小的记录跳跃式前移，在进行最后一趟增量为趟增量为1 1的插入排序时，序列已基本有序的插入排序时，序列已基本有序平均时间复杂度：平均时间复杂度：与每趟的增量有关与每趟的增量有关如：如： dtdt=n/2,n/4,=n/2,n/4,1 O(n,1 O(n1.51.5) )希尔排序是不稳定的希尔排序是不稳定的最后一个增量值必须为最后一个增量值必须为1 1希尔排序特点希尔排序特点10.3 10.3 交换排序交换排序 交换排序的基本思想：两两比较待排序记录的关交换排序的基本思想：两两比较待排序记录的关

13、键字键字,发现两个记录的次序相反时即进行交换发现两个记录的次序相反时即进行交换,直到直到没有反序的记录为止。没有反序的记录为止。 两种交换排序两种交换排序: (1)冒泡排序冒泡排序 (2)快速排序快速排序10.3.1 10.3.1 冒泡排序冒泡排序 冒泡排序的基本思想是：冒泡排序的基本思想是： 通过无序区中通过无序区中相邻记录关键字间的比较和位置的相邻记录关键字间的比较和位置的交换交换,使关键字最小的记录如气泡一般逐渐往上使关键字最小的记录如气泡一般逐渐往上“漂漂浮浮”直至直至“水面水面”。整个算法是从最下面的记录开。整个算法是从最下面的记录开始始,对每两个相邻的关键字进行比较对每两个相邻的关

14、键字进行比较,且使关键字较小且使关键字较小的记录换至关键字较大的记录之上的记录换至关键字较大的记录之上,使得经过一趟冒使得经过一趟冒泡排序后泡排序后,关键字最小的记录到达最上端关键字最小的记录到达最上端,接着接着,再在剩再在剩下的记录中找关键字次小的记录下的记录中找关键字次小的记录,并把它换在第二个并把它换在第二个位置上。依次类推位置上。依次类推,一直到所有记录都有序为止。一直到所有记录都有序为止。例例49 38 65 97 76 13 27 30 初始关键字初始关键字13 27 49 38 65 97 76 30 第二趟第二趟13 27 30 49 38 65 97 76 第三趟第三趟13

15、27 30 38 49 65 76 97 第四趟第四趟1 2 3 4 5 6 7 8从下往上扫描从下往上扫描13 49 38 65 97 76 27 30 第一趟第一趟void BubbleSort(RecType R,int n) int i,j;RecType temp; for (i=0;ii;j-) /*比较找本趟最小关键字的记录比较找本趟最小关键字的记录*/ if (Rj.keyRj-1.key) / 相邻记录的比较相邻记录的比较 temp=Rj; /*Rj与与Rj-1进行交换进行交换*/ Rj=Rj-1; Rj-1=temp; 例例10.3 设待排序的表有设待排序的表有10个记录个

16、记录,其关键字分别其关键字分别为为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法进行。说明采用冒泡排序方法进行排序的过程。排序的过程。 初始关键字初始关键字 9 8 7 6 5 4 3 2 1 0 i=0 0 9 8 7 6 5 4 3 2 1 i=1 0 1 9 8 7 6 5 4 3 2 i=2 0 1 2 9 8 7 6 5 4 3 i=3 0 1 2 3 9 8 7 6 5 4 i=4 0 1 2 3 4 9 8 7 6 5 i=5 0 1 2 3 4 5 9 8 7 6 i=6 0 1 2 3 4 5 6 9 8 7 i=7 0 1 2 3 4 5 6 7 9 8 i=

17、8 0 1 2 3 4 5 6 7 8 9 在有些情况下在有些情况下, ,在第在第i(ii(in-1)n-1)趟时已排好序了趟时已排好序了, ,但但仍执行后面几趟的比较。实际上仍执行后面几趟的比较。实际上, ,一旦算法中某一趟比一旦算法中某一趟比较时不出现记录交换较时不出现记录交换, ,说明已排好序了说明已排好序了, ,就可以结束本就可以结束本算法。为此算法。为此, ,改进冒泡排序算法如下：改进冒泡排序算法如下： void BubbleSort(RecType R,int n) int i, j, exchange; RecType temp; for (i=0;ii;j-) /*比较比较,找

18、出最小关键字的记录找出最小关键字的记录*/ if (Rj.keyRj-1.key) temp=Rj; Rj=Rj-1;Rj-1=temp; exchange=1; if (exchange=0) return; /*中途结束算法中途结束算法*/ 空间复杂度：S(n)=O(1)算法评价算法评价时间复杂度时间复杂度最好情况（正序）：只需一趟扫描即可最好情况（正序）：只需一趟扫描即可比较次数：比较次数：n-1移动次数：移动次数：0最坏情况（逆序）最坏情况（逆序）比较次数：比较次数：)(21)(211nninni移动次数：移动次数：)(23)(321nninniT(n)=O(n)起泡排序：起泡排序：比

19、较和交换在相邻单元中进行，移动幅度仅比较和交换在相邻单元中进行，移动幅度仅一个单元，致使比较和移动次数较多；一个单元，致使比较和移动次数较多；每经过一趟起泡，无序序列的长度只缩小每经过一趟起泡，无序序列的长度只缩小1。设想：设想：若能在经过一趟排序，使无序若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序列的长度缩小一半，则必能加快排序的速度。序的速度。10.3.2 10.3.2 快速排序快速排序 快速排序是由冒泡排序改进而得的快速排序是由冒泡排序改进而得的, ,它的基本思想它的基本思想是：是：在待排序的在待排序的n n个记录中任取一个记录个记录中任取一个记录( (通常取第一通常取第

20、一个记录，称为个记录，称为基准记录基准记录),),把该记录放入适当位置后把该记录放入适当位置后, ,数据序列被此记录划分成两部分。所有关键字比该记数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分录关键字小的记录放置在前一部分, ,所有比它大的记所有比它大的记录放置在后一部分录放置在后一部分, ,并把该记录排在这两部分的中间并把该记录排在这两部分的中间( (称为该记录归位称为该记录归位),),这个过程称作一趟快速排序。之这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程后对所有的两部分分别重复上述过程, ,直至每部分内直至每部分内只有一个记录为止。简而言之只

21、有一个记录为止。简而言之, ,每趟使表的第一个元每趟使表的第一个元素放入适当位置素放入适当位置, ,将表一分为二将表一分为二, ,对子表按递归方式继对子表按递归方式继续这种划分续这种划分, ,直至划分的子表长为直至划分的子表长为1 1。快速排序过程快速排序过程例如例如:初始关键字序列初始关键字序列 5，6，3，1，2，7R : 0 1 2 3 4 5 选第一个元素为基准元素选第一个元素为基准元素第一趟快速排序：第一趟快速排序：（2，1，3），5，（6，7）第二趟快速排序：第二趟快速排序：（1），2，（3），5，6，（7）i:基准位置基准位置0 . i-1i+1. n-1i结束条件：待排区间只有

22、一个记录或无记录结束条件：待排区间只有一个记录或无记录R : 0 1 2 3 4 5 一次划分一次划分 初始关键字： 49 38 65 97 76 13 27 50 ij基准元素temp=49ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij调整过程中的基准位置并不重要，因此，为了减少记录的移动次数，应先将基准记录“移出”，待求得基准记录应在的位置之后(此时i=j

23、),再将基准记录归位。一趟划分实现过程void QuickSort(RecType R , int s, int t) /*对对Rs至至Rt的元素进行快速排序的元素进行快速排序*/ int i=s,j=t; RecType temp; if (si & Rj.keytemp.key) j-; if (ij) /*表示找到这样的表示找到这样的Rj,Ri、Rj交换交换*/ Ri=Rj; i+; while (ij & Ri.keytemp.key) i+; if (ij) /*表示找到这样的表示找到这样的Ri,Ri、Rj交换交换*/ Rj=Ri; j-; Ri=temp; Quic

24、kSort(R,s,i-1); /*对左区间递归排序对左区间递归排序*/ QuickSort(R,i+1,t); /*对右区间递归排序对右区间递归排序*/ 划分划分 例例10.4 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用快速排序方法进行排序。说明采用快速排序方法进行排序的过程。的过程。 初始关键字初始关键字 6 8 7 9 0 1 3 2 4 5 5 4 2 3 0 1 6 9 7 8 1 4 2 3 0 5 6 9 7 8 0 1 2 3 4 5 6 9 7 8 0 1 2 3 4 5 6 9 7 8 0 1

25、2 3 4 5 6 9 7 8 0 1 2 3 4 5 6 9 7 8 0 1 2 3 4 5 6 8 7 9 0 1 2 3 4 5 6 7 8 9 算法评价算法评价时间复杂度时间复杂度最好情况（每次总是选到中间值作基准）最好情况（每次总是选到中间值作基准）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素最坏情况（每次总是选到最小或最大元素作作基准基准）T(n)=O(n)空间复杂度：需栈空间以实现递归空间复杂度：需栈空间以实现递归最坏情况：最坏情况：S(n)=O(n)一般情况：一般情况：S(n)=O(log2n)平均：平均：T(n)=O(nlog2n)10.4 选择排序选择排

26、序 选择排序的基本思想是：每一趟从待排序的记录选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录中选出关键字最小的记录,顺序放在已排好序的子表顺序放在已排好序的子表的最后的最后,直到全部记录排序完毕。直到全部记录排序完毕。 两种选择排序方法：两种选择排序方法： (1)直接选择排序直接选择排序(或称简单选择排序或称简单选择排序) (2)堆排序堆排序10.4.1 10.4.1 直接选择排序直接选择排序 直接选择排序的基本思想是：直接选择排序的基本思想是：第第i趟排序开始时趟排序开始时,当前有序区和无序区分别为当前有序区和无序区分别为R0.i-1和和Ri.n-1(0in-1),该趟排序

27、则是从当前无序区中选出关键字最小该趟排序则是从当前无序区中选出关键字最小的记录的记录Rk,将它与无序区的第将它与无序区的第1个记录个记录Ri交换交换,使使R0.i和和Ri+1.n-1分别变为新的有序区和新的无序分别变为新的有序区和新的无序区。区。 因为每趟排序均使有序区中增加了一个记录因为每趟排序均使有序区中增加了一个记录,且且有序区中的记录关键字均不大于无序区中记录的关有序区中的记录关键字均不大于无序区中记录的关键字键字,即第即第i趟排序之后趟排序之后R0.i的所有关键字小于等于的所有关键字小于等于Ri+1.n-1中的所有关键字中的所有关键字,所以进行所以进行n-1趟排序之后趟排序之后有有R

28、0.n-2 的所有关键字小于等于的所有关键字小于等于Rn-1.key,也就是也就是说说,经过经过n-1趟排序之后趟排序之后,整个表整个表R0.n-1递增有序递增有序。例例初始初始： 49 38 65 97 76 13 27 kjjjjjjkki=01349一趟：一趟： 13 38 65 97 76 49 27 i=1kkjjjjj2738二趟：二趟： 13 27 65 97 76 49 38 三趟：三趟： 13 27 38 97 76 49 65 四趟：四趟： 13 27 38 49 76 97 65 五趟：五趟： 13 27 38 49 65 97 76 六趟：六趟： 13 27 38 49

29、 65 76 97 排序结束：排序结束： 13 27 38 49 65 76 97实现过程实现过程void SelectSort(RecType R,int n) int i,j,k; RecType temp; for (i=0;in-1;i+) /*做第做第i趟排序趟排序*/ k=i;for (j=i+1;jn;j+) /*在在i.n-1中选中选key最小的最小的Rk */ if (Rj.keyRk.key) k=j; /*k记下的最小关键字所在的位置记下的最小关键字所在的位置*/ if (k!=i) /*交换交换Ri和和Rk */ temp=Ri; Ri=Rk; Rk=temp; 例例1

30、0.5 设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用直接选择排序方法进行。说明采用直接选择排序方法进行排序的过程。排序的过程。 初始关键字初始关键字 6 8 7 9 0 1 3 2 4 5 i=0 0 8 7 9 6 1 3 2 4 5 i=1 0 1 7 9 6 8 3 2 4 5 i=2 0 1 2 9 6 8 3 7 4 5 i=3 0 1 2 3 6 8 9 7 4 5 i=4 0 1 2 3 4 8 9 7 6 5 i=5 0 1 2 3 4 5 9 7 6 8 i=6 0 1 2 3 4 5 6 7 9

31、8 i=7 0 1 2 3 4 5 6 7 9 8 i=8 0 1 2 3 4 5 6 7 8 9 算法评价时间复杂度记录移动次数最好情况：0 (已正序的纪录不用移动)最坏情况：3(n-1) 每趟均需交换比较次数：)(21)(211nninni空间复杂度：S(n)=O(1)T(n)=O(n)10.4.2 10.4.2 堆排序堆排序 堆排序是一树形选择排序堆排序是一树形选择排序,它的特点是它的特点是,在排序过程在排序过程中中,将将R1.n看成是一棵完全二叉树的顺序存储结构看成是一棵完全二叉树的顺序存储结构,利利用完全二叉树中双亲结点和孩子结点之间的内在关系用完全二叉树中双亲结点和孩子结点之间的内

32、在关系,在当前无序区中选择关键字最大在当前无序区中选择关键字最大(或最小或最小)的记录。的记录。 堆的定义堆的定义: 堆是满足下列性质的数列堆是满足下列性质的数列k1,k2, ，kn： 221iiiikkkk或若将此数列看成是一棵顺序存储的完全二叉树若将此数列看成是一棵顺序存储的完全二叉树:则堆或是空树或是满足下列特性的完全二叉树：则堆或是空树或是满足下列特性的完全二叉树：根结点的值小于根结点的值小于(或大于或大于)左左/右子树根结点的值右子树根结点的值。分别称作分别称作小根堆或大根堆小根堆或大根堆。221iiiikkkk例例 （96，83，27，38，11，9） 例例 （13，38，27，5

33、0，76，65，49，97）962791138831327384965765097堆顶元素堆顶元素k1k1必为序列中必为序列中n n个元素的最小值或最大值个元素的最小值或最大值96 83 27 38 119012345696279113883初始大根堆初始大根堆存储结构存储结构内存中内存中962791138839279611388383279611389832796119381127968393811279683938382796839119279683381127996833811调整实现过程调整实现过程 将根结点值与左、右子树的根结点值进行比将根结点值与左、右子树的根结点值进行比较，并与其

34、中大者进行交换；较，并与其中大者进行交换； 重复上述操作，直至叶子结点；重复上述操作，直至叶子结点； 得到新大根堆；得到新大根堆；27996833811927968338111127968338992796833811911 27 38 83 960123456 堆排序的关键是构造堆堆排序的关键是构造堆,这里采用筛选算法建堆：这里采用筛选算法建堆：假若完全二叉树的某一个结点假若完全二叉树的某一个结点i对于它的左子树、右对于它的左子树、右子树已是堆子树已是堆,接下来需要将接下来需要将R2i.key与与R2i+1.key之中之中的最大者与的最大者与Ri.key比较比较,若若Ri.key较小则交换较

35、小则交换,这有这有可能破坏下一级的堆。于是继续采用上述方法构造下可能破坏下一级的堆。于是继续采用上述方法构造下一级的堆。直到完全二叉树中结点一级的堆。直到完全二叉树中结点i构成堆为止。对构成堆为止。对于任意一棵完全二叉树于任意一棵完全二叉树,从从i= n/2 到到1,反复利用上述思反复利用上述思想建堆。大者想建堆。大者“上浮上浮”,小者被小者被“筛选筛选”下去。下去。 其调整堆的算法其调整堆的算法sift( )如下：如下：void sift(RecType R ,int low,int high) / 对对Rlow.high进行筛选进行筛选 int i=low, j=2*i; /*Rj是是Ri

36、的左孩子的左孩子*/ RecType temp=Ri; while (j=high) if (jhigh & Rj.keyRj+1.key) j+; if (temp.key=1;i-) /*循环建立初始堆循环建立初始堆*/ sift(R, i, n ); for (i=n;i=2;i-) /*进行进行n-1次循环次循环,完成推排序完成推排序*/ temp=R1; /*将第一个元素同当前区间内将第一个元素同当前区间内R1对换对换*/ R1=Ri;Ri=temp; sift(R,1,i-1); /*筛选筛选R1结点结点,得到得到i-1个结点的堆个结点的堆*/ 例例10.6 设待排序的表有

37、设待排序的表有10个记录个记录,其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的。说明采用堆排序方法进行排序的过程。过程。 6 8 7 9 0 2 4 1 3 5 9 8 7 6 5 2 4 1 3 0 (a) 初始状态初始状态 (b) 建立的初始堆建立的初始堆 0 8 7 6 5 2 4 1 3 8 6 7 4 5 2 0 1 3 (a) 交换交换 9 与与 0，输出，输出 9 (b) 筛选调整筛选调整 0 6 7 4 5 2 1 3 (c) 交换交换 8 与与 0，输出，输出 8 7 6 3 4 5 2 1 0 2 6 3 4 5 1 0 (

38、d) 筛选调整筛选调整 (e) 交换交换 7 与与 2，输出，输出 7 6 5 3 4 2 1 0 (f) 筛选调整筛选调整 堆排序过程：堆排序过程：98 97 8 998 97 8 9 0 5 3 4 2 1 5 4 3 0 2 1 (g) 交换交换 6 与与 0，输出，输出 6 (h) 筛选调整筛选调整 (i) 交换交换 5 与与 1，输出，输出 5 1 4 3 0 2 4 2 3 0 1 (j) 筛选调整筛选调整 1 2 3 2 3 2 0 (k) 交换交换 4 与与 1，输出，输出 4 (l) 筛选调整筛选调整 (m) 交换交换 3 与与 1，输出，输出 3 0 2 1 2 0 1 (

39、n) 筛选调整筛选调整 1 1 0 1 0 (o) 交换交换 2 与与 1，输出，输出 2 (p) 筛选调整筛选调整 (q) 交换交换 1 与与 0，输出，输出 1 0 1 0 (r) 输出输出 0 665 65 64 5 64 5 63 4 5 63 4 5 6222堆排序的时间复杂度为堆排序的时间复杂度为O(nlog2n)建初始堆建初始堆所需比较次数较多，以后各趟只所需比较次数较多，以后各趟只需对堆顶元素进行筛选，需对堆顶元素进行筛选，所以堆排序对所以堆排序对n较大的文件十分有效。较大的文件十分有效。10.5 10.5 归并排序归并排序 归并排序是多次将两个或两个以上的有序表合归并排序是多

40、次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。有序的子表合并成一个有序的表。 将两个有序表直接归并为一个有序表的算法将两个有序表直接归并为一个有序表的算法Merge( ) ：0 1 2 3 4 5 6 74913659776780R0 1 2 3 4 5 6 7 R1ijkMERGE (rectype R , int low, int mid, int high) low mid mid+1 high7jk13ik49ik65ik76jk4913659776780R0 1 2 3 4 5 6 7

41、 R1ijk713496576800 1 2 3 4 5 6 74913659776780R0 1 2 3 4 5 6 7 R1ijk71349657680将剩余的将剩余的Ri.mid复制到复制到R10 1 2 3 4 5 6 7 low mid mid+1 high4913659776780R0 1 2 3 4 5 6 7 R1ijk71349657680970 1 2 3 4 5 6 7 low mid mid+1 highvoid Merge(RecType R , int low, int mid, int high) RecType *R1; int i=low,j=mid+1,k=

42、0; /*k是是R1的下标的下标,i、j分别为第分别为第1、2段的下标段的下标*/ R1=(RecType *)malloc(high-low+1)*sizeof(RecType); while (i=mid & j=high) if (Ri.key=Rj.key) /*将第将第1段中的记录放入段中的记录放入R1中中*/ R1k=Ri; i+;k+; else /*将第将第2段中的记录放入段中的记录放入R1中中*/ R1k=Rj; j+;k+; 有序子序列有序子序列Rlow.mid有序子序列有序子序列Rmid+1.high 有有 序序 序序 列列 R1low.highwhile (i=

43、mid) /*将第将第1段余下部分复制到段余下部分复制到R1*/ R1k=Ri; i+;k+; while (j=high) /*将第将第2段余下部分复制到段余下部分复制到R1*/ R1k=Rj; j+;k+; for (k=0,i=low; i=high; k+,i+) /*将将R1复制回复制回R中中*/ Ri=R1k; free(R1); void MergePass(RecType R , int length, int n) int i; for (i=0;i+2*length-1n;i=i+2*length) /*归并归并length长的两相长的两相邻子表邻子表*/ Merge(R,

44、 i, i+length-1, i+2*length-1 ); if (i+length-1n) /*余下两个子表余下两个子表,后者长度小于后者长度小于length*/ Merge(R, i, i+length-1, n-1); /*归并这两个子表归并这两个子表*/MergePass( )实现了一趟归并实现了一趟归并 二路归并排序算法如下：二路归并排序算法如下：void MergeSort(RecType R,int n) /*自底向上的二路归并算法自底向上的二路归并算法*/ int length; for (length=1;length=0;i-) /*从低位到高位做从低位到高位做d趟排序

45、趟排序*/*123以以“321”存储存储*/for (j=0;jdatai-0; /*找第找第k个链队个链队*/if (headk=NULL) /*进行分配进行分配,即采用尾插法建立单链表即采用尾插法建立单链表*/headk=p; tailk=p; else tailk-next=p; tailk=p; p=p-next; /*取下一个待排序的元素取下一个待排序的元素*/分分配配 p=NULL; for (j=0;jnext=headj; t=tailj; t-next=NULL; /*最后一个结点的最后一个结点的next域置域置NULL*/ 收收集集 例例10.8 设待排序的表有设待排序的表

46、有10个记录个记录,其关键字分别为其关键字分别为75,23,98,44,57,12,29,64,38,82。说明采用基数排序。说明采用基数排序方法进行排序的过程。方法进行排序的过程。 初初始始关关键键字字 75 23 98 44 57 12 29 64 38 82 按按个个数数排排序序 12 82 23 44 64 75 57 98 38 29 按按十十位位排排序序 12 23 29 38 44 57 64 75 82 98 p 75 23 98 44 57 12 29 64 38 82 （a）初始状态）初始状态 head0 head1 head2 head3 head4 head5 head6 head7 head8 head9 tail0 tail1 tail2 tail3 tail4 tail5 tail6 t