9排序技术课件

1、数据结构第九章 排序技术第1页，共42页。第九章 排序 排序的基本概念 三种简单排序方法 堆排序 快速排序 归并排序(不做要求） 基数排序(不做要求）第2页，共42页。 什么是排序？简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。例如，将下列记录序列 5, 4, 8, 3, 1, 5, 6, 2, 9, 7 调整为序列 1, 2, 3, 4, 5, 5, 6, 7, 8, 9 将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序(sort)。 本章讨论的排序均为按非递减顺序排序，并假定要排序的记录均已存储在一个一维数组中。排序的基本概念第3页，共42页。对一批记录的排序，应该指定是

2、根据记录中哪个域的数据进行排列。这个作为排序依据的数据域我们称之为关键字(key)。大多数的排序方法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。第4页，共42页。9.1 互换类排序所谓互换排序是指借助数据元素之间的互相交换进行排序的一种方法。互换类排序方法有： 冒泡排序 快速排序第5页，共42页。冒泡排序首先，从表头开始往后扫描

3、线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。然后从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面。对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。第6页，共42页。冒泡排序过程示意图

4、（从后往前）第一遍（从前往后）原序列：98结果：6476235119682476135196结果：8247613516824961371568249613715999999888888最后结果：第三遍（从前往后）结果：（从后往前）结果：第二遍（从前往后）766543211766543211766543211764652311764652311647623511对于有相同关键字记录的情况，此算法是稳定的。第7页，共42页。算法9.1冒泡排序输入：无序序列 P(1:n)输出：有序序列 P(1:n) PROCEDURE BUBSORT（P，n）k=1;m=nWHILE (kp(i+1) THEN 发

5、现逆序进行交换 d=p(i);p(i)=p(i+1);p(i+1)=d;m=i; j=k+1; k=0 FOR i=m TO j BY -1 DO 从后往前扫描子表 IF (p(i-1)p(i) THEN 发现逆序进行交换 d=p(i);p(i)=p(i-1);p(i-1)=d;k=i;RETURN m记住从前往后扫描中最后一次发生交换的位置，此位置之后肯定为有序的，因此往回扫描时只能从该处往前扫描即可。 k记住每次从后往前扫描时最后交换的位置第8页，共42页。冒泡排序算法的C语言描述：BUBSORT（ET P，int n） int m,k,j,i; ET d; k=0; m=n-1; whi

6、le (km) 子表未空 j=m-1;m=0; for(i=k;ipi+1) 发现逆序进行交换 d=pi;pi=pi+1;pi+1=d;m=i; j=k+1; k=0 for (i=m;i=j;i-) 从后往前扫描子表 if(pi-1pi) 发现逆序进行交换 d=pi;pi=pi-1;pi-1=d;k=i;return;第9页，共42页。冒泡排序的分析 冒泡排序是一种最简单的互换类排序方法，它属于稳定的排序。 设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2。但这个工作量不是必需的，一般要小于这个工作量第1

7、0页，共42页。快速排序 快速排序是由冒泡排序改进而得到的，冒泡排序在扫描过程中只对相邻两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序，而快速排序是通过一次交换而消除多个逆序。快速排序也是一种互换类排序，由于比冒泡排序速度快，因此称为快速排序，又称为分区交换排序，是目前内部排序中速度较快的方法。第11页，共42页。快速排序的思想从线性表中选取一个元素，设为T。然后将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处。这个过程称为线性表的分割。 通过线性表的一次分割，就以T为分界线，将线性表分成了前后两个子

8、表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。对分割后的各子表再按上述原则进行分割，一直做下去，直到所有子表为空为止，此时的线性表就变成了有序表。无序线性表分割T=T=T分割分割 快速排序的关键是对线性表的分割，以及对各分割出的子表再进行分割第12页，共42页。快速排序的步骤首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的位置。反复作以下两步： (1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个P(j)T为止，将P(j)移到P(i)的

9、位置上。 (2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个P(i)T为止，将P(i)移到P(j)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个位置（即ij）为止，此时将T移到P(i)的位置上。第13页，共42页。快速排序示例原序列： 1 2 3 4 5 6 7 8 9 10 11 5 1 7 3 1 6 9 4 2 8 6 快速排序是不稳定的，对于有相同关键字的记录，排序以后次序可能会颠倒。第14页，共42页。算法9.2线性表的分割输入：待分割的子表 P(m:n)输出：分割后的分界线位置 iPROCEDURE SPLIT（P,m,n,i）选取P(k) 其中mkn P(k)一

10、般取第一项，中间项和最后一项的中间项T=P(k); P(k)=P(m)i=m ; j=nWHILE (ij) DO WHILE(P(j)T）and (ij) DO j=j-1 IF (ij) THEN p(i)=p(j);i=i+1 WHILE(p(i)T）and (ij) DO i=i+1 IF (im) THEN 子表不空 SPLIT（P,m,n,i); 分割 QKSORT1(P,m,i-1); 对前面子表进行快速排序 QKSORT1(P,i+1,n); 对后面子表进行快速排序RETURN第16页，共42页。快速排序的分析 快速排序也是一种互换类排序方法，但它属于不稳定的排序。 设线性表的

11、长度为n，则在最坏情况下，快速排序也需要n(n-1)/2次比较，但实际的排序效率要比冒泡排序高得多。 若系统不支持递归，则在快速排序过程中，随着对各子表的不断分割，划分出的子表会越来越多，但一次只能对一个子表进行再分割处理，因此需要将暂时不分割的子表保存起来，这可用一个栈来实现。第17页，共42页。9.2 插入类排序冒泡排序与快速排序本质上都是通过数据元素的交换逐步消除线性表中的逆序，而插入类的排序方法是将无序表中的元素按照一定的算法插入到有序的线性表中，直到原始无序表中的所有元素全部插入完毕为止。插入类排序方法主要有：简单插入排序和希尔排序第18页，共42页。简单插入排序 在线性表中，只包含

12、第1个元素的子表显然可以是有序表，然后从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面已经有序的子表中。插入思想：首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中的第j-1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。第19页，共42页。简单插入排序6897654621168297654311682497653116824976531198766543211698765432116824967531

13、168249617531682496137516824961375168249613715其中红底黄字为当前插入的元素，白底黑字为j指针的位置，即当前要处理的元素 对于有相同关键字记录的情况， 此算法是稳定的。第20页，共42页。算法9.5简单插入排序输入：待排序序列 P(1:n)输出：有序序列 P(1:n) PROCEDURE INSORT（P，n）FOR j=2 TO n DO T=P(j)；k=j-1 WHILE (k0) and (P(k)T) DO P(k+1)=P(k);k=k-1 P(k+1)=TRETURN第21页，共42页。简单插入排序算法的C语言描述：insort（ET P

14、，int n） int j,k; ET t; for(j=1;j=0)&(pkt) pk+1=pk;k=k-1; pk+1=t; return;第22页，共42页。简单插入排序的分析 简单插入排序是一种插入类排序方法，它属于稳定的排序。 在简单插入排序中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。第23页，共42页。希尔排序 将整个无序序列分割成若干小子序列分别进行简单插入排序。子序列的分割方法如下： 将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就

15、完成。 增量序列一般取 htn/2k(k1，2，log2n)，其中n为待排序序列的长度。在希尔排序过程中，虽然对于每一个子表采用的仍然是插入排序，但是在子表中每进行一次比较就可能移去整个线性表中的多个逆序，从而改善整个排序过程的性能第24页，共42页。希尔排序示意图7192413318821844635297182413 5 88219446331297 5 8131824631929823144h=12/2=6h=12/4=3h=12/8=1最后结果5781318192429314463821 2 3 4 5 6 7 8 9 10 11 12第25页，共42页。算法9.6 希尔排序输入：待排

16、序序列 P(1:n)输出：有序序列 P(1:n) PROCEDURE SHLSORT（P，n）h=n/2WHILE (h0) DO FOR j=h+1 TO n DO t=P(j);i=j-h WHILE (i0)and(P(i)t) DO P(i+h)=P(i);i=i-h P(i+h)=t h=h/2RETURN希尔排序是不稳定的排序第26页，共42页。希尔排序算法的C语言描述：shlsort（ET P，int n） int h,j,i; ET t; h=n/2; while(h0) for(j=h;j=0)&(pit) pi+h=pi;i=i-h; pi+h=t; h=h/2; retu

17、rn;第27页，共42页。9.3 选择类排序选择排序的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。选择类排序有简单选择排序和堆排序，但都是不稳定的排序第28页，共42页。简单选择排序简单选择排序的作法是：第一趟扫描所有数据，选择其中最小的一个与第一个数据互换；第二趟从第二个数据开始向后扫描，选择最小的与第二个数据互换；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。第29页，共42页。简单选择排序过程示意图原序列8921564885161947第一遍选择1621564885891947第二遍选择161956

18、4885892147第三遍选择1619214885895647第四遍选择1619214785895648第五遍选择1619214748895685第六遍选择1619214748568985第七遍选择1619214748568589第30页，共42页。算法9.7简单选择排序输入：待排序序列 P(1:n)输出：有序序列 P(1:n) PROCEDURE SELESORT（P，n）FOR i=1 TO n-1 DO k=i FOR j=i+1 TO n DO IF P(j)P(k) THEN k=j IF(ki) THEN d=P(i);P(i)=P(k);P(k)=d RETURN第31页，共42

19、页。简单选择排序算法的C语言描述：insort（ET P，int n） int j,k; ET d; for(i=0;i=n-2;i+) k=i; for(j=i+1;j=n-1;j+) if(pj= h2ihi = h2i+1hi = h2ihi = h2i+1或(i1，2，n/2) 时称之为堆。我们只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素(即第一个元素)必为最大项。第33页，共42页。堆排序（Heap Sort）是利用二叉树的一种排序方法。堆（Heap）是与二叉排序树不同的一种二叉树，它的定义为：一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点

20、，此结点数据必须大于或等于其儿子结点数据。由于堆是完全二叉树，采用将结点顺序编号存入一维数组中的表示法比链接表示法节省存储空间，也便于计算。 堆排序属于选择类的排序方法第34页，共42页。堆的示意图（堆顶元素最大）序列（91，85，53，36，47，30，24，12）是一个堆，如图：9185533647302412在一棵具有n个结点的完全二叉树（用一维数组H(1:n)表示）中，假设结点H（m）的左右子树均为堆，现要将H（m）为根结点的子树也调整为堆，这就是调整建堆的过程。第35页，共42页。调整建堆示意图（）（）（）479153853012243691475385301224369185534

21、730122436调整建堆的过程总是将根结点值与左右子数的根结点值进行比较，若不满足堆的条件，则将左右子树根结点值中的大者与根结点值交换，该过程一直到所有子树均为堆为止。第36页，共42页。算法9.8 调整建堆输入：完全二叉树数组H(1:n)。其中结点H(m)的左、右子树均为堆。输出：以H(m)为根结点的子树为堆。PROCEDURE SIFT（H，n，m）t=H(m);j=2mWHILE (jn) DO IF(jn)and(H(j)H(j+1) THEN j=j+1 IF (tH(j) THEN H(m)=H(j);m=j;j=2m else j=n+1 H(m)=tRETURN完全二叉树中的

22、所有结点值是从根结点开始一层一层地从左到右存储在一维数组H中。而对于完全二叉树的顺序存储结构来说，结点k的左子树根结点为2k，右子树的根结点为2k+1。因此算法中没有用到指针运算，而只用到数组的下标运算。第37页，共42页。有了调整建堆的算法后，就可以将一个无序序列建成为堆。假设无序序列H(1:n)以完全二叉树表示。从完全二叉树的最后一个非叶子结点（即第n/2个元素）开始，直到根结点（即第一个元素）为止，对每一个结点进行调整建堆，最后就可以得到与该序列对应的堆。第38页，共42页。堆排序(1)首先将一个无序序列建成堆。(2)然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。 反复做第(2)步，直到剩下的子序列为空为止。第39页，共42页。算法9.9 堆排序输入：无序序列 H(1: