数据结构排序

1、第第10章章 排序排序 排序是数据处理过程中经常使用的一种重要的运算，排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内部排序的各种算法，排序的方法有很多种，本章主要讨论内部排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。等进行了讨论。 10.1 概述概述 假设一个文件是由假设一个文件是由n个记录个记录R1，R2，Rn组成，所谓排序就是组成，所谓排序就是以记录中某个以记录中某个(或几个或几个)字段值不减字段值不减“正序正序”(或不增或不增“逆序逆序”)的次序将的次序将这这n个记录重新

2、排列，称该字段为个记录重新排列，称该字段为排序码排序码。能唯一标识一个记录的字。能唯一标识一个记录的字段称为段称为关键字关键字，关键字可以作为关键字可以作为排序码排序码，但，但排序码排序码不一定要是关键字不一定要是关键字。 根据排序过程中使用到的存储介质，可以将排序分成两大类根据排序过程中使用到的存储介质，可以将排序分成两大类:内部排序内部排序和和外部排序外部排序。 内部排序内部排序是指在排序过程中所有数据均放在内存中处理，不需要是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况

3、下，则还需要使用外存，这种排序方法称为况下，则还需要使用外存，这种排序方法称为外部排序外部排序。 排序码相同的记录，若经过排序后，这些记录仍保持原来的排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个相对次序不变，称这个排序算法是稳定的排序算法是稳定的。否则，称为。否则，称为排序算法排序算法是不稳定的是不稳定的。 内部排序算法的分类与性能分析：内部排序算法的分类与性能分析： 内部排序算法大致可分为内部排序算法大致可分为5类：类： (1) 插入排序插入排序 (2) 交换排序交换排序 (3) 选择排序选择排序 (4) 归并排序归并排序 (5) 基数排序基数排序 内部排序算法的

4、分类也可以从算法执行所需的时间，即根据排序内部排序算法的分类也可以从算法执行所需的时间，即根据排序过程中的过程中的比较次数和移动次数比较次数和移动次数来划分。一般可以分为来划分。一般可以分为3类：类： (1) 简单的排序算法，其时间复杂度为简单的排序算法，其时间复杂度为O(n2)； (2) 先进的排序算法，其时间复杂度为先进的排序算法，其时间复杂度为O(n log n)； (3) 基数排序，其时间复杂度为基数排序，其时间复杂度为O(d n)；内部排序算法的分类与性能分析：内部排序算法的分类与性能分析： 采用不同的存储结构，对排序算法的记录采用不同的存储结构，对排序算法的记录移动次数移动次数也有

5、影响。也有影响。 (1) 如果采用线性表的顺序存储结构如果采用线性表的顺序存储结构(数组数组)，则在排序过程中记，则在排序过程中记录的移动是避免不了的。录的移动是避免不了的。 (2) 若采用线性链表，则可避免移动记录，只需修改指针即可。若采用线性链表，则可避免移动记录，只需修改指针即可。这种排序称为这种排序称为链表排序链表排序。 (3) 记录采用顺序存储，另设一个地址数组，排序时只对地址数记录采用顺序存储，另设一个地址数组，排序时只对地址数组操作，不对记录操作，这种排序称为组操作，不对记录操作，这种排序称为地址排序地址排序。 (如：索引文件如：索引文件)在本章讨论排序算法时，记录存储采用在本章

6、讨论排序算法时，记录存储采用顺序表结构顺序表结构，记录按，记录按排序码排序码（关键字）（关键字）进行进行“正序正序”排序，排序码均为整数。有关定义如下排序，排序码均为整数。有关定义如下 ：#define MAXSIZE 20 /文件中记录个数的最大值文件中记录个数的最大值 typedef int KeyType; /定义关键字类型为整数类型定义关键字类型为整数类型 typedef struct KeyType key; /记录的关键字记录的关键字 InfoType otherinfo; /记录中其它数据项记录中其它数据项 RecordType; /记录类型记录类型 typedef struct

