数据结构第9章排序

《数据结构第9章排序》由会员分享，可在线阅读，更多相关《数据结构第9章排序（89页珍藏版）》请在金锄头文库上搜索。

1、第第9章章 排排 序序 在信息处理过程中，最基本的操作是查找。从查在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是所找来说，效率最高的是折半查找，折半查找的前提是所有的数据元素有的数据元素(记录记录)是按关键字有序的。需要将一个无是按关键字有序的。需要将一个无序的数据文件转变为一个有序的数据文件。序的数据文件转变为一个有序的数据文件。 将任一文件中的记录通过某种方法整理成为按将任一文件中的记录通过某种方法整理成为按(记记录录)关键字有序排列的处理过程称为关键字有序排列的处理过程称为排序排序。 排序是排序是数据处理数据处理中一种中一种最常用的操作最常用的操

2、作。9.1 排序的基本概念排序的基本概念 排序排序(Sorting) 排序排序是将一批是将一批(组组)任意次序的记录重新排列成任意次序的记录重新排列成按按关键字有序关键字有序的记录序列的过程，其定义为的记录序列的过程，其定义为： 给定一组记录序列给定一组记录序列：R1 , R2 , , Rn，其相应的其相应的关键字序列是关键字序列是K1 , K2 , , Kn 。确定确定1, 2, n的一个的一个排列排列p1 , p2 , , pn，使其相应的关键字满足如下非递使其相应的关键字满足如下非递减减(或非递增或非递增)关系关系： Kp1Kp2 Kpn的序列的序列Kp1 ,Kp2 , ,Kpn ，这种

3、操作称为排序。这种操作称为排序。 关键字关键字Ki可以是记录可以是记录Ri的主关键字的主关键字，也可以是次关也可以是次关键字或若干数据项的组合。键字或若干数据项的组合。 Ki是主关键字：排序后得到的结果是唯一的；是主关键字：排序后得到的结果是唯一的； Ki是次关键字：排序后得到的结果是不唯一的。是次关键字：排序后得到的结果是不唯一的。 排序的稳定性排序的稳定性 若记录序列中有若记录序列中有两个或两个以上关键字相等两个或两个以上关键字相等的记的记录：录： Ki =Kj(ij，i, j=1, 2, n)，且在排序前且在排序前Ri先于先于Rj(ij)，排序后的记录序列仍然是排序后的记录序列仍然是Ri

4、先于先于Rj，称排序方称排序方法是稳定的，否则是不稳定的。法是稳定的，否则是不稳定的。 排序算法有许多，但就全面性能而言，还没有一种排序算法有许多，但就全面性能而言，还没有一种公认为最好的。每种算法都有其优点和缺点，分别适合公认为最好的。每种算法都有其优点和缺点，分别适合不同的数据量和硬件配置。不同的数据量和硬件配置。 评价排序算法的标准有：评价排序算法的标准有：执行时间执行时间和和所需的辅助空所需的辅助空间间，其次是，其次是算法的稳定性算法的稳定性。 若排序算法所需的辅助空间不依赖问题的规模若排序算法所需的辅助空间不依赖问题的规模n，即空间复杂度是即空间复杂度是O(1) ，则称排序方法是则称

5、排序方法是就地排序就地排序，否则，否则是是非就地排序非就地排序。 排序的分类排序的分类 待排序的记录数量不同，排序过程中涉及的存储器待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。的不同，有不同的排序分类。 待排序的记录数不太多待排序的记录数不太多：所有的记录都能存放在：所有的记录都能存放在内存中进行排序，称为内存中进行排序，称为内部排序内部排序； 待排序的记录数太多待排序的记录数太多：所有的记录不可能存放在：所有的记录不可能存放在内存中，内存中， 排序过程中必须在内、外存之间进行数据排序过程中必须在内、外存之间进行数据交换，这样的排序称为交换，这样的排序称为外部排序外部

6、排序。 内部排序的基本操作内部排序的基本操作 对内部排序地而言，其基本操作有两种对内部排序地而言，其基本操作有两种： 比较两个关键字的大小；比较两个关键字的大小； 存储位置的移动：从一个位置移到另一个位置。存储位置的移动：从一个位置移到另一个位置。 第一种操作是必不可少的；而第二种操作却不是必第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是：须的，取决于记录的存储方式，具体情况是： 记录存储在一组连续地址的存储空间记录存储在一组连续地址的存储空间：记录之间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，的逻辑顺序关系是通过其物理存储位置的相邻来体现，

7、记录的移动是必不可少的记录的移动是必不可少的； 记录采用链式存储方式记录采用链式存储方式：记录之间的逻辑顺序关：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程系是通过结点中的指针来体现，排序过程仅需修改结仅需修改结点的指针点的指针，而，而不需要移动记录不需要移动记录；记录存储在一组连续地址的存储空间记录存储在一组连续地址的存储空间：构造另一：构造另一个辅助表来保存各个记录的存放地址个辅助表来保存各个记录的存放地址(指针指针) ：排：排序过程序过程不需要移动记录不需要移动记录，而，而仅需修改辅助表中的仅需修改辅助表中的指针指针，排序后视具体情况决定是否调整记录的存，排序后视具体情况决定

8、是否调整记录的存储位置。储位置。 比较适合记录数较少的情况；而比较适合记录数较少的情况；而、则适合记则适合记录数较多的情况。录数较多的情况。 为讨论方便，假设待排序的记录是以为讨论方便，假设待排序的记录是以的情况存的情况存储，且设排序是按升序排列的；关键字是一些可直储，且设排序是按升序排列的；关键字是一些可直接用比较运算符进行比较的类型。接用比较运算符进行比较的类型。待排序的记录类型的定义如下：待排序的记录类型的定义如下：#define MAX_SIZE 100Typedef int KeyType ;typedef struct RecType KeyType key ; /* 关键字码关键

