数据结构第9章排序(第25-27讲)

1、第第 9章章排排序序9.1 9.1 排序的基本概念及分类排序的基本概念及分类排序是日常工作和软件设计中常用的运算排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。按照一定的顺序组织成有序序列。例如：将下列关键字序列例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 97排序的主要目的就是实现快速查找。排序的主要目的就是实现快速查找。第第 9章章排排序序一般情况下，一般情况下，假设

2、含假设含n个记录的序列为个记录的序列为R1,R2, ，Rn其相应的关键字序列为其相应的关键字序列为K1,K2, ，Kn这些关键字相互之间可以进行比较，即在这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系它们之间存在着这样一个关系 ： Kp1Kp2Kpn按此固有关系将上式记录序列重新排列为按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。的操作称作排序。姓姓 名名学学 号号性性 别别年龄年龄成绩成绩王小林王小林790631男男1869陈陈 红红790632女女2099刘建平刘建平790633男男2189张立立张立立790634男男1770第第 9章

3、章排排序序(1) 增排序和减排序：如果排序的结果是按关键字增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是从小到大的次序排列的，就是增排序，否则就是减排序。减排序。(2)稳定排序和不稳定排序：稳定排序和不稳定排序：假设假设Ki=Kj（1in，1jn，ij），且在排），且在排序前的序列中序前的序列中Ri领先于领先于Rj（即（即ij）。若在排序）。若在排序后的排序中后的排序中Ri仍领先于仍领先于Rj，即那些具有相同关键，即那些具有相同关键字的记录，经过排序后它们的相对次序仍然保持字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之，若不变

4、，则称这种排序方法是稳定的；反之，若Rj领先于领先于Ri，则称所用的方法是不稳定的。，则称所用的方法是不稳定的。第第 9章章排排序序例：有一组记录为例：有一组记录为(011,张宏张宏,90)，(002,王王强强,89)，(005,魏征魏征,67)，(009,孙燕孙燕,96)，(030,刘花刘花,79)，(021,马新马新,47)，(014,吴吴实实,90)若以成绩为关键字按某种排序方法得到序列为：若以成绩为关键字按某种排序方法得到序列为：(021,马新马新,47)，(005,魏征魏征,67)，(030,刘刘花花,79)，(002,王强王强,89)，(011,张宏张宏,90)，(014,吴实吴实

5、,90)，(009,孙燕孙燕,96)这种排序方法为稳定的排序方法。这种排序方法为稳定的排序方法。若以成绩为关键字按某种排序方法得到序列为：若以成绩为关键字按某种排序方法得到序列为：(021,马新马新,47)，(005,魏征魏征,67)，(030,刘刘花花,79)，(002,王强王强,89)，(014,吴实吴实,90)，(011,张宏张宏,90)，(009,孙燕孙燕,96)这种排序方法为不稳定的排序方法。这种排序方法为不稳定的排序方法。第第 9章章排排序序(3)(3)内部排序和外部排序内部排序和外部排序: :若整个排序过程不需要若整个排序过程不需要访问外存便能完成，则称此类排序问题为访问外存便能

6、完成，则称此类排序问题为内部排内部排序序； 反之，若参加排序的记录数量很大，整个序列的反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问排序过程不可能在内存中完成，则称此类排序问题为题为外部排序外部排序。数据类型说明见教材数据类型说明见教材第第 9章章排排序序插入排序的插入排序的基本思想基本思想是：排序过程中将待排是：排序过程中将待排记录分成有序表和无序表两部分，每次从无记录分成有序表和无序表两部分，每次从无序表中拿出一个待排序的记录，按其关键字序表中拿出一个待排序的记录，按其关键字大小插入到前面已经排好序的有序子表中的大小插入到前面已经排好序的有序子表中的适

7、当位置，直到全部记录插入完成为止。适当位置，直到全部记录插入完成为止。根据不同的插入方法，插入排序算法主要包括：根据不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序和希尔排序等。直接插入排序、折半插入排序和希尔排序等。第第 9章章排排序序9.2.1 直接插入排序直接插入排序基本操作基本操作：将一个记录插入到已排好序的有序表：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增中，从而得到一个新的、记录数增1的有序表。的有序表。第第 9章章排排序序9.2.1 直接插入排序直接插入排序例：例：设待排序列为设待排序列为49,38,65,13,97,76，某一趟的结果，某一趟