7、 RecordType rMAXSIZE+1; /r0闲置或用作闲置或用作“哨兵哨兵”单元单元 int length; /记录的个数记录的个数 SqList; /顺序表的类型顺序表的类型 10.2 插入排序插入排序 插入排序的基本思想是插入排序的基本思想是: 将待排序表中的记录，将待排序表中的记录， 逐个地按其关键字值的大小插入到目前已逐个地按其关键字值的大小插入到目前已经排好序的若干个记录组成的表中的适当位置，并保持新表中记录有序。经排好序的若干个记录组成的表中的适当位置，并保持新表中记录有序。10.2.1 直接插入排序直接插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可认

8、为表中的第初始可认为表中的第1个记录己排好序，个记录己排好序，然后将第然后将第2个到第个到第n个记录依次插入已排序的记录组成的表中。在对第个记录依次插入已排序的记录组成的表中。在对第i个记录个记录Ri进行插入时，进行插入时，R1，R2，Ri-1已排序，将记录已排序，将记录Ri的关键字的关键字keyi与已经排好序的关键字从右向左依次比较，找到与已经排好序的关键字从右向左依次比较，找到Ri应插入的位置，应插入的位置，将该位置以后直到将该位置以后直到Ri-1各记录顺序后移，空出该位置让各记录顺序后移，空出该位置让Ri插入。插入。 一组记录的关键字分别为一组记录的关键字分别为:312，126，272，

9、226，28，165，123 初始时将第初始时将第1个关键字作为已经排好序的，把排好序的数据记录放个关键字作为已经排好序的，把排好序的数据记录放入中括号入中括号中，表示有序表，剩下的在中括号外，如下所示：中，表示有序表，剩下的在中括号外，如下所示：312，126，272，226，28，165，123 设前设前3个记录的关键字已重新排列有序，构成一个含有个记录的关键字已重新排列有序，构成一个含有3个记录的个记录的有序表有序表:126，272，312，226，28，165，123 现在要将第现在要将第4个关键字个关键字226插入插入 ！直接插入排序的过程：直接插入排序的过程：126，272，312

10、，226，28，165，123现在要将第现在要将第4个关键字个关键字226插入插入 ！ 将待插入的关键字将待插入的关键字226和已经有序的最后一个关键字和已经有序的最后一个关键字312比较，因比较，因为待插入的为待插入的关键字关键字226小于小于312，所以，所以226肯定要置于肯定要置于312的前面，至于的前面，至于是否就是置于是否就是置于312的前一个位置，此时还不能确定，需要继续向左比较；的前一个位置，此时还不能确定，需要继续向左比较； 将所有大于待插入关键字将所有大于待插入关键字226的那两个关键字的那两个关键字312和和272依次后移依次后移一个位置，在空出的位置插入待排序的关键字一

11、个位置，在空出的位置插入待排序的关键字226，得一含有，得一含有4个记录个记录的有序表：的有序表： 126，226，272，312，28，165，123 直接插入排序的过程直接插入排序的过程(续续)：void InsertSort(SqList &L) for (i=2; i=L.length; i+) /依次插入从第依次插入从第2个开始的所有元素个开始的所有元素 if (L.ri.key L.ri-1.key) L.r0 = L.ri; /设置哨兵设置哨兵(将当前记录存入将当前记录存入0元素元素) L.ri = L.ri-1; /将有序表中的记录后移一个位置将有序表中的记录后移一个位置 fo

12、r (j = i-2; L.r0.key L.rj.key; -j) L.rj+1=L.rj; /将有序表中的记录继续后移一个位置将有序表中的记录继续后移一个位置 L.rj+1 = L.r0; /将当前记录插入到指定位置将当前记录插入到指定位置 /InsertSort直接插入排序算法：直接插入排序算法：该算法是该算法是稳定的！稳定的！ 设待排序的设待排序的7记录的关键字为记录的关键字为312，126，272，226，28，165，123，直接插入排序算法的执行过程如下：直接插入排序算法的执行过程如下： 哨兵哨兵 关键字关键字初始初始 （）（） 312，126，272，226，28，165，12

13、3i=2： （126） 126，312，272，226，28，165，123i=3： （272） 126，272，312，226，28，165，123i=4： （226） 126，226，272，312，28，165，123i=5： （28） 28，126，226，272，312，165，123i=6： （165） 28，126，165，226，272，312，123i=7： （123） 28，123，126，165，226，272，312直接插入排序算法的执行过程直接插入排序算法的执行过程直接插入排序算法执行时间的分析：直接插入排序算法执行时间的分析：最好的情况最好的情况 ： 即初始关键字开

14、始就是正序即初始关键字开始就是正序(递增递增)的情况下，该算法外循环共执行的情况下，该算法外循环共执行n-1次，其循环体内由于条件不成立，不需要进行移动操作。所以在最次，其循环体内由于条件不成立，不需要进行移动操作。所以在最好情况下，直接插入排序算法的比较次数为好情况下，直接插入排序算法的比较次数为(n-1)次，移动次数为次，移动次数为0次。次。 最坏的情况最坏的情况 ： 即初始关键字开始是逆序即初始关键字开始是逆序(递减递减)的情况下，当插入第的情况下，当插入第i个关键字时，个关键字时，该算法内循环要执行该算法内循环要执行i-1次，每次要移动次，每次要移动1个记录，而外循环体要执行个记录，而

15、外循环体要执行n-l次，在循环体内不含内循环每次循环要进行次，在循环体内不含内循环每次循环要进行3次移动操作，所以在最次移动操作，所以在最坏情况下，比较次数为坏情况下，比较次数为2+n=(n+2)(n-1)/2，移动次数为，移动次数为(3+4+n+1) =(n+4)(n-1)/2。 若待排序的记录以各种排列出现的概率相同，则可取上述最小值若待排序的记录以各种排列出现的概率相同，则可取上述最小值和最大值的平均值作为直接插入排序算法的比较次数和移动次数，约和最大值的平均值作为直接插入排序算法的比较次数和移动次数，约为为n2/4。由此，直接插入排序算法的时间复杂度为。由此，直接插入排序算法的时间复杂

16、度为O(n2)。 10.2.2 其他插入排序其他插入排序 1. 折半插入排序折半插入排序 根据插入排序的基本思想，在找第根据插入排序的基本思想，在找第i个记录的插入位置时，前个记录的插入位置时，前i-l个记录已排序，将第个记录已排序，将第i个记录的关键字个记录的关键字key和已排序的前和已排序的前i-1个的中间个的中间位置记录的关键字进行比较，如果位置记录的关键字进行比较，如果key小于中间位置记录关键字，则小于中间位置记录关键字，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定查找，直到查找

17、范围为空，即可确定key的插入位置。的插入位置。 当当n较大时，折半插入排序的比较次数远少于直接插入排序的平较大时，折半插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，故折半插入排序的均比较次数，但二者所要进行的移动次数相等，故折半插入排序的时间复杂度也是时间复杂度也是O(n2) 。 void BInsertSort(SqList &L) for(i=2; i=L.length; i+) /依次插入从第依次插入从第2个开始的所有元素个开始的所有元素 L.r0 = L.ri; /保存待插入的元素保存待插入的元素 low=1; high = i-1; while(

18、low = high) /在在rlow.high中查找有序插入的位置中查找有序插入的位置 mid=(low+high)/2; /折半折半 if(L.r0.key =low; -j) L.rj+1=L.rj; /记录后移记录后移 L.rlow = L. r0; /插入插入 / for/ BInsertSort折半插入排序算法折半插入排序算法 2. 2-路插入排序路插入排序 2-路插入排序是在折半插入排序的基础，对插入排序中移动元素路插入排序是在折半插入排序的基础，对插入排序中移动元素的操作进行改进。其基本思想是：将插入区域分成大致等长的两段，的操作进行改进。其基本思想是：将插入区域分成大致等长的