9、字码 */infoType otherinfo ; /* 其他域其他域 */RecType ;typedef struct Sqlist RecType RMAX_SIZE ;int length ;Sqlist ;9.2 插入排序插入排序 采用的是以采用的是以 “玩桥牌者玩桥牌者”的方法为基础的的方法为基础的。即在考。即在考察记录察记录Ri之前之前，设以前的所有记录，设以前的所有记录R1, R2 ,., Ri-1已排已排好序好序，然后将，然后将Ri插入到插入到已排好序的诸记录的适当位置已排好序的诸记录的适当位置。 最基本的插入排序是最基本的插入排序是直接插入排序直接插入排序(Straight

10、 Insertion Sort) 。9.2.1 直接插入排序直接插入排序1 排序思想排序思想 将待排序的记录将待排序的记录Ri，插入到已插入到已排好序的排好序的记录表记录表R1, R2 ,., Ri-1中中，得到一个新的、记录数增加，得到一个新的、记录数增加1的有序表的有序表。 直到所有的记录都插入完为止直到所有的记录都插入完为止。 设设待排序的记录顺序存放在数组待排序的记录顺序存放在数组R1n中，在排序中，在排序的某一时刻，将记录序列分成两部分：的某一时刻，将记录序列分成两部分： R1i-1：已：已排好序的有序部分排好序的有序部分； Rin：未：未排好序的无序部分。排好序的无序部分。 显然，

11、在刚开始排序时，显然，在刚开始排序时，R1是已经是已经排好序的。排好序的。 例例：设有关键字序列为：设有关键字序列为：7, 4, -2, 19, 13, 6，直接插，直接插入排序的过程如下图入排序的过程如下图9-1所示：所示：初始记录的关键字初始记录的关键字： 7 4 -2 19 13 6第一趟排序第一趟排序： 4 7 -2 19 13 6第二趟排序第二趟排序： -2 4 7 19 13 6第三趟排序第三趟排序： -2 4 7 19 13 6第四趟排序第四趟排序： -2 4 7 13 19 6第五趟排序第五趟排序： -2 4 6 7 13 19图图9-1 直接插入排序的过程直接插入排序的过程2

12、 算法实现算法实现void straight_insert_sort(Sqlist *L) int i, j ;for (i=2; ilength; i+) L-R0=L-Ri; j=i-1; /* 设置哨兵设置哨兵 */while( LT(L-R0.key, L-Rj.key) ) L-Rj+1=L-Rj; j-; /* 查找插入位置查找插入位置 */L-Rj+1=L-R0; /* 插入到相应位置插入到相应位置 */3 算法说明算法说明 算法中的算法中的R0开始时并不存放任何待排序的记录，开始时并不存放任何待排序的记录，引入的作用主要有两个：引入的作用主要有两个： 不需要增加辅助空间：不需要

13、增加辅助空间： 保存当前待插入的记录保存当前待插入的记录Ri，Ri会会因为记录的后移而被占用；因为记录的后移而被占用； 保证查找插入位置的内循环总可以在超出循环边保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起界之前找到一个等于当前记录的记录，起“哨兵监视哨兵监视”作用，避免在内循环中每次都要判断作用，避免在内循环中每次都要判断j是否越界是否越界。4 算法分析算法分析 最好情况最好情况：若待排序记录按关键字从小到大排若待排序记录按关键字从小到大排列列( (正序正序) )，算法中的内循环无须执行，算法中的内循环无须执行，则一趟排序时：则一趟排序时：关键字比较次数关键

14、字比较次数1次，记录移动次数次，记录移动次数2次次(RiR0, R0Rj+1)。 则整个排序的关键字比较次数和记录移动次数分别则整个排序的关键字比较次数和记录移动次数分别是：是：比较次数比较次数：1=n-1ni=2移动次数移动次数： 2=2(n-1)ni=2 最坏情况最坏情况：若待排序记录按关键字从大到小排若待排序记录按关键字从大到小排列列( (逆序逆序) )，则一趟排序时：算法中的内循环体执行，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数关键字比较次数i次，记录移动次数次，记录移动次数i+1。则就整个排序而言：则就整个排序而言：比较次数比较次数： i=ni=2(n-1)(n+1)

15、2移动次数移动次数：(i+1)=ni=2(n-1)(n+4)2 一般地一般地，认为，认为待排序的记录可能出现的各种排列的待排序的记录可能出现的各种排列的概率相同概率相同，则取以上两种情况的平均值，作为排序的，则取以上两种情况的平均值，作为排序的关关键字比较次数和记录移动次数键字比较次数和记录移动次数，约为约为n2/4，则，则复杂度为复杂度为O(n2) 。9.2.2 其它插入排序其它插入排序1 折半插入排序折半插入排序 当将待排序的记录当将待排序的记录Ri 插入到已排好序的记录子表插入到已排好序的记录子表R1i-1中时，由于中时，由于R1, R2 , Ri-1已排好序，则查找已排好序，则查找插入

16、位置可以用插入位置可以用“折半查找折半查找”实现，则直接插入排序就实现，则直接插入排序就变成为折半插入排序。变成为折半插入排序。 算法实现算法实现void Binary_insert_sort(Sqlist *L) int i, j, low, high, mid ;for (i=2; ilength; i+) L-R0=L-Ri; /* 设置哨兵设置哨兵 */low=1 ; high=i-1 ; while (lowR0.key, L-Rmid.key) ) high=mid-1 ; else low=mid+1 ; /* 查找插入位置查找插入位置 */for (j=i-1; j=high+

17、1; j-)L-Rj+1=L-Rj; L-Rhigh+1=L-R0; /* 插入到相应位置插入到相应位置 */ 从时间上比较从时间上比较，折半插入排序仅仅减少了关键字的，折半插入排序仅仅减少了关键字的比较次数比较次数，却没有减少，却没有减少记录的移动次数记录的移动次数，故时间故时间复杂度复杂度仍然为仍然为O(n2) 。 排序示例排序示例 设有一组关键字设有一组关键字30, 13, 70, 85, 39, 42, 6, 20，采用折采用折半插入排序方法排序的过程如图半插入排序方法排序的过程如图9-2所示：所示：i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30)

18、70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85) 20i=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 20 (6 13 30 39 42 70 85) 20lowhighmidi=8 20 (6 13 30 39 42 70 85) 20mid highlowi=8 20 (6 13 20 30 39 42 70 85)图图9-2 折半插入排序过程折半插入排序过程2 2-路插入排序路插入排序 是对折半插入排序的改进是对折半插入排序的改进，以减少排序过程中移动以减少排序过程中移动记录的次数记录的次数。附加附加n个记

19、录的辅助空间个记录的辅助空间，方法是，方法是： 另设一个和另设一个和L-R同同类型的数组类型的数组d，L-R1赋给赋给d1，将，将d1看成是排好序的序列中中间位置的记录；看成是排好序的序列中中间位置的记录； 分别将分别将L-R 中的第中的第i个记录依次插入到个记录依次插入到d1之之前或之后前或之后的有序序列中，具体方法的有序序列中，具体方法： L-Ri.keyRi插入到插入到d1之前之前的有序表中；的有序表中； L-Ri.keyd1.key： L-Ri插入到插入到d1之后之后的有序表中；的有序表中；关键点关键点：实现时将实现时将向量向量d看成是循环向量看成是循环向量，并设两个指，并设两个指针针

20、first和和final分别指示排序过程中得到的有序序列中的分别指示排序过程中得到的有序序列中的第一个和最后一个记录第一个和最后一个记录。排序示例排序示例设有初始关键字集合设有初始关键字集合49, 38, 65, 13, 97, 27, 76 ，采，采用用2-路插入排序的过程如右图路插入排序的过程如右图9-3所示。所示。 在在2-路插入排序中，移动记录的次数约为路插入排序中，移动记录的次数约为n2/8 。但当但当L-R1是待排序记录中关键字最大或最小的记录是待排序记录中关键字最大或最小的记录时，时，2-路插入排序就完全失去了优越性。路插入排序就完全失去了优越性。2776d49firstfirs

21、tfirstfirstfinalfinalfinalfinal653897971313图图9-3 2-路插入排序过程路插入排序过程3 表插入排序表插入排序前面的插入排序不可避免地要移动记录，若不移动记录前面的插入排序不可避免地要移动记录，若不移动记录就需要改变数据结构。附加就需要改变数据结构。附加n个记录的辅助空间，记录个记录的辅助空间，记录类型修改为：类型修改为：typedef struct RecNode KeyType key ;infotype otherinfo ;int *next;RecNode ;初始化初始化：下标值为：下标值为0的分量作为表头结点的分量作为表头结点，关键字取，

22、关键字取为最大值，各分量的指针值为空；为最大值，各分量的指针值为空； 将静态链表中将静态链表中数组下标值为数组下标值为1的分量的分量(结点结点)与表与表头结点构成一个循环链表；头结点构成一个循环链表； i=2 ，将分量将分量Ri按关键字递减插入到循环链表；按关键字递减插入到循环链表； 增加增加i ，重复，重复，直到全部分量插入到循环链表。，直到全部分量插入到循环链表。例：例：设有关键字集合设有关键字集合49, 38, 65, 97, 76, 13, 27, 49 ，采，采用表插入排序的过程如下图用表插入排序的过程如下图9-4所示所示。 0 1 2 3 4 5 6 7 8key域域next域域M

23、AXINT 49 38 65 13 97 27 76 49 1 0 - - - - - - -i=2MAXINT 49 38 65 13 97 27 76 49 2 0 1 - - - - - -i=3MAXINT 49 38 65 13 97 27 76 49 2 3 1 0 - - - - -i=4MAXINT 49 38 65 13 97 27 76 49 4 3 1 0 2 - - - -i=5MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 2 0 - - - 和直接插入排序相比，不同的是修改和直接插入排序相比，不同的是修改2n次指针值以次指针值以代替移动

24、记录，而代替移动记录，而关键字的比较次数相同关键字的比较次数相同，故时间复杂故时间复杂度为度为O(n2)。 表表插入排序得到一个有序链表，对其可以方便地进插入排序得到一个有序链表，对其可以方便地进行顺序查找，但不能实现随机查找行顺序查找，但不能实现随机查找。根据需要，可以对根据需要，可以对记录进行重排，记录重排详见记录进行重排，记录重排详见P247。i=6MAXINT 49 38 65 13 97 27 76 49 4 3 1 5 6 0 2 - -i=7MAXINT 49 38 65 13 97 27 76 49 4 3 1 7 6 0 2 5 -i=8MAXINT 49 38 65 13

25、97 27 76 49 4 8 1 7 6 0 2 5 3图图9-4 表插入排序过程表插入排序过程9.2.3 希尔排序希尔排序 希尔排序希尔排序(Shell Sort，又称，又称缩小增量法缩小增量法)是一种是一种分组插入排序方法分组插入排序方法。1 排序思想排序思想 先取一个正整数先取一个正整数d1(d1n)作为第一个增量，将全作为第一个增量，将全部部n个记录分成个记录分成d1组，组，把所有相隔把所有相隔d1的记录放在一组的记录放在一组中，即对于每个中，即对于每个k(k=1, 2, d1)，Rk, Rd1+k, R2d1+k , 分在分在同一组中同一组中，在各组内进行直接插入，在各组内进行直接

26、插入排序排序。这样一次分组和排序过程称为一趟这样一次分组和排序过程称为一趟希尔排序希尔排序； 取新的增量取新的增量d2d1，重复重复的的分组和排序操作；分组和排序操作；直至所取的增量直至所取的增量di=1为止，为止，即所有记录放进一个组中即所有记录放进一个组中排序为止排序为止。2 排序示排序示例例 设有设有10个待排序的记录个待排序的记录，关键字分别为，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是，增量序列是5, 3, 1，希尔排序的过程，希尔排序的过程如图如图9-5所示所示。9 7 1 2 5 13 13 8 15 11第一趟排序后第一趟排序后:2