8、的结果为：为：38,49,65,13,97,76则下一趟需做三项工作：则下一趟需做三项工作：1、在有序序列中进行查找以确定、在有序序列中进行查找以确定13应插入应插入的位置；的位置；2、移动元素将待插入位置空出；、移动元素将待插入位置空出；3.插入。插入。void Insert_Sort (STable L ) int i,j; for ( i=2; i=L.length; +i ) if (L.Ri.key L.Ri-1.key) L.R0 = L.Ri; for ( j=i-1; L.R0.key L.Rj.key; - j )L.Rj+1 = L.Rj; L.Rj+1 = L.R0; t

9、ypedef struct KeyType R100; int length; STable;直接插入排序算法：直接插入排序算法：13,6,9,2,9稳定的排序方法稳定的排序方法第第 9章章排排序序3636、2424、1010、6 6、1212存放在存放在 r r 数组的下标数组的下标为为 1 1 至至 5 5 的元素之中，用直接插入法将其的元素之中，用直接插入法将其排序。结果仍保存在下标为排序。结果仍保存在下标为 1 1 至至 5 5 的元素的元素之中。之中。举例举例:练习：练习：对关键字序列对关键字序列(265，301，751，129，937，863，742，694，076，438)进行直

10、进行直接插入排序，写出每一趟的结果。接插入排序，写出每一趟的结果。直接插入排序过程直接插入排序过程:( :(方括号表示无序区方括号表示无序区) ) 初始态初始态: 265301 751 129 937 863 742 694 076 438: 265301 751 129 937 863 742 694 076 438第一趟：第一趟：265 301751 129 937 863 742 694 076 438265 301751 129 937 863 742 694 076 438第二趟：第二趟：265 301 751129 937 863 742 694 076 438265 301 75

11、1129 937 863 742 694 076 438第三趟：第三趟：129 265 301 751937 863 742 694 076 438129 265 301 751937 863 742 694 076 438第四趟：第四趟：129 265 301 751 937863 742 694 076 438129 265 301 751 937863 742 694 076 438第五趟：第五趟：129 265 301 751 863 937742 694 076 438129 265 301 751 863 937742 694 076 438第六趟：第六趟：129 265 301

12、742 751 863 937694 076 438129 265 301 742 751 863 937694 076 438第七趟：第七趟：129 265 301 694 742 751 863 937076 438129 265 301 694 742 751 863 937076 438第八趟：第八趟：076 129 265 301 694 742 751 863 937438076 129 265 301 694 742 751 863 937438第九趟：第九趟：076 129 265 301 438 694 742 751 863 937 076 129 265 301 438

13、694 742 751 863 937 第第 9章章排排序序1、在对一组记录、在对一组记录(54,38,96,23,15,72,60,45,83)进行进行直接插入排序时，当把第直接插入排序时，当把第7个记录个记录60插入到插入到有序表时，为寻找插入位置需比较（有序表时，为寻找插入位置需比较（）次。）次。3练习：练习：2、请写出、请写出23，15，67，89，99，201，12，35，*99进行直接插入排序的每一趟进行直接插入排序的每一趟的结果。的结果。第第 9章章排排序序直接插入排序的时间分析直接插入排序的时间分析实现直接插入排序的基本操作有两个：实现直接插入排序的基本操作有两个：（1）“比较

14、比较”序列中两个关键字的大小；序列中两个关键字的大小；（2）“移动移动”记录。记录。void Insert_Sort (STable L ) int i,j; for ( i=2; i=L.length; +i ) if (L.Ri.key L.Ri-1.key) L.R0 = L.Ri; for ( j=i-1; L.R0.key L.Rj.key; - j )L.Rj+1 = L.Rj; L.Rj+1 = L.R0; 最好情况：待排数据已递增有序。最好情况：待排数据已递增有序。“比较比较”次数为次数为n-1次，次，“移动移动”次数为次数为0次。次。最坏情况：待排数据为逆序有序。最坏情况：待

15、排数据为逆序有序。“比较比较”次数为次数为(n+4)(n-1)/2；“移动移动”次数为次数为(n+4)(n-1)/2。第第 9章章排排序序直接插入排序的基本操作是在有序表中进行查找直接插入排序的基本操作是在有序表中进行查找和插入，而在有序表中查找插入位置，可以通过和插入，而在有序表中查找插入位置，可以通过折半查找的方法实现，由此进行的插入排序称之折半查找的方法实现，由此进行的插入排序称之为为折半插入排序折半插入排序。折半插入排序仅减少了关键字间的比较次数，但折半插入排序仅减少了关键字间的比较次数，但记录的移动次数不变。因此折半插入排序的时间记录的移动次数不变。因此折半插入排序的时间复杂度仍为复

