第10章内部排序

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

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

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

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

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

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

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

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

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

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

11、无序部分。：未排好序的无序部分。 显然，在刚开始排序时，显然，在刚开始排序时，R1是已经排好序的。是已经排好序的。 例：例：设有关键字序列为：设有关键字序列为：7, 4, -2, 19, 13, 6，直接插，直接插入排序的过程如下图入排序的过程如下图10-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

12、 19图图10-1 直接插入排序的过程直接插入排序的过程2 算法实现算法实现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。则就整个排序而言：则就整个排序而言：

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

16、1, R2 , Ri-1已排好序，则查找插入已排好序，则查找插入位置可以用位置可以用“折半查找折半查找”实现，则直接插入排序就变成实现，则直接插入排序就变成为折半插入排序。为折半插入排序。 算法实现算法实现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 ; /* 查找插入

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

18、3 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=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)图图10-2 折半插入排序过程折半插入排序过程2 2-路插入排序路插入排序 是对折半插入排序的改进是对折半插入排序的改进，以减少排序

19、过程中移动记以减少排序过程中移动记录的次数。附加录的次数。附加n个记录的辅助空间个记录的辅助空间，方法是，方法是： 另设一个和另设一个和L-R同类型的数组同类型的数组d，L-R1赋给赋给d1，将，将d1看成是排好序的序列中中间位置的记录；看成是排好序的序列中中间位置的记录； 分别将分别将L-R 中的第中的第i个记录依次插入到个记录依次插入到d1之前或之后之前或之后的的有序序列中，具体方法有序序列中，具体方法： L-Ri.keyRi插入到插入到d1之前之前的有序表中；的有序表中； L-Ri.keyd1.key： L-Ri插入到插入到d1之后之后的的有序表中；有序表中；关键点关键点：实现时将实现时

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

21、了优越性。路插入排序就完全失去了优越性。2776d49firstfirstfirstfirstfinalfinalfinalfinal653897971313图图10-3 2-路插入排序过程路插入排序过程3 表插入排序表插入排序前面的插入排序不可避免地要移动记录，若不移动记录前面的插入排序不可避免地要移动记录，若不移动记录就需要改变数据结构。附加就需要改变数据结构。附加n个记录的辅助空间，记录个记录的辅助空间，记录类型修改为：类型修改为：typedef struct RecNode KeyType key ;infotype otherinfo ;int *next;RecNode ;初始化初

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

23、-4所示。所示。 0 1 2 3 4 5 6 7 8key域域next域域MAXINT 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 - - - 和直接插入排序相比，

24、不同的是修改和直接插入排序相比，不同的是修改2n次指针值次指针值以代替移动记录，而关键字的比较次数相同，故时间复以代替移动记录，而关键字的比较次数相同，故时间复杂度为杂度为O(n2)。 表插入排序得到一个有序链表，对其可以方便地进行表插入排序得到一个有序链表，对其可以方便地进行顺序查找，但不能实现随即查找。根据需要，可以对记顺序查找，但不能实现随即查找。根据需要，可以对记录进行重排，记录重排详见录进行重排，记录重排详见P268。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

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

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

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

28、序进行一趟希尔排序, 增量为增量为d */ int j, k ;for (j=d+1; jlength; j+) L-R0=L-Rj ; /* 设置监视哨兵设置监视哨兵 */k=j-d ;while (k0&LT(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 ;fo

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

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

31、22 38 23 45 31 15 41 67第二趟排序后第二趟排序后:22 23 23 38 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

32、 ;for (j=0; jlength; j+) /* 共有共有n-1趟排序趟排序 */ flag=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；移动次数

33、：；移动次数：0； 最坏情况最坏情况(逆序逆序)：比较次数：比较次数：(n-i)=n-1i=1n(n-1)2移动次数：移动次数： 3(n-i)=n-1i=13n(n-1)210.3.2 快速排序快速排序1 排序思想排序思想 通过一趟排序，将待排序记录分割成独立的两部分，通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序再分别对这两部分记录进行下一趟排序，以达到整个序列有序列有序。2 排序过程排序过程 设待排序的记录序列是设待排序的记录序列是Rst ，在

34、记录序列中任取，在记录序列中任取一个记录一个记录(一般取一般取Rs)作为作为参照参照(又称为又称为基准基准或或枢轴枢轴)，以，以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

36、进行比较：进行比较： 若若R0.keyRj.key ：令：令j=j-1，然后继续进行比，然后继续进行比较，较， 直到直到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

37、while (LQ(L-R0.key, L-Rj.key)&(ji) j- ;if (ji) L-Ri=L-Rj ; i+; 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为止为止。 递归算法递归算

38、法 void quick_Sort(Sqlist *L , int low, int high) int k ;if (lowhigh) k=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

39、=0; do while (lowhigh) k=quick_one_pass(L,low,high); stack+top=high ; stack+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

40、) ，即即Tavg(n)=(n+1)/nTavg(n-1)+(2n-1)/nC(n+1)/nTavg(n-1)+2C(n+1)/nn/(n-1)Tavg(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) 从所需要的附加空间来看，快速排序算法是递归调从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当

41、每次划分比较均匀用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为时，栈的最大深度为2n+1 。 快速排序的空间复杂度是：快速排序的空间复杂度是：S(n)=O(2n) 从排序的稳定性来看，快速排序是从排序的稳定性来看，快速排序是不稳定不稳定的。的。10. 4 选择排序选择排序 选择排序选择排序(Selection Sort)的基本思想是：每的基本思想是：每次从当前待排序的记录中选取关键字最小的记录表，然次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。整个记录序列

42、有序为止。 10.4.1 简单选择排序简单选择排序 简单选择排序简单选择排序(Simple Selection Sort ，又称为，又称为直接选择排序直接选择排序)的基本操作是：通过的基本操作是：通过n-i次关键字间的比次关键字间的比较，从较，从n-i+1个记录中选取关键字最小的记录，然后和第个记录中选取关键字最小的记录，然后和第i个记录进行交换，个记录进行交换，i=1, 2, n-1 。1 排序示例排序示例 例：例：设有关键字序列为：设有关键字序列为：7, 4, -2, 19, 13, 6，直接，直接选择排序的过程如下图选择排序的过程如下图10-8所示。所示。图图10-8 直接选择排序的过程

43、直接选择排序的过程初始记录的关键字：初始记录的关键字： 7 4 -2 19 13 6第一趟排序：第一趟排序：-2 4 7 19 13 6第二趟排序：第二趟排序： -2 4 7 19 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 算法实现算法实现void simple_selection_sort(Sqlist *L) int m, n , k;for (m=1; mlength; m+) k=m ; for (n=

44、m+1; nlength; n+) if ( LT(L-Rn.key, L-Rk.key) ) k=n ;if (k!=m) /* 记录交换记录交换 */ L-R0=L-Rm; L-Rm=L-Rk; L-Rk=L-R0; 3 算法分析算法分析 整个算法是二重循环：外循环控制排序的趟数，对整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为个记录进行排序的趟数为n-1趟；内循环控制每一趟的趟；内循环控制每一趟的排序。排序。 进行第进行第i趟排序时，关键字的比较次数为趟排序时，关键字的比较次数为n-i，则：，则：比较次数：比较次数： (n-i)=n-1i=1n(n-1)2 时间复杂

45、度是：时间复杂度是：T(n)=O(n2) 空间复杂度是：空间复杂度是：S(n)=O(1) 从排序的稳定性来看，直接选择排序是从排序的稳定性来看，直接选择排序是不稳定不稳定的。的。10.4.2 树形选择排序树形选择排序 借助借助“淘汰赛淘汰赛”中的对垒就很容易理解树形选择排序中的对垒就很容易理解树形选择排序的思想。的思想。 首先对首先对n个记录的关键字两两进行比较个记录的关键字两两进行比较，选取，选取n/2个较小者；然后这个较小者；然后这n/2个较小者个较小者两两进行比较两两进行比较，选，选取取n/4个较小者个较小者 如此重复，直到只剩如此重复，直到只剩1个关键字为个关键字为止止。该过程可用一棵

46、有该过程可用一棵有n个叶子结点的完全二叉树表示，如个叶子结点的完全二叉树表示，如图图10-9所示。所示。 每个枝结点的关键字都等于其左、右孩子结点中较每个枝结点的关键字都等于其左、右孩子结点中较小的关键字，小的关键字，根结点的关键字就是最小的关键字根结点的关键字就是最小的关键字。 输出最小关键字后，根据输出最小关键字后，根据关系的可传递性关系的可传递性，欲选取次，欲选取次小关键字，只需将叶子结点中的最小关键字改为小关键字，只需将叶子结点中的最小关键字改为“最大最大值值” ，然后重复上述步骤即可。，然后重复上述步骤即可。 含有含有n个叶子结点的完全二叉树的深度为个叶子结点的完全二叉树的深度为2n

47、+1，则总的时间复杂度为则总的时间复杂度为O(n2n) 。492525372828196519153415251515图图10- “淘汰赛淘汰赛”过程示意图过程示意图10.4.3 堆排序堆排序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为根的完全二叉树。为根的完全二叉树。若对该二叉树的结点进行编号若对该二叉树的结点进行编号(从上

48、到下，从左到右从上到下，从左到右)，得到的序列就是将二叉树的结点以得到的序列就是将二叉树的结点以顺序结构存放顺序结构存放，堆的，堆的结构正好和该序列结构完全一致。结构正好和该序列结构完全一致。2 堆的性质堆的性质 堆是一棵采用顺序存储结构的完全二叉树，堆是一棵采用顺序存储结构的完全二叉树， k1是根结点；是根结点； 堆的根结点是关键字序列中的最小堆的根结点是关键字序列中的最小(或最大或最大)值，分别称为值，分别称为小小(或大或大)根堆；根堆； 从根结点到每一叶子结点路径上的元素组成的序列都是从根结点到每一叶子结点路径上的元素组成的序列都是按元素值按元素值(或关键字值或关键字值)非递减非递减(或

49、非递增或非递增)的；的；堆中的任一子树也是堆堆中的任一子树也是堆。 利用堆顶记录的关键字值最小利用堆顶记录的关键字值最小(或最大或最大)的性质，从的性质，从当前待排序的记录中当前待排序的记录中依次选取关键字最小依次选取关键字最小(或最大或最大)的记的记录，就可以实现对数据记录的排序，这种排序方法称为录，就可以实现对数据记录的排序，这种排序方法称为堆排序堆排序。3 堆排序思想堆排序思想 对一组待排序的记录，按堆的定义对一组待排序的记录，按堆的定义建立堆建立堆； 将将堆顶记录和最后一个记录交换堆顶记录和最后一个记录交换位置，则前位置，则前n-1个记录是无序的，而最后一个记录是有序的；个记录是无序的

50、，而最后一个记录是有序的； 堆顶记录堆顶记录被交换后，前被交换后，前n-1个记录不再是堆，需个记录不再是堆，需将前将前n-1个待排序记录重新组织成为一个堆，然后个待排序记录重新组织成为一个堆，然后将将堆顶记录和倒数第二个记录交换堆顶记录和倒数第二个记录交换位置，即将整个位置，即将整个序列中次小关键字值的记录调整序列中次小关键字值的记录调整(排除排除)出无序区；出无序区； 重复上述步骤，直到全部记录排好序为止。重复上述步骤，直到全部记录排好序为止。 结论结论：排序过程中，若采用排序过程中，若采用小根堆小根堆，排序后得到的是，排序后得到的是非递减序列非递减序列；若采用；若采用大根堆大根堆，排序后得

51、到的是，排序后得到的是非递增非递增序列序列。堆排序的关键堆排序的关键 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？成为一个新的堆？ 4 堆的调整堆的调整筛选筛选 堆的调整思想堆的调整思想 输出堆顶元素之后，以堆中最后一个元素替代之；然输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并后将根结点值与左、右子树的根结点值进行比较，并与与其中小者进行交换其中小者进行交换；重复上述操作，直到是叶子结点或；重复上述操作，直到是叶子结点或其关键字值

52、小于等于左、右子树的关键字的值，将得到其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为新的堆。称这个从堆顶至叶子的调整过程为“筛选筛选”，如，如图图10-10所示。所示。注意注意：筛选过程中，根结点的左、右子树都是堆，因筛选过程中，根结点的左、右子树都是堆，因此，筛选是从根结点到某个叶子结点的一次调整过程。此，筛选是从根结点到某个叶子结点的一次调整过程。图图10-10 堆的筛选过程堆的筛选过程49253728196534182715492537281965342718154927372819653425181549253728196534181527 堆调

53、整算法实现堆调整算法实现void Heap_adjust(Sqlist *H, int s, int m)/* H-Rsm中记录关键字除中记录关键字除H-Rs.key均满足堆定义均满足堆定义 */* 调整调整H-Rs的位置使之成为的位置使之成为小根堆小根堆 */ 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

54、 ( LT(H-Rk.key, H-R0.key) ) H-Rj=H-Rk ; j=k ; k=2*j else break ;H-Rj=H-R0 ; 5 堆的建立堆的建立 利用筛选算法，可以将任意无序的记录序列建成一利用筛选算法，可以将任意无序的记录序列建成一个堆，设个堆，设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 ; /* 堆顶与最后一个交换堆顶与最后一个交换

57、 */Heap_adjust(H, 1, j-1) ; 7 算法分析算法分析 主要过程：初始建堆和重新调整成堆。设记录数为主要过程：初始建堆和重新调整成堆。设记录数为n，所对应的完全二叉树深度为所对应的完全二叉树深度为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)

58、筛选调整筛选调整：每次筛选要将根结点：每次筛选要将根结点“下沉下沉”到一个合到一个合适位置。第适位置。第i次筛选时：堆中元素个数为次筛选时：堆中元素个数为n-i+1；堆的；堆的深度是深度是2(n-i+1)+1，则进行，则进行n-1次次“筛选筛选”的比较的比较次数次数C2(n)为：为：C2(n) (22(n-i+1)n-1i=1 C2(n)2n2n 堆排序的比较次数的数量级为：堆排序的比较次数的数量级为： T(n)=O(n2n)；而附加空间就是交换时所用的临时空间，故空间复杂而附加空间就是交换时所用的临时空间，故空间复杂度为：度为： S(n)=O(1) 。10. 5 归并排序归并排序 归并归并(

59、Merging) ：是指将两个或两个以上的有序：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表序列合并成一个有序序列。若采用线性表(无论是那种无论是那种存储结构存储结构)易于实现，其时间复杂度为易于实现，其时间复杂度为O(m+n) 。 归并思想实例归并思想实例：两堆扑克牌，都两堆扑克牌，都已从小到大排好已从小到大排好序序，要将两堆合并为一堆且要求，要将两堆合并为一堆且要求从小到大排序从小到大排序。 将两堆最上面的抽出将两堆最上面的抽出(设为设为C1，C2)比较大小，将比较大小，将小者置于一边作为新的一堆小者置于一边作为新的一堆(不妨设不妨设C1C2)；再从第；再从第一堆中抽出一

60、张继续与一堆中抽出一张继续与C2进行比较，将较小的放置进行比较，将较小的放置在新堆的最下面；在新堆的最下面； 重复上述过程，直到某一堆已抽完，然后将剩下重复上述过程，直到某一堆已抽完，然后将剩下一堆中的所有牌转移到新堆中。一堆中的所有牌转移到新堆中。1 排序思想排序思想 初始时，将每个记录看成一个单独的有序序列，则初始时，将每个记录看成一个单独的有序序列，则n个待个待排序记录就是排序记录就是n个长度为个长度为1的有序子序列；的有序子序列； 对所有有序子序列进行两两归并，得到对所有有序子序列进行两两归并，得到n/2个长度为个长度为2或或1的有序子序列的有序子序列一趟归并一趟归并； 重复重复 ，直到得到长度为，直到得到长度为n的有序