[理学]9排序技术

《[理学]9排序技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、法数据是存储在内存中，并在内存中加以处理的，这种排序方法叫内部排序。如果在排序过程中，数据的主要部分存放在外存储器中（如软盘、硬盘、磁带），借助内存进行内、外存数据交换，逐步排列记录之间的顺序，则称之为外部排序。一种排序方法，如果排序后具有相同关键字的记录仍维持排序之前的相对次序，则称之为稳定的，否则称为不稳定的。9.1互换类排序所谓互换排序是指借助数据元素之间的互相交换进行排序的一种方法。互换类排序方法有：冒泡排序快速排序冒泡排序首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在

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

4、13715999999888888最后结果：第三遍（从前往后）结果：（从后往前）结果：第二遍（从前往后）766543211766543211766543211764652311764652311647623511对于有相同关键字记录的情况，此算法是稳定的。[算法9.1]冒泡排序输入：无序序列P(1:n)输出：有序序列P(1:n)PROCEDUREBUBSORT（P，n）k=1;m=nWHILE(kp(i+1))THEN[发现逆序进行交换]{d=p(i);p(i)=p(i+1);p(i+1)=

5、d;m=i;}j=k+1;k=0FORi=mTOjBY-1DO[从后往前扫描子表]IF(p(i-1)>p(i))THEN[发现逆序进行交换]{d=p(i);p(i)=p(i-1);p(i-1)=d;k=i;}}RETURNm记住从前往后扫描中最后一次发生交换的位置，此位置之后肯定为有序的，因此往回扫描时只能从该处往前扫描即可。k记住每次从后往前扫描时最后交换的位置冒泡排序算法的C语言描述：BUBSORT（ETP[]，intn）{intm,k,j,i;ETd;k=0;m=n-1;while(k

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

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