19、两段，选择性地插入到其中一段。选择性地插入到其中一段。具体过程如下：具体过程如下：01234563428817922165534first final3428first final348128first final34798128first final3479812228first final347981162228first final34557981162228first final3. 表插入排序表插入排序 折半插入排序比较次数通常比直接插入排序的比较次数少，但移动折半插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有次数

20、相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。关信息的改变来达到排序的目的。 给每个记录附设一个所谓的指针域给每个记录附设一个所谓的指针域next，它的类型为整型，表插入，它的类型为整型，表插入排序的思路：在插入第排序的思路：在插入第i个记录个记录Ri时，时，R1，R2，Ri-1已经通过各自的已经通过各自的指针域指针域next按关键字不减的次序连接成一个（静态链）表，将记录按关键字不减的次序连接成一个（静态链）表，将记录Ri的的关键字关键字keyi与表中已经排好序的关键字从表头向右、或称向后依次比较，与表中已经排好序的关键字从表头向右、或称向后依次比较

21、，找到找到Ri应插入的位置，将其插入在表中，使表中各记录的关键字仍然有应插入的位置，将其插入在表中，使表中各记录的关键字仍然有序。序。 #define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/typedef struct RecordType rc;/记录项记录项 int next;/指针项指针项 SLNode; /表结点类型表结点类型typedef struct SLNode rMAXSIZE; /0号单元为表头结点号单元为表头结点 int length; /链表长度链表长度(记录数记录数) SLinkList; /静态链表类型静态链表类型 表插入排序的存

22、储结构表插入排序的存储结构 初始时，初始时，r0.next用于存放表中第用于存放表中第1个记录的下标，个记录的下标， r0.next的值为的值为1，排序结束时，排序结束时，r0.next中存放的是所有关键字中值最小的对应记录的下标，中存放的是所有关键字中值最小的对应记录的下标，其它的关键字记录通过各自的指针域其它的关键字记录通过各自的指针域next按不减的次序连接成一个（静态按不减的次序连接成一个（静态链）表，最大的关键字记录的链）表，最大的关键字记录的next为为0。 具体过程如下：具体过程如下：表插入排序算法表插入排序算法4938659776132749201-初初始始012345678i

23、=2493865977613274923140-i=34938659776132749231504-49386597761327496315042-i=6493865977613274963150472-i=7493865977613274910-49386597761327492310-i=44938659776132749681504723i=8i=5012345678void TableInsertSort(SLinkList &SL) SL.r0.next = 1; SL.r1.next = 0; /第第1个元素为有序静态表个元素为有序静态表 for(i=2; i=SL.length;

24、 i+) /依次插入从第依次插入从第2个开始的所有元素个开始的所有元素q=0; p=SL.r0.next; /p指向表中第指向表中第1个元素，个元素，q指向指向p的前驱元素位置的前驱元素位置 while(p!=0 & (SL.rp.rc.key SL.ri.rc.key) /找插入位置找插入位置 q=p; p=SL.rp.next; /继续查找继续查找 /while SL.ri.next=p; SL.rq.next=i; /将第将第i个元素插入个元素插入q和和p所指向的元素之间所指向的元素之间 /for/TableInsertSort表插入排序算法表插入排序算法(续续)10.2.3 Shell

25、(希尔希尔)排序排序 Shell排序的基本思想是：对排序的基本思想是：对n个记录进行排序，首先取一个整数个记录进行排序，首先取一个整数d=1) for(i=d+1; i=L.length; i+) /从第从第d+1个元素开始个元素开始,将所有元素有序插入相应分组中将所有元素有序插入相应分组中 L.r0=L. ri; /保存第保存第i个元素个元素 j=i-d; /向前找插入位置向前找插入位置 while( L.r0.key 0) /找插入位置并后移找插入位置并后移 L.rj+d=L.rj; /后移后移j=j-d; /继续向前查找继续向前查找 /while L.rj+d=L.r0; /插入第插入第