16、杂度仍为O(n2)。折半插入排序也是一个。折半插入排序也是一个稳定稳定的的排序方法。排序方法。例：请写出例：请写出23，15，67，89，12，35，99进进行折半插入排序的每一趟的结果。行折半插入排序的每一趟的结果。折半插入排序算法折半插入排序算法void Inserthalf_Sort(STable L) int i,j,low,high,mid; for(i=2; i= L.length; i+) L.R0=L.Ri; low=1; high=i-1; while(low=L.Rmid.key)low=mid+1; else high=mid-1; for(j=i-1;j=high+1;

17、 -j) L.Rj+1=L.Rj; L.Rhigh+1=L.R0; 第第 9章章排排序序直接插入排序在直接插入排序在2 2种情况下排序较快：种情况下排序较快：1 1、数据较少时；、数据较少时；2 2、数据基本有序时；、数据基本有序时；基本思想：对待排记录序列先作基本思想：对待排记录序列先作“宏观宏观”调整，再作调整，再作“微观微观”调整。调整。9.2.3 希尔排序（又称缩小增量排序）希尔排序（又称缩小增量排序）第第 9章章排排序序先将整个待排记录序列分割成若干个子序列先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记分别进行直接插入排序，待整个序列中的记录录“基本有序

18、基本有序“时，再对全体记录进行一次时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。直接插入排序，就可以完成整个的排序工作。9.2.3 希尔排序（又称缩小增量排序）希尔排序（又称缩小增量排序）希尔排序的一个特点是：子序列的构成不希尔排序的一个特点是：子序列的构成不是简单地是简单地“逐段分割逐段分割”，而是将相隔某个，而是将相隔某个增量的记录组成一个子序列。增量的记录组成一个子序列。第第 9章章排排序序例例: : 将序列将序列 4949、3838、6565、9797、7676、1313、2727、4949、5555、4 4 用用 shell shell 排序的方法进行排序排序的方法

19、进行排序(1)(1)选定步长序列，如选为选定步长序列，如选为 8 8、4 4、2 2、1 1(2)(2)针对步长序列进行排序，从最大的步长开始，针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的步长肯定为逐步减少步长，最后一次选择的步长肯定为 1 1 。步长步长 8：49、38、65、97、76、13、27、49、55、4步长步长 8：49、38、65、97、76、13、27、49、55、4步长步长 4：49、 4、 65、97、76、13、27、49、55、38第第 9章章排排序序步长步长 2：49、 4、 27、49、55、13、65、97、76、38例例:将序列将序列

20、49、38、65、97、76、13、27、49、55、4 用用 shell 排序的排序的方法进行排序方法进行排序步长步长 1：27、 4、49、13、55、33、65、49、76、 97：4、 13、27、38、49、49、55、65、76、 97排序结果排序结果第第 9章章排排序序例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量第一趟希尔排序，设增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量第二趟希尔排序，设增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希尔

21、排序，设增量第三趟希尔排序，设增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 分析分析:shell 排序的分析非常困难，原因是何种步长排序的分析非常困难，原因是何种步长序列最优难以断定。通常认为时间复杂度为：序列最优难以断定。通常认为时间复杂度为：O（n1.5）练习：练习：对关键字序列对关键字序列(265，301，751，129，937，863，742，694，076，438)进行希进行希尔排序。尔排序。(增量为增量为5，3，1)初始态初始态: : 265 301 751 129 937 863 742 694 076 438第第1 1趟：趟：265 301

22、694 076 438 863 742 751 129 937 第第2 2趟：趟：076 301 129 265 438 694 742 751 863 937 第第3 3趟：趟：076 129 265 301 438 694 742 751 863 937 例：例：8,1,10,5,6,*8采用希尔排序，采用希尔排序，设设d=5,3,1不稳定的排序方法不稳定的排序方法第第 9章章排排序序9.3 9.3 交交 换换 排排 序序利用交换记录的位置进行排序的方法称为利用交换记录的位置进行排序的方法称为交换排交换排序序。其基本思想是：两两比较待排序记录的关键字，其基本思想是：两两比较待排序记录的关键

23、字，如果逆序就进行交换，直到所有记录都排好序为如果逆序就进行交换，直到所有记录都排好序为止。止。常用的交换排序方法主要有常用的交换排序方法主要有冒泡排序冒泡排序和和快速排序快速排序。快速排序是一种分区交换排序法，是对冒泡排序快速排序是一种分区交换排序法，是对冒泡排序方法的改进。方法的改进。第第 9章章排排序序原理原理: 若若序列中有序列中有n个元素，个元素，最多最多进行进行n-1趟趟排序排序。第第1趟，针对第趟，针对第r1至至rn个元素进行。个元素进行。第第2趟，针对第趟，针对第r1至至rn-1个元素进行。个元素进行。 第第i趟，针对第趟，针对第r1至至rn-i+1个元素进行。个元素进行。每一

24、趟进行的过程：每一趟进行的过程：从第一个元素开始，比较两个相邻的元素。从第一个元素开始，比较两个相邻的元素。若相邻的元素若相邻的元素逆序逆序，则进行交换；否则继续，则进行交换；否则继续比较下面两个相邻的元素。比较下面两个相邻的元素。结束条件：结束条件：在在该该趟趟排序排序过程中，未出现交换。过程中，未出现交换。第第 9章章排排序序冒泡排序冒泡排序假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟起泡排序趟起泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较

25、相邻记录，将关比较相邻记录，将关键字最大的记录键字最大的记录交换交换到到 n-i+1 的位置上的位置上第第 9章章排排序序void Bubble_Sort(STable L)int i,j,flag=0;for(i=1; iL.length; i+) flag=1; for(j=1;j= L.length-i;j+) if(L.Rj+1.keyL.Rj.key) flag=0; L.R0=L.Rj; L.Rj=L.Rj+1; L.Rj+1=L.R0; if(flag=1) return; 稳定的排序方法稳定的排序方法冒泡排序算法冒泡排序算法第第 9章章排排序序练习：练习：1: 将序列将序列1、

26、3、5、7、9、13、27、49 用冒泡排序的方法进行排序。用冒泡排序的方法进行排序。2: 将序列将序列49、27、13、9、7、5、3、1用冒泡排序的方法进行排序。用冒泡排序的方法进行排序。例例: 将序列将序列49、38、65、97、76、13、27、*49 用冒泡排序的方法进行排序。用冒泡排序的方法进行排序。第第 9章章排排序序时间性能分析时间性能分析: :最好的情况最好的情况（关键字在记录序列中顺序有序）：（关键字在记录序列中顺序有序）：只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况最坏的情况（关键字在记录序列中逆序有序）：（关键字在记录序列中逆序有序）： 需进行