27、 5 1 9 7 13 11 8 15 13第二趟排序后第二趟排序后:1 2 5 7 8 9 11 13 13 15第三趟排序后第三趟排序后:图图9-5 希尔排序过程希尔排序过程9 13 8 2 5 13 7 1 15 1171318初始关键字序列初始关键字序列:第一趟排序过程第一趟排序过程:3 算法实现算法实现 先给出一趟希尔排序的算法，类似直接插入排序先给出一趟希尔排序的算法，类似直接插入排序。void shell_pass(Sqlist *L, int d) /* 对顺序表对顺序表L进行一趟希尔排序进行一趟希尔排序, 增量为增量为d */ int j, k ;for (j=d+1; jl

28、ength; j+) L-R0=L-Rj ; /* 设置监视哨兵设置监视哨兵 */k=j-d ;while (k0<(L-R0.key, L-Rk.key) ) L-Rk+d=L-Rk ; k=k-d ; L-Rk+j=L-R0 ; 然后在根据增量数组然后在根据增量数组dk进行希尔排序进行希尔排序。void shell_sort(Sqlist *L, int dk, int t) /* 按增量序列按增量序列dk0 t-1,对顺序表对顺序表L进行希尔排序进行希尔排序 */ int m ;for (m=0; mR1与与L-R2的关键字进行比较的关键字进行比较，若，若为反序为反序( (L-R1的

29、关键字大于的关键字大于L-R2的关键字的关键字) )，则，则交换两个记录交换两个记录；然后比较然后比较L-R2与与L-R3的关键字的关键字，依此类推，直到依此类推，直到L-Rn-1与与L-Rn的关键字比较后的关键字比较后为止为止，称为一趟，称为一趟冒泡排序冒泡排序，L-Rn为关键字最大的为关键字最大的记录记录。 然后进行第二趟然后进行第二趟冒泡排序冒泡排序，对前，对前n-1个记录进行个记录进行同样的操作同样的操作。 一般地，第一般地，第i趟趟冒泡排序是对冒泡排序是对L-R1 n-i+1中的中的记录进行的记录进行的，因此，若待排序的记录有，因此，若待排序的记录有n个个，则要经过，则要经过n-1趟

30、趟冒泡排序才能使所有的记录有序冒泡排序才能使所有的记录有序。2 排序示排序示例例 设有设有9个待排序的记录个待排序的记录，关键字分别为，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程如图，冒泡排序的过程如图9-6所示所示。3 算法实现算法实现#define FALSE 0#define TRUE 1图图9-6 冒泡排序过程冒泡排序过程23 38 22 45 23 67 31 15 41初始关键字序列初始关键字序列:第一趟排序后第一趟排序后:23 22 38 23 45 31 15 41 67第二趟排序后第二趟排序后:22 23 23 38 31

31、 15 41 45 67第三趟排序后第三趟排序后:22 23 23 31 15 38 41 45 67第四趟排序后第四趟排序后:22 23 23 15 31 38 41 45 67第五趟排序后第五趟排序后:22 23 15 23 31 38 41 45 67第六趟排序后第六趟排序后:22 15 23 23 31 38 41 45 67第七趟排序后第七趟排序后:15 22 23 23 31 38 41 45 67void Bubble_Sort(Sqlist *L) int j ,k , flag ;for (j=0; jlength; j+) /* 共有共有n-1趟排序趟排序 */ flag=

32、TRUE ;for (k=1; klength-j; k+) /* 一趟排序一趟排序 */ if (LT(L-Rk+1.key, L-Rk.key ) ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if (flag=TRUE) break ;故时间复杂度故时间复杂度：T(n)=O(n)空间复杂度：空间复杂度：S(n)=O(1)4 算法分析算法分析时间复杂度时间复杂度 最好情况最好情况(正序正序)：比较次数：比较次数：n-1；移动次数：；移动次数：0； 最坏情况最坏情况(逆序逆序)：比较次数比较次数：(n-i)=n-1i=1n(n-

33、1)2移动次数移动次数： 3(n-i)=n-1i=13n(n-1)29.3.2 快速排序快速排序1 排序思想排序思想 通过一趟排序，将待排序记录分割成独立的两部分，其中一通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序部分记录进行下一趟排序，以达到整个序列有序。2 排序过程排序过程 设待排序的记录序列是设待排序的记录序列是Rst ，在，在记录序列中记录序列中任取任取一个记一个记录录(一般取一般取Rs)作为作为参照参照(又称为又称为基准基准

34、或或枢轴枢轴)，以，以Rs.key为为基基准重新排列其余的所有记录准重新排列其余的所有记录，方法是方法是： 所有关键字比基准小的放所有关键字比基准小的放Rs之前之前； 所有关键字比基准大的放所有关键字比基准大的放Rs之后之后。 以以Rs.key最后所在位置最后所在位置i作为分界，将序列作为分界，将序列Rst分割成两个子序列，称为一趟快速排序分割成两个子序列，称为一趟快速排序。3 一趟快速排序方法一趟快速排序方法 从序列的两端交替扫描各个记录，将从序列的两端交替扫描各个记录，将关键字小于关键字小于基准关键字的记录基准关键字的记录依次依次放置到序列的前边放置到序列的前边；而将而将关键字关键字大于基

35、准关键字的记录大于基准关键字的记录从序列的最后端起，依次从序列的最后端起，依次放置到放置到序列的后边序列的后边，直到扫描完所有的记录，直到扫描完所有的记录。 设置指针设置指针low，high，初值为第，初值为第1个和最后一个记个和最后一个记录的位置。录的位置。 设两个变量设两个变量i，j，初始时令初始时令i=low，j=high，以以Rlow.key作为基准作为基准(将将Rlow保存在保存在R0中中) 。 从从j所指位置向前搜索：将所指位置向前搜索：将R0.key与与Rj.key进进行比较行比较： 若若R0.keyRj.key ：令：令j=j-1，然后继续进，然后继续进行比较，行比较， 直到直

36、到i=j或或R0.keyRj.key为止为止； 若若R0.keyRj.key ：RjRi，腾空腾空Rj的的位置位置， 且令且令i=i+1； 从从i所指位置起向后搜索：将所指位置起向后搜索：将R0.key与与Ri.key进行比较进行比较： 若若R0.keyRi.key ：令：令i=i+1，然后继续进，然后继续进行比较，行比较， 直到直到i=j或或R0.keyRi.key为止为止； 若若R0.keyR0=L-Ri ; /* R0作为临时单元和哨兵作为临时单元和哨兵 */do while (LQ(L-R0.key, L-Rj.key)&(ji) j- ;if (ji) L-Ri=L-Rj ; i+;

37、 while (LQ(L-Ri.key, L-R0.key)&(ji) i+ ;if (ji) L-Rj=L-Ri ; j-; while(i!=j) ; /* i=j时退出扫描时退出扫描 */L-Ri=L-R0 ; return(i) ; 快速排序算法实现快速排序算法实现 当进行一趟快速排序后当进行一趟快速排序后，采采用同样方法分别对用同样方法分别对两两个子序列个子序列快速排序快速排序，直到，直到子子序列记录个为序列记录个为1为止为止。 递归算法递归算法 void quick_Sort(Sqlist *L , int low, int high) int k ;if (lowhigh) k=

38、quick_one_pass(L, low, high);quick_Sort(L, low, k-1);quick_Sort(L, k+1, high); /* 序列分为两部分后分别对每个子序列排序序列分为两部分后分别对每个子序列排序 */ 非递归算法非递归算法# define MAX_STACK 100void quick_Sort(Sqlist *L , int low, int high) int k , stackMAX_STACK , top=0; do while (lowhigh) k=quick_one_pass(L,low,high); stack+top=high ; s

39、tack+top=k+1 ; /* 第二个子序列的上第二个子序列的上,下界分别入栈下界分别入栈 */ high=k-1 ; if (top!=0) low=stacktop- ; high=stacktop- ; while (top!=0&low1时，用时，用n-1代替代替中的中的n，得到，得到：Tavg(n)=(n-1)C+ Tavg(k) n-2k=02n nTavg(n)-(n-1)Tavg(n-1)=(2n-1)C+2Tavg(n-1) ，即即Tavg(n)=(n+1)/nTavg(n-1)+(2n-1)/nC(n+1)/nTavg(n-1)+2C(n+1)/nn/(n-1)Tavg

40、(n-2)+2C+2C=(n+1)/(n-1)Tavg(n-2)+2(n+1)1/n+1/(n+1)C Tavg(1)+2(n+1)C2n+13141+1n+1n1+ Tavg(n)只有只有1个记录的排序时间是个记录的排序时间是一个常数一个常数， 快速排序的平均时间复杂度是快速排序的平均时间复杂度是：T(n)=O(n2n) 从所需要的附加空间来看从所需要的附加空间来看，快速排序算法是递归调，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为时，栈的最大深度为2n+1 。 快速排序的空间复杂度是快速排序的空间复杂

41、度是：S(n)=O(2n) 从排序的稳定性来看，快速排序是从排序的稳定性来看，快速排序是不稳定不稳定的。的。9. 4 选择排序选择排序 选择排序选择排序(Selection Sort)的基本思想是：每的基本思想是：每次从当前次从当前待排序的记录待排序的记录中选取关键字最小的中选取关键字最小的记录，然后记录，然后与与待排序的记录序列待排序的记录序列中的第中的第一个记录进行交换，直到整一个记录进行交换，直到整个记录序列有序为止个记录序列有序为止。 9.4.1 简单选择排序简单选择排序 简单选择排序简单选择排序(Simple Selection Sort ，又，又称为称为直直接选择排序接选择排序)的

42、基本操作是的基本操作是：通过：通过n-i次关键字间的比较，次关键字间的比较，从从n-i+1个记录中选取关键字最小的记录，然后和第个记录中选取关键字最小的记录，然后和第i个记个记录进行交换，录进行交换，i=1, 2, n-1 。1 排序示例排序示例 例例：设有关键字序列为：设有关键字序列为：7, 4, -2, 19, 13, 6，直接选，直接选择排序的过程如下图择排序的过程如下图9-8所示。所示。图图9-8 直接选择排序的过程直接选择排序的过程初始记录的关键字初始记录的关键字： 7 4 -2 19 13 6第一趟排序第一趟排序：-2 4 7 19 13 6第二趟排序第二趟排序： -2 4 7 1

43、9 13 6第三趟排序第三趟排序： -2 4 6 19 13 7第四趟排序第四趟排序： -2 4 6 7 13 19第五趟排序第五趟排序： -2 4 6 7 13 19第六趟排序第六趟排序： -2 4 6 7 13 192算法实现算法实现 1.void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; mlength; m+) k=m ; for (n=m+1; nlength; n+) if ( LT(L-Rn.key, L-Rk.key) ) k=n ;if (k!=m) /* 记录交换记录交换 */ L-R0=L-Rm; L-

44、Rm=L-Rk; L-Rk=L-R0; 3 算法分析算法分析 整个算法是二重循环整个算法是二重循环：外循环控制排序的趟数，对：外循环控制排序的趟数，对n个记录进行排序的趟数为个记录进行排序的趟数为n-1趟；内循环控制每一趟的趟；内循环控制每一趟的排序排序。 进行第进行第i趟排序时趟排序时，关键字的比较次数为，关键字的比较次数为n-i，则：，则：比较次数比较次数： (n-i)=n-1i=1n(n-1)2 时间复杂度时间复杂度是是：T(n)=O(n2) 空间复杂度是空间复杂度是：S(n)=O(1) 从排序的稳定性来看从排序的稳定性来看，直接选择排序是直接选择排序是不稳定不稳定的的。9.4.2 树形

45、选择排序树形选择排序 借助借助“淘汰赛淘汰赛”中的对垒就很容易理解树形选择排中的对垒就很容易理解树形选择排序的思想。序的思想。 首先对首先对n个记录的关键字两两进行比较个记录的关键字两两进行比较，选取，选取 n/2 个较小者个较小者；然后这；然后这 n/2 个较小者个较小者两两进行比较两两进行比较，选取，选取 n/4 个较小者个较小者 如此重复，直到只剩如此重复，直到只剩1个关键字为止个关键字为止。该过程可用一棵有该过程可用一棵有n个叶子结点的完全二叉树表示，如个叶子结点的完全二叉树表示，如图图9-9所示。所示。 每个枝结点的关键字都等于其左、右孩子结点中较每个枝结点的关键字都等于其左、右孩子

46、结点中较小的关键字，小的关键字，根结点的关键字就是最小的关键字根结点的关键字就是最小的关键字。 输出最小关键字后输出最小关键字后，根据，根据关系的可传递性关系的可传递性，欲选取，欲选取次小关键字，只需将叶子结点中的最小关键字改为次小关键字，只需将叶子结点中的最小关键字改为“最最大值大值” ，然后重复上述步骤即可，然后重复上述步骤即可。 含有含有n个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为 2n +1，则总的时间复杂度为则总的时间复杂度为O(n2n) 。492525372828196519153415251515图图9- “淘汰赛淘汰赛”过程示意图过程示意图9.4.3 堆排序堆

47、排序1 堆的定义堆的定义 是是n个元素的序列个元素的序列H=k1, k2 , kn ，满足满足：kik2i 当当2in时时kik2i+1 当当2i+1n时时或或kik2i 当当2in时时ki k2i+1 当当2i+1n时时其中其中： i=1,2 , , n/2 由堆的定义知由堆的定义知，堆是一棵以，堆是一棵以k1为根的完全二叉树为根的完全二叉树。若对该二叉树的结点进行编号若对该二叉树的结点进行编号(从上到下从上到下，从左到右从左到右)，得到的序列就是将二叉树的结点以得到的序列就是将二叉树的结点以顺序结构存放顺序结构存放，堆的，堆的结构正好和该序列结构完全一致结构正好和该序列结构完全一致。2 堆

48、的性质堆的性质 堆是一棵采用顺序存储结构的完全堆是一棵采用顺序存储结构的完全二叉树二叉树， k1是是根结点；根结点； 堆的根结点是关键字序列中的最小堆的根结点是关键字序列中的最小(或最大或最大)值值，分别称为小分别称为小(或大或大)根堆；根堆； 从根结点到每一叶子结点路径上的元素组成的序从根结点到每一叶子结点路径上的元素组成的序列都是按元素值列都是按元素值(或关键字值或关键字值)非递减非递减(或非递增或非递增)的；的；堆中的任一子树也是堆堆中的任一子树也是堆。 利用堆顶记录的关键字值最小利用堆顶记录的关键字值最小(或最大或最大)的性质的性质，从，从当前待排序的记录中当前待排序的记录中依次选取关

49、键字依次选取关键字最小最小(或最大或最大)的记的记录，就可以实现对数据记录的排序，这种排序方法称为录，就可以实现对数据记录的排序，这种排序方法称为堆排序堆排序。3 堆排序思想堆排序思想 对一组待排序的记录，按堆的定义对一组待排序的记录，按堆的定义建立堆建立堆； 将将堆顶记录和最后一个记录交换堆顶记录和最后一个记录交换位置位置，则前，则前n-1个记录是无序的个记录是无序的，而最后，而最后一个记录是有序的一个记录是有序的； 堆顶记录堆顶记录被交换后被交换后，前，前n-1个记录不再是堆个记录不再是堆，需，需将前将前n-1个待排序记录重新组织成为一个堆个待排序记录重新组织成为一个堆，然后，然后将将堆顶

50、记录和倒数第二个记录交换堆顶记录和倒数第二个记录交换位置位置，即将整个序，即将整个序列中次小关键字值的记录调整列中次小关键字值的记录调整(排除排除)出无序区出无序区； 重复上述步骤重复上述步骤，直到全部记录排好序为止，直到全部记录排好序为止。 结论结论：排序过程中，排序过程中，若若采用采用小根堆小根堆，排序后得到的是，排序后得到的是非递减序列非递减序列；若；若采用采用大根堆大根堆，排序后得到的是，排序后得到的是非递增序非递增序列列。堆堆排序的关键排序的关键 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元

51、素，使之成为一个新的堆？成为一个新的堆？ 4 堆的调整堆的调整筛选筛选 堆的调整思想堆的调整思想 输出堆顶元素之后，以堆中最后一个元素替代之；输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换与其中小者进行交换；重复上述操作，直到是叶子结点；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得或其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为到新的堆。称这个从堆顶至叶子的调整过程为“筛选筛选”，如图，如图9-10所示所示。注意

52、注意：筛选过程中，根结点的左、右子树都是堆，因筛选过程中，根结点的左、右子树都是堆，因此，筛选是从根结点到某个叶子结点的一次调整过程此，筛选是从根结点到某个叶子结点的一次调整过程。图图9-10 堆的筛选过程堆的筛选过程49253728196534182715492537281965342718154927372819653425181549253728196534181527 堆调整堆调整算法实现算法实现void Heap_adjust(Sqlist *H, int s, int m)/* H-Rsm中记录关键字除中记录关键字除H-Rs.key均满足堆定义均满足堆定义 */* 调整调整H-Rs

53、的位置使之成为的位置使之成为小根堆小根堆 */ int j=s, k=2*j ; /* 计算计算H-Rj的的左孩子的位置左孩子的位置 */H-R0=H-Rj ; /* 临时保存临时保存H-Rj */ for (k=2*j; k=m; k=2*k) if (kRk+1.key, H-Rk.key) k+ ; /* 选择选择左、右孩子中关键字的最小者左、右孩子中关键字的最小者 */if ( LT(H-Rk.key, H-R0.key) ) H-Rj=H-Rk ; j=k ; k=2*j else break ;H-Rj=H-R0 ; 5 堆的建立堆的建立 利用筛选算法，可以将任意无序的记录序列建成

54、一利用筛选算法，可以将任意无序的记录序列建成一个堆，个堆，设设R1,R2, ,Rn是待排序的记录序列。是待排序的记录序列。 将二叉树的将二叉树的每棵子树都筛选成为堆每棵子树都筛选成为堆。只有根结点的。只有根结点的树是堆树是堆。第。第 n/2 个结点之后的所有个结点之后的所有结点都没有子树，即结点都没有子树，即以以第第 n/2 个结点之后的个结点之后的结点为根的子树都是堆结点为根的子树都是堆。因此。因此，以这些结点为以这些结点为左、右孩子的结点，其左、右子树都是堆，左、右孩子的结点，其左、右子树都是堆，则进行一次筛选就可以成为堆则进行一次筛选就可以成为堆。同理，只要将这些结点同理，只要将这些结点

55、的直接父结点进行一次筛选就可以成为堆的直接父结点进行一次筛选就可以成为堆。 只需从只需从第第 n/2 个记录到第个记录到第1个记录依次进行筛选就可个记录依次进行筛选就可以建立堆。以建立堆。可用下列语句实现可用下列语句实现：for (j=n/2; j=1; j-)Heap_adjust(R, j , n) ;6 堆排序算法实现堆排序算法实现 堆的根结点是堆的根结点是关键字最小的记录关键字最小的记录，输出根结点后输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的是以序列的最后一个记录作为根结点，而原来堆的左、左、右子树都是堆右子树都是堆，则，则进行一次筛选就可以成为堆进行一次筛选就可以成为

56、堆。void Heap_Sort(Sqlist *H) int j ;for (j=H-length/2; j0; j-)Heap_adjust(H, j , H-length) ; /* 初始建堆初始建堆 */for (j=H-length/2; j=1; j-) H-R0=H-R1 ; H-R1=H-Rj ;H-Rj=H-R0 ; /* 堆顶与最后一个交换堆顶与最后一个交换 */Heap_adjust(H, 1, j-1) ; 7 算法分析算法分析 主要过程：初始建堆和重新调整成堆主要过程：初始建堆和重新调整成堆。设记录数为。设记录数为n，所对应的完全二叉树深度为，所对应的完全二叉树深度为

57、h 。 初始建堆初始建堆：每个非叶子结点都要从上到下做：每个非叶子结点都要从上到下做“筛筛选选” 。第。第i层结点数层结点数2i-1，结点下移的最大深度是，结点下移的最大深度是h-i，而每下移一层要比较，而每下移一层要比较2次，则比较次数次，则比较次数C1(n)为：为：C1(n) 2 (2i-1(h-i)4(2h-h-1)h-1i=1 h= 2n +1， C1(n)4(n-2n-1) 筛选调整筛选调整：每次筛选要将根结点：每次筛选要将根结点“下沉下沉”到到一个一个合适位置合适位置。第。第i次筛选时次筛选时：堆中元素个：堆中元素个数为数为n-i+1；堆堆的深度是的深度是 2(n-i+1) +1，

58、则进行则进行n-1次次“筛选筛选”的比的比较次数较次数C2(n)为为：C2(n) (22(n-i+1)n-1i=1 C2(n)2n2n 堆排序的比较次数的数量级为：堆排序的比较次数的数量级为： T(n)=O(n2n)；而；而附加空间就是交换时所用的临时空间，故空间复附加空间就是交换时所用的临时空间，故空间复杂度为：杂度为： S(n)=O(1) 。9. 5 归并排序归并排序 归并归并(Merging) ：是指将两个或两个以上的有序序是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表列合并成一个有序序列。若采用线性表(无论是那种存无论是那种存储结构储结构)易于实现，其时间复杂度为易于实

59、现，其时间复杂度为O(m+n) 。 归并思想实例归并思想实例：两堆扑克牌，都两堆扑克牌，都已从小到大排好已从小到大排好序序，要将两堆合并为一堆且要求，要将两堆合并为一堆且要求从小到大排序从小到大排序。 将两堆最上面的抽出将两堆最上面的抽出(设为设为C1，C2)比较大小，将比较大小，将小者置于一边作为新的一堆小者置于一边作为新的一堆(不妨设不妨设C1C2)；再从第再从第一堆中抽出一张继续与一堆中抽出一张继续与C2进行比较，将较小的放置进行比较，将较小的放置在新堆的最下面在新堆的最下面； 重复上述过程重复上述过程，直到某一堆已抽完，直到某一堆已抽完，然后将剩下然后将剩下一堆中的所有牌转移到新堆中。

60、一堆中的所有牌转移到新堆中。1 排序思想排序思想 初始时，将每个记录看成一个单独的有序序列，初始时，将每个记录看成一个单独的有序序列，则则n个待排序记录就是个待排序记录就是n个长度为个长度为1的有序子序列的有序子序列； 对所有有序子序列进行两两归并，得到对所有有序子序列进行两两归并，得到 n/2 个长个长度为度为2或或1的有序子序列的有序子序列一趟归并一趟归并； 重复重复 ，直到得到长度为，直到得到长度为n的有序序列为止的有序序列为止。 上述排序过程中，子序列总是上述排序过程中，子序列总是两两归并两两归并，称为，称为2-路路归并排序归并排序。其核心是如何将相邻的两个子序列归并成一其核心是如何将

61、相邻的两个子序列归并成一个子序列个子序列。设。设相邻的两个子序列分别为相邻的两个子序列分别为：Rk, Rk+1, , Rm和和Rm+1, Rm+2, Rh，将，将它们归并为一个有序的子序列它们归并为一个有序的子序列：DRl, DRl+1, , DRm, DRm+1, , DRh 例：例：设有设有9个待排序的记录个待排序的记录，关键字分别为，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，归并归并排序的过程如图排序的过程如图9-11所示。所示。图图9-11 归并排序过程归并排序过程23 38 22 45 23 67 31 15 41初始关键字初始关键字:23 3

62、8 22 45 23 67 15 31 41一趟归并后一趟归并后:22 23 38 45 15 23 31 67 41二趟归并后二趟归并后:15 22 23 23 31 38 45 67 41三趟归并后三趟归并后:15 22 23 23 31 38 41 45 67四趟归并后四趟归并后:归并的算法归并的算法void Merge(RecType R, RecType DR, int k, int m, int h) int p, q, n ; p=n=k, q=m+1 ;while (p=m)&(q=h) if (LQ(Rp.key, Rq.key) ) /* 比较两个子序列比较两个子序列 */

63、 DRn+=Rp+ ;else DRn+=Rq+ ;while (p=m) /* 将剩余子序列复制到结果序列中将剩余子序列复制到结果序列中 */DRn+=Rp+ ;while (qd：再调用一次上述过程：再调用一次上述过程，将一，将一个长度为个长度为d的子的子序列和不足序列和不足d的子序列进行归并的子序列进行归并； 剩下的元素个数剩下的元素个数d：将剩下的元素依次复制到归将剩下的元素依次复制到归并后的序列中并后的序列中。 一趟归并排序算法一趟归并排序算法void Merge_pass(RecType R, RecType DR, int d, int n) int j=1 ;while (j+

64、2*d-1)=n) Merge(R, DR, j, j+d-1, j+2*d-1) ;j=j+2*d ; /* 子序列两两归并子序列两两归并 */if (j+d-1n) /* 剩余元素个数超过一个子序列长度剩余元素个数超过一个子序列长度d */Merge(R, DR, j, j+d-1, n) ;else Merge(R, DR, j, n, n) ;/* 剩余子序列复制剩余子序列复制 */ 归并排序的算法归并排序的算法 开始归并时，每个记录是长度为开始归并时，每个记录是长度为1的有序子序列，的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列对这些有序子序列逐趟归并，每一趟归并后有

65、序子序列的长度均扩大一倍的长度均扩大一倍；当当有序子序列的长度与整个记录序有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列列长度相等时，整个记录序列就成为有序序列。算法是。算法是：void Merge_sort(Sqlist *L, RecType DR) int d=1 ;while(dlength) Merge_pass(L-R, DR, d, L-length) ;Merge_pass(DR, L-R, 2*d, L-length) ;d=4*d ;3 算法分析算法分析 具有具有n个待排序记录的归并次数是个待排序记录的归并次数是2n，而而一趟归一趟归并的时间复杂度为并

66、的时间复杂度为O(n)，则整个归并排序的则整个归并排序的时间复杂度时间复杂度无论是最好还是最坏情况均为无论是最好还是最坏情况均为O(n2n)。在排序过程中，在排序过程中，使用了辅助向量使用了辅助向量DR，大小与待排序记录空间相同大小与待排序记录空间相同，则，则空空间复杂度为间复杂度为O(n)。归并排序是稳定的归并排序是稳定的。9. 6 基数排序基数排序 基数排序基数排序(Radix Sorting) 又称为又称为桶排序桶排序或或数字数字排序排序：按待排序记录的关键字的组成成分按待排序记录的关键字的组成成分(或或“位位”)进进行排序行排序。 基数排序基数排序和前面的各种内部排序方法完全不同和前面

67、的各种内部排序方法完全不同，不不需要进行关键字的比较和记录的移动。借助于多关键字需要进行关键字的比较和记录的移动。借助于多关键字排序思想实现单逻辑关键字的排序。排序思想实现单逻辑关键字的排序。9.6.1 多关键字排序多关键字排序 设有设有n个记录个记录R1, R2, ,Rn， 每个记录每个记录Ri的关的关键字是由若干项键字是由若干项(数据项数据项)组成，即记录组成，即记录Ri的关键字的关键字Key是若干项的集合：是若干项的集合： Ki1, Ki2, ,Kid(d1) 。 记录记录R1, R2, ,Rn有序的，指的是有序的，指的是 i, j1,n，ij ，若记录的关键字满足：，若记录的关键字满足

68、：Ki1, Ki2, Kid=0; j-) /* 关键字的每位一趟排序关键字的每位一趟排序 */ for (k=0; kkeyj) ; /* 取关键字的第取关键字的第j位位kj */ if (fm=NULL) fm=p ; else em-next=p ; p=p-next ; head=NULL ; /* 以以head作为头指针进行收集作为头指针进行收集 */ q=head ; /* q作为收集后的尾指针作为收集后的尾指针 */for (k=0; knext=fk ; else head=fk ; q=ek ; /* 完成一趟排序的收集完成一趟排序的收集 */q-next=NULL ; /*

69、 修改收集链尾指针修改收集链尾指针 */4 算法分析算法分析 设有设有n个待排序记录个待排序记录，关键字位数为关键字位数为d，每位有每位有r种种取值取值。则排序的趟数是则排序的趟数是d；在每在每一趟中：一趟中： 链表初始化的时间复杂度：链表初始化的时间复杂度：O(r) ； 分配的时间复杂度：分配的时间复杂度：O(n) ； 分配后收集的时间复杂度：分配后收集的时间复杂度：O(r) ； 则链式基数排序的则链式基数排序的时间复杂度为：时间复杂度为： O(d(n+r) 在排序过程中使用的辅助空间是在排序过程中使用的辅助空间是：2r个链表个链表指针指针， n个指针域个指针域空间，空间，则则空空间复杂度为

70、：间复杂度为：O(n+r) 基数排序是稳定的基数排序是稳定的。9. 7 各种内部排序的比较各种内部排序的比较 各种内部排序按所采用的基本思想各种内部排序按所采用的基本思想(策略策略)可分为：可分为：插入排序插入排序、交换交换排序排序、选择选择排序排序、归并归并排序排序和和基基数数排序排序，它们的基本策略分别是：，它们的基本策略分别是：1 插入排序插入排序：依次将无序序列中的一个依次将无序序列中的一个记录记录，按关按关键字值的大小插入到已键字值的大小插入到已排好序排好序一个子序列的适当位置一个子序列的适当位置，直到所有的记录都插入为止直到所有的记录都插入为止。具体的方法有。具体的方法有：直接插入

71、：直接插入、表表插入插入、2-路路插入和插入和shell排序排序。2 交换交换排序排序：对于待排序记录序列中的记录对于待排序记录序列中的记录，两两两两比较记录的关键字比较记录的关键字，并对反序的两个记录进行交换，直，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。到整个序列中没有反序的记录偶对为止。具体的方法有具体的方法有：冒泡排序冒泡排序、快速、快速排序排序。3 选择选择排序排序：不断地从不断地从待排序的记录序列待排序的记录序列中选取关中选取关键字最小的键字最小的记录，放在已记录，放在已排好序的序列排好序的序列的最后的最后，直到所，直到所有记录都被选取为止有记录都被选取为止

72、。具体的方法有。具体的方法有：简单选择排序：简单选择排序、堆堆排序排序。4 归并归并排序排序：利用利用“归并归并”技术不断地对待排序记技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序录序列中的有序子序列进行合并，直到合并为一个有序序列为止序列为止。5 基数排序基数排序：按待排序记录的关键字的组成成分按待排序记录的关键字的组成成分(“位位”)从低到高从低到高(或从高到低或从高到低)进行进行。每次是按记录关。每次是按记录关键字某一键字某一“位位”的值将所有记录分配到相应的的值将所有记录分配到相应的桶中，再桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序按桶的编号依次将记

73、录进行收集，最后得到一个有序序列列。 各种内部排序方法的性能比较如下表各种内部排序方法的性能比较如下表。方法方法平均时间平均时间最坏所需时间最坏所需时间附加空间附加空间稳定性稳定性直接插入直接插入O(n2)O(n2)O(1)稳定的稳定的Shell排序排序O(n1.3)O(1)不稳定的不稳定的直接选择直接选择O(n2)O(n2)O(1)不稳定的不稳定的堆堆排序排序O(n2n)O(n2n)O(1)不稳定的不稳定的冒泡冒泡排序排序O(n2)O(n2)O(1)稳定的稳定的快速排序快速排序O(n2n)O(n2)O(2n)不稳定的不稳定的归并排序归并排序O(n2n)O(n2n)O(n)稳定的稳定的基数排序

74、基数排序O(d(n+r)O(d(n+r)O(n+r)稳定的稳定的表表9-1 主要内部排序方法的性能主要内部排序方法的性能 本章中讨论的排序方法是在顺序存储结构上实现的本章中讨论的排序方法是在顺序存储结构上实现的，在排序过程中需要移动大量记录。当记录数很多、在排序过程中需要移动大量记录。当记录数很多、时间耗时间耗费很大费很大时时，可以采用静态链表作为存储结构，可以采用静态链表作为存储结构。但有些排序。但有些排序方法方法，若采用静态链表作存储结构，则无法实现表排序，若采用静态链表作存储结构，则无法实现表排序。选取排序方法的主要考虑因素：选取排序方法的主要考虑因素： 待排序的记录数目待排序的记录数目n； 每个记录的大小每个记录的大小； 关键字的结构及其初始状态；关键字的结构及其初始状态； 是否要求排序的稳定性；是否要求排序的稳定性； 语言工具的特性；语言工具的特性； 存储结构的初始条件和要求；存储结构的初始条件和要求； 时间复杂度时间复杂度、空间复杂度和开发工作的复杂程度的空间复杂度和开发工作的复杂程度的平衡点等。平衡点等。作作 业业P273-P274：1，2，6，7，10