26、i个元素个元素 / for d=d/2; /while/ShellSortShell排序算法排序算法Shell排序的分析是一个排序的分析是一个复杂的数学问题，算法复杂的数学问题，算法的时间复杂度与增量的时间复杂度与增量d有有关。一般是关。一般是O(n3/2)。对于。对于增量增量d，尽量取素数，且，尽量取素数，且最后最后d=1。10.3 交换排序交换排序交换排序的基本思路：交换排序的基本思路： 对待排序记录两两进行关键字比较，若不满足排序顺序则交换对待排序记录两两进行关键字比较，若不满足排序顺序则交换这对记录，直到任何两个记录的关键字都满足排序要求为止。这对记录，直到任何两个记录的关键字都满足排

27、序要求为止。 冒泡排序冒泡排序(Bubble Sort)的基本思想为：的基本思想为： 第第1趟，对所有记录从左到右每相邻两个记录的关键字进行比较，趟，对所有记录从左到右每相邻两个记录的关键字进行比较，如果这两个记录的关键字不符合排序要求，则进行交换，这样一趟做如果这两个记录的关键字不符合排序要求，则进行交换，这样一趟做完，将关键字最大者放在最后一个位置；完，将关键字最大者放在最后一个位置； 第第2趟，对剩下的趟，对剩下的n-l个待排序记录重复上述过程，又将一个关键字个待排序记录重复上述过程，又将一个关键字放于最终位置，反复进行放于最终位置，反复进行n-l次，可将次，可将n-l个关键字对应的记录

28、放至最终个关键字对应的记录放至最终位置，剩下的即为关键字最小的记录，它在第位置，剩下的即为关键字最小的记录，它在第1的位置处。的位置处。 如果在某一趟中，没有发生交换，则说明此时所有记录已经按排如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。序要求排列完毕，排序结束。 10.3.1 冒泡排序冒泡排序 void BubbleSort(SqList &L) i=1; done=1; while(i=L.length & done) /最多进行最多进行length次冒泡，如没有发生交换则结束次冒泡，如没有发生交换则结束 done=0; for(j=1; j=L.le

29、ngth-i; j+) if (L.rj+1.keyL.rj.key) /两个记录不符合排序规则两个记录不符合排序规则 L.r0 = L.rj; /交换两个记录位置交换两个记录位置 L.rj = L.rj+1; L. rj+1 = L.r0;done=1; /if i+; /while/BubbleSort冒泡排序算法冒泡排序算法该算法是稳定的！该算法是稳定的！时间复杂度与插入时间复杂度与插入算法一样。算法一样。例如：待排序的例如：待排序的9个记录的关键字序列为个记录的关键字序列为312，126，272，226，8，165，123，12，28，使用冒泡排序算法进行的排序过程如下图所示：，使用冒

30、泡排序算法进行的排序过程如下图所示： 10.3.2 快速排序快速排序 快速排序快速排序(Quick Sort)是对冒泡排序的一种改进，它的基本思想是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将待排序的记录分割成独立的两部分，其中一部分是：通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均小于另一部分记录的关键字，然后分别对这两部分记记录的关键字均小于另一部分记录的关键字，然后分别对这两部分记录继续进行排序，以达到整个序列有序。录继续进行排序，以达到整个序列有序。 快速排序的实现方法是：从快速排序的实现方法是：从n个待排序的记录中任取一个记录个待排序的记录中任取一个记