27、需进行n-1n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-12) 1() 1(2nnini2) 1(3) 1(32nnini时间复杂时间复杂度度:正序时正序时 O(n)，逆序时逆序时 O(n2)。所以所以时间复杂时间复杂度度 O(n2)。第第 9章章排排序序1、对一组记录、对一组记录(54,38,96,23,15,72,60,45,83)进行进行排序，分别采用直接插入排序、希尔排序排序，分别采用直接插入排序、希尔排序（d=5,3,1）、冒泡排序方法。）、冒泡排序方法。练习练习2、排序方法中，从未排序序列中依次取出、排序方法中，从未排

28、序序列中依次取出元素与已排序序列中的元素进行比较，将其元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为放入已排序序列的正确位置上的方法，称为（）插入排序插入排序第第 9章章排排序序快速排序快速排序基本思想：找一个记录，以它的关键字作为基本思想：找一个记录，以它的关键字作为“枢轴枢轴”，凡其关键字小于枢轴的记录均移，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。的记录均移动至该记录之后。致使一趟快速排序之后，记录的无序序列致使一趟快速排序之后，记录的无序序列Rs.tRs.t将分割成两部

29、分将分割成两部分：Rs.i-1和和Ri+1.t，且，且 Rj.key Ri.key Rj.key (sji-1) 基准基准 (i+1jt)。快速排序是对冒泡排序的改进。快速排序是对冒泡排序的改进。52 49 80 36 14 58 61 97 23 75stlowhigh设设 Rs=52 Rs=52 为为枢轴（或基准）枢轴（或基准）将将 Rhigh.key Rhigh.key 和和 枢轴的关键字进行比较，要枢轴的关键字进行比较，要求求Rhigh.key Rhigh.key 枢轴的关键字枢轴的关键字将将 Rlow.key Rlow.key 和和 枢轴的关键字进行比较，枢轴的关键字进行比较，要求要

30、求Rlow.key Rlow.key 枢轴的关键字枢轴的关键字high23low80high14low52例如例如R052lowhighhighhighlow思考：一趟快速排序的结果？思考：一趟快速排序的结果？第第 9章章排排序序快速排序首先对无序的记录序列进行快速排序首先对无序的记录序列进行“一一次划分次划分”，之后分别对分割所得两个子序，之后分别对分割所得两个子序列列“递归递归”进行快速排序。进行快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序例：请对关键字序列例：请对关键

31、字序列52,49,80,36,14,58,61,97, 23,75进行快速进行快速排序。排序。练习练习:对关键字序列对关键字序列56 23 15 96 53进行快速进行快速排序排序.第第 9章章排排序序先对先对 Rs.key, Rt.keyRs.key, Rt.key 和和 RR (s+t)/2(s+t)/2 .key.key，进行，进行相互比较，然后取关键字为相互比较，然后取关键字为 “ “三者之三者之中中”的记录的记录为枢轴记录。为枢轴记录。快速排序的时间分析快速排序的时间分析若待排记录的初始状态为按关键字有序时，快速若待排记录的初始状态为按关键字有序时，快速排序将蜕化为冒泡排序，其时间复

32、杂度为排序将蜕化为冒泡排序，其时间复杂度为O(nO(n2 2) )。为避免出现这种情况，可在进行一次划分之前，为避免出现这种情况，可在进行一次划分之前，进行进行“预处理预处理”，即：，即：快速排序的时间复杂度为快速排序的时间复杂度为O(nlogO(nlog2 2n)n)不稳定的排序方法不稳定的排序方法例：对例：对1616，1818，* *18,1518,15排序排序第第 9章章排排序序例：例：用某种排序方法对关键字序列用某种排序方法对关键字序列25,84,21,47,15,27,68,35,20进行进行排序时，元素序列的变化情况如下：排序时，元素序列的变化情况如下：(1)20,15,21,25

33、,47,27,68,35,84(2)15,20,21,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84则所采用的排序方法是（）则所采用的排序方法是（）快速排序快速排序第第 9章章排排序序例：例：快速排序方法在（快速排序方法在（）情况下最不利于发挥其）情况下最不利于发挥其长处。长处。A.要排序的数据量太大要排序的数据量太大B.要排序的数据中含有多个相同值要排序的数据中含有多个相同值C.要排序的数据已基本有序要排序的数据已基本有序D.要排序的数据个数为奇数要排序的数据个数为奇数C第第 9章章排排序序9.4 9.4 选择排序选择排序选择排序（选择排序（Se

34、lection Sort）的基本思）的基本思想是：不断从待排记录序列中选出关键字最想是：不断从待排记录序列中选出关键字最小的记录插入已排序记录序列的后面，直到小的记录插入已排序记录序列的后面，直到n个记录全部插入已排序记录序列中。个记录全部插入已排序记录序列中。本节主要介绍两种选择排序方法：本节主要介绍两种选择排序方法：简单选择简单选择排序排序和和堆排序堆排序。第第 9章章排排序序简单选择排序简单选择排序假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列R1.i-1R1.i-1无序序列无序序列 Ri.nRi.n 第第 i i 趟趟简单选择排序简单选择排

35、序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.iR1.i无序序列无序序列 Ri+1.nRi+1.nvoid Select_Sort(RecType R,int n) int i,j,k; RecType temp; for(i=1;in;i+) k=i; /假定起始位置为最小记录的位置假定起始位置为最小记录的位置 for(j=i+1;j=n;j+) /查找最小记录查找最小记录 if(Rj.keyRk.key) k=j; if(i!=k) /如果如果k k不是假定位置，则交换不是假定位置，则交换 L.R0=L.Rk; /*R0作为辅助存储空间作为辅助存储空间*/ L.R

36、k=L.Ri; L.Ri= L.R0; 本算法中有两重循环：外循环用于控制排序的次数，内本算法中有两重循环：外循环用于控制排序的次数，内循环用于查找当前待排记录序列中关键字最小的记录。循环用于查找当前待排记录序列中关键字最小的记录。 第第 9章章排排序序例：例：用简单选择排序方法对关键字序列用简单选择排序方法对关键字序列25,84,21,47,15,27,68,35,20进行升序排序进行升序排序练习：练习：用简单选择排序方法对关键字序用简单选择排序方法对关键字序列列15,13,*15,11,17进行升序排序进行升序排序简单选择排序是简单选择排序是不稳定的不稳定的排序方法排序方法第第 9章章排排

37、序序时间性能分析时间性能分析对对 n n 个记录进行简单选择排序，所需进行的个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：关键字间的比较次数总计为：移动记录的次数，最小值为移动记录的次数，最小值为 0, 0, 最大值为最大值为3(n-1) 3(n-1) 。2) 1()(11nninni时间复杂度为时间复杂度为O(nO(n2 2) )。第第 9章章排排序序堆排序堆排序堆排序堆排序借助于完全二叉树结构进行排序，是借助于完全二叉树结构进行排序，是一种一种树型选择排序树型选择排序。基本思想：在直接选择排序时，为从基本思想：在直接选择排序时，为从n个关键字中选出个关键字中选出最小值，需要进

38、行最小值，需要进行n-1次比较，然后又在剩下的次比较，然后又在剩下的n-1个个关键字中选出次最小值，需要关键字中选出次最小值，需要n-2次比较。在次比较。在n-2次的次的比较中可能有许多比较在前面的比较中可能有许多比较在前面的n-1次比较中已经做过，次比较中已经做过，因此存在多次重复比较，降低了算法的效率。堆排序方因此存在多次重复比较，降低了算法的效率。堆排序方法是由法是由J. Williams和和Floyd提出的一种改进方法，提出的一种改进方法，它在选择当前最小关键字记录的同时，还保存了本次排它在选择当前最小关键字记录的同时，还保存了本次排序过程所产生的比较信息。序过程所产生的比较信息。第第

39、 9章章排排序序堆是满足下列性质的数列堆是满足下列性质的数列r r1 1, r, r2 2, , ，r rn n ：或或122iiiirrrr122iiiirrrr堆的定义堆的定义: :12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 4912, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例例: :小顶堆小顶堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 4912, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆( (小顶堆小顶堆) )( (大顶堆大顶堆)

40、 )第第 9章章排排序序r ri ir r2i 2i r r2i+1 2i+1 若将该数列视作完全二叉树，则若将该数列视作完全二叉树，则 r r2i2i 是是 r ri i 的左孩子；的左孩子； r r2i+12i+1 是是 r ri i 的右孩子。的右孩子。121236362727656549498173735555404034349898例例: :是堆是堆1414不不12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 4912, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49堆顶堆顶第第 9章章排排序序对一组待排序记录，首先把它们的

41、关键字按对一组待排序记录，首先把它们的关键字按堆定义排列成一个序列（称为初始建堆），堆定义排列成一个序列（称为初始建堆），堆顶元素为最小关键字的记录，将堆顶元素堆顶元素为最小关键字的记录，将堆顶元素与序列中的最后一个元素交换位置；然后对与序列中的最后一个元素交换位置；然后对剩余的记录再建堆，得到次最小关键字记录；剩余的记录再建堆，得到次最小关键字记录；如此反复进行，直到全部记录有序为止，这如此反复进行，直到全部记录有序为止，这个过程称为个过程称为堆排序堆排序。堆排序的过程堆排序的过程第第 9章章排排序序如何将一个无序序列建成一个堆？如何将一个无序序列建成一个堆？从一个无序序列建堆的过程就是一个

42、反复从一个无序序列建堆的过程就是一个反复“筛选筛选”的过程，的过程，“筛选筛选”需要从需要从i= n/2的结点的结点Ri开始，直至结点开始，直至结点R1结束。结束。堆排序中的两种基本动作：堆排序中的两种基本动作：筛选和建堆筛选和建堆建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。40405555494973738164643636121227279898例如例如: : 排序之前的关键字序列为排序之前的关键字序列为121236368181737349499898818173735555现在，左现在，左/ /右子树都已经调整为堆，最后只要调右子树都已经调整为堆，最后只要调整

43、根结点，使整个二叉树是个整根结点，使整个二叉树是个“堆堆”即可。即可。9898494940406464363612122727若将待排序列看成是一个完全二叉树，则最后一若将待排序列看成是一个完全二叉树，则最后一个非终端结点是第个非终端结点是第 n/2 个元素，所以筛选从第个元素，所以筛选从第 n/2 个元素开始个元素开始建大顶堆过程如下：建大顶堆过程如下：第第 9章章排排序序练习：一组记录的关键字序列为：练习：一组记录的关键字序列为：46,79,56,38,40,84,则利用堆排序的方则利用堆排序的方法进行从小到大的排序建立的初始堆为（）法进行从小到大的排序建立的初始堆为（）84，79，56，

44、38，40，46例例:对对12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49利用堆排序进行利用堆排序进行递增排序递增排序堆排序的时间复杂度为堆排序的时间复杂度为O(O(n nloglog2 2n n) )。练习：对关键字序列练习：对关键字序列15,5,4,9,*15,8 进行从小到大的排序。进行从小到大的排序。堆排序是堆排序是不稳定的不稳定的排序方法。排序方法。第第 9章章排排序序9.5 9.5 归归 并并 排排 序序归并排序的过程基于下列归并排序的过程基于下列基本思想基本思想进行：进行：将两个或两个以上的有序子序列将两个或两个以上的有序子序列 “ “归并归并

45、” ” 为一个有序序列。为一个有序序列。在内部排序中，通常采用的是在内部排序中，通常采用的是2-2-路归并排序。路归并排序。即：将两个位置相邻的记录有序子序列即：将两个位置相邻的记录有序子序列有有 序序 序序 列列 Rl.nRl.n有序子序列有序子序列 RRl l. .mm 有序子序列有序子序列 RRmm+1.+1.n n 第第 9章章排排序序例如：例如：对下列关键字序列进行对下列关键字序列进行2 2路归并排序路归并排序52, 23, 80, 36, 68, 1452, 23, 80, 36, 68, 1452, 23, 80, 36, 68, 1452, 23, 80, 36, 68, 14

46、(23,36,52,80),(14,68)(23,36,52,80),(14,68)(23 ,52), (36 , 80)(23 ,52), (36 , 80)，(14 ,68)(14 ,68)(14,23,36,52, 68,80)(14,23,36,52, 68,80)练习：对练习：对12 34 8 90 7 67 52 56 *34进行归并排序进行归并排序第第 9章章排排序序对对 n n 个记录进行归并排序每一趟归并的时个记录进行归并排序每一趟归并的时间复杂度为间复杂度为 O(O(n n) )，总共需进行，总共需进行 loglog2 2n n 趟。趟。即：归并排序的时间复杂度为即：归并排

47、序的时间复杂度为(n nloglog2 2n n) )。从排序的稳定性看，二路归并排序是一从排序的稳定性看，二路归并排序是一种种稳定的稳定的排序方法。排序方法。归并排序的性能分析归并排序的性能分析第第 9章章排排序序基数排序是和前面所述各类排序方法完全不同的一基数排序是和前面所述各类排序方法完全不同的一种排序方法。种排序方法。基数排序基数排序(Radix Sort)是一种借助于多关键字排是一种借助于多关键字排序的思想对单逻辑关键字进行排序的方法，即先将序的思想对单逻辑关键字进行排序的方法，即先将关键字分解成若干部分，然后通过对各部分关键字关键字分解成若干部分，然后通过对各部分关键字的分别排序，

48、最终完成对全部记录的排序。的分别排序，最终完成对全部记录的排序。基数排序首先把每个关键字看成一个基数排序首先把每个关键字看成一个d元组：元组：Ki=( Ki0, Ki1, Kid-1)例：例：578看成是（看成是（5，7，8）其中，其中，C C0 0KKi i j jCCr-1r-1（1in1in，0jd-10jd-1），），r r称为称为基数基数。设置设置r r个桶，排序时先按个桶，排序时先按K Ki id-1d-1从大到小将记录分配到从大到小将记录分配到r r个个桶中，然后依次收集这些记录，称之为桶中，然后依次收集这些记录，称之为一趟基数排序一趟基数排序。再按再按K Ki i d-2 d-2从大到小将记录分配到从大到小将记录分配到r r个桶中，如此反复，个桶中，如此反复，直到对直到对K Ki i0 0分配和收集，得到的便是排好序的序列。分配和收集，得到的便是排好序的序列。基数基数r r的选择和关键字的分解法因关键字的类型而异。的选择和关键字的分解法因关键字的类型而异。关键字为关键字为十进制整数十进制整数时，时，r=10r=10，C C0 0=0=0，C C