31、录(不不妨取第妨取第1个记录，该记录称为个记录，该记录称为枢轴枢轴或或支点支点)，将该记录放置于排序后它，将该记录放置于排序后它最终应该放的位置，使它前面的记录关键字都不大于它的关键字，而最终应该放的位置，使它前面的记录关键字都不大于它的关键字，而后面的记录关键字都大于它的关键字，这个过程称为后面的记录关键字都大于它的关键字，这个过程称为一趟快速排序一趟快速排序（或一次划分或一次划分）。然后对前、后两部分待排序记录重复上述过程，可）。然后对前、后两部分待排序记录重复上述过程，可以将所有记录放于排序成功后的相应位置，排序即告完成。以将所有记录放于排序成功后的相应位置，排序即告完成。 一趟快速排序

32、一趟快速排序(划分划分)的具体做法是：附设两个指针的具体做法是：附设两个指针low和和high，其，其初值分别是初值分别是1和和L.length，设枢轴记录的关键字为，设枢轴记录的关键字为pivotkey，其初值为，其初值为low指针所指记录的关键字。首先从指针所指记录的关键字。首先从high位置起向前搜索找到第一个关位置起向前搜索找到第一个关键字小于键字小于pivotkey的记录和枢轴记录互相交换，然后从的记录和枢轴记录互相交换，然后从low所指位置起所指位置起向后搜索，找到第一个关键字大于向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交的记录和枢轴记录互相交换，重复这两

33、步直至换，重复这两步直至low=high为止。具体算法如下：为止。具体算法如下：1. 快速排序的实现快速排序的实现 int Partition (SqList &L, int low, int high) pivotkey = L.rlow.key; while (low high) while (low = pivotkey) - -high;L.rlow L.rhigh; /两个记录互换位置两个记录互换位置while (low high & L.rlow.key = pivotkey) +low;L.rlow L.rhigh; /两个记录互换位置两个记录互换位置 return low;/

34、Partition 设待排序的设待排序的7个记录的关键字序列为个记录的关键字序列为126，272，12，165，123，12，28，一次划分的过程如图所示：，一次划分的过程如图所示： 初始状态：初始状态：pivoekey=126126272121651231228lowhigh282721216512312126lowhigh第第1次循环次循环 281261216512312272lowhigh281212165123126272lowhigh第第2次循环次循环 281212126123165272lowhigh281212123126165272lowhigh第第3次循环次循环 281212

35、123126165272lowhigh快速排序快速排序是不稳定是不稳定的！的！因此，上述因此，上述7个记录的关键字个记录的关键字 126，272，12，165，123，12，28经经快速排序后的结果如下：快速排序后的结果如下： 第第1次划分后：次划分后：28，12，12，123，126，165，272第第2次划分后：次划分后：12，12，28，123 ，126， 165，272第第3次划分后：次划分后：12，12，28，123，126 ，165，272第第4次划分后：次划分后：12， 12 ，28，123，126 ，165，272void QuickSort(SqList &L, int lo

36、w, int high) if (low high) pivotloc = Partition(L, low, high);QuickSort(L, low, pivotloc-1); /对低端子表递归调用本函数对低端子表递归调用本函数 QuickSort(L, pivotloc+1, high); /对高端子表递归调用本函数对高端子表递归调用本函数 /QuickSort2. 快速排序算法快速排序算法 int Partition (SqList &L, int low, int high) /改进的一趟排序算法改进的一趟排序算法 L.r0 = L.rlow; pivotkey = L.rlow

37、.key; while (low high) while (low = pivotkey) -high;L.rlow = L.rhigh; /两个记录互换位置两个记录互换位置while (low high & L.rlow.key = pivotkey) +low;L.rhigh = L.rlow; /两个记录互换位置两个记录互换位置 L.rlow = L.r0; return low;/ Partition 快速排序算法的时快速排序算法的时间复杂度是间复杂度是O(nlogn)。是该量级平均性能是该量级平均性能最好的算法。最好的算法。10.4 选择排序选择排序 选择排序的基本思想是：每次从待排

38、序的文件中选择出关键字最选择排序的基本思想是：每次从待排序的文件中选择出关键字最小的记录，将该记录放于已排序文件的指定位置，直到已排序文件记小的记录，将该记录放于已排序文件的指定位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。录个数等于初始待排序文件的记录个数为止。 10.4.1 简单简单(直接直接)选择排序选择排序 首先从所有首先从所有n个待排序记录中选择关键字最小的记录，将该记录与个待排序记录中选择关键字最小的记录，将该记录与第第1个记录交换，再从剩下的个记录交换，再从剩下的n-l个记录中选出关键字最小的记录和第个记录中选出关键字最小的记录和第2个记录交换。重复这样的操作直到

39、剩下个记录交换。重复这样的操作直到剩下2个记录时，再从中选出关键字个记录时，再从中选出关键字最小的记录和第最小的记录和第n-1个记录交换。剩下的那个记录交换。剩下的那1个记录肯定是关键字最大个记录肯定是关键字最大的记录，这样排序即告完成。的记录，这样排序即告完成。 void SimpleSelectSort(SqList &L) for (i=1; i=L.length-1; i+) k=i; /记下当前最小元素的位置记下当前最小元素的位置 for (j=i+1; j=L.length; j+) /向右查找更小的元素向右查找更小的元素 if (L.rj.key aj+1或者或者ajaj+1或者

40、或者ajaj+1很明显不包很明显不包括相等的情况，所以如果两个元素相等，他们不会交换；所以，括相等的情况，所以如果两个元素相等，他们不会交换；所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以好序后的顺序，所以插入排序是稳定的插入排序是稳定的。内部排序算法的稳定性分析内部排序算法的稳定性分析(4)快速排序快速排序 快速排序有两个方向，快速排序有两个方向， high下标一直往左走，直到下标一直往左走，直到 ahigh alow交换两个元素，然后交换两个元素，然后 low下标一直往右走，直到下标一直往右走，直到

41、alow ahigh交交换两个元素。重复上述过程，直到换两个元素。重复上述过程，直到low=high，完成一趟快速排序。，完成一趟快速排序。在在alow和和ahigh交换的时候，很有可能把前面的元素的稳定性打交换的时候，很有可能把前面的元素的稳定性打乱。乱。 比如序列为比如序列为5,3,3,4,3,8,9,10,11，现在中枢元素，现在中枢元素5和和3(第第5个元素，个元素，下标从下标从1开始计开始计)交换就会把元素交换就会把元素3的稳定性打乱，所以的稳定性打乱，所以快速排序是一快速排序是一个不稳定的排序算法个不稳定的排序算法。 内部排序算法的稳定性分析内部排序算法的稳定性分析(5)归并排序归

42、并排序 归并排序是把一个有归并排序是把一个有n个无序关键码看成是由个无序关键码看成是由n个长度为个长度为1的有序的有序表，然后进行两两归并，得到表，然后进行两两归并，得到n/2个长度为个长度为2或或1的有序表，再两的有序表，再两两归并，如此重复，直至最后形成包含两归并，如此重复，直至最后形成包含n个关键码的有序表为止。个关键码的有序表为止。所以，所以，归并排序也是稳定的排序算法归并排序也是稳定的排序算法。(6)基数排序基数排序 基数排序是按照低位先分组，然后收集；再按照高位分组，然后基数排序是按照低位先分组，然后收集；再按照高位分组，然后再收集；依次类推，直到最高位的排序方式。有时候有些属性是

43、再收集；依次类推，直到最高位的排序方式。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。为了减少记录的移动次数，队列可以采用链式存储分配，称前。为了减少记录的移动次数，队列可以采用链式存储分配，称为链队列。为链队列。基数排序基于分组排序，分别收集，所以是稳定的排基数排序基于分组排序，分别收集，所以是稳定的排序算法。序算法。内部排序算法的稳定性分析内部排序算法的稳定性分析(7)希尔排序希尔排序(shell) 希尔排序又称为希尔排序又称为“缩小增量排序缩小增量排序”是按照不同步长对元素进行插是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序入排序，当刚开始元素很无序的时候，步长最