数据结构-合肥工业大学 9

第九章内排序★基本概念★插入排序★冒泡排序★选择排序★计数排序★希尔排序★堆排序★快速排序★合并排序★基数排序设含有n个记录的文件{R1,R2,…，Rn

},其相应的关键字为{K1,K2,…，Kn

}，需确定一种排列P(1),P(2),…,P(n),使其相应的关键字满足如下的递增(或递减)关系：KP(1)

≤KP(2)≤KP(3)≤…≤KP(n)即，使上述文件成为一个按其关键字线性有序的文件{RP(1),RP(2),…，RP(n)},这样一种运算称为排序。9.1基本概念如果在排序期间具有相同关键字的记录的相对位置不变，则称此方法是稳定的。排序：排序的稳定性：内排序插入类排序直接插入排序折半插入排序希尔排序交换类排序冒泡排序快速排序选择类排序选择排序堆排序归并类排序归并排序其他排序计数排序基数排序9.2直接插入排序假设在排序过程中，记录序列R[1..n]的状态为：

则一趟插入排序的基本思想为：将记录R[i]插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i]。显然，完成这个“插入”需分三步进行：1．查找R[i]的插入位置j+1；2．将R[j+1..i-1]中的记录后移一个位置；3．将R[i]复制到R[j+1]的位置上。直接插入排序：利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。注意直接插入排序算法的三个要点：

1.从R[i-1]起向前进行顺序查找，监视哨设置在R[0]；

R[0]=R[i]；{设置“哨兵”}j=i-1;while(R[0].key<R[j].key)j=j-1;{//从后往前找}Return(j+1);{返回R[i]的插入位置为j+1}2.对于在查找过程中找到的那些关键字不小于R[i].key的记录，并在查找的同时实现记录向后移动；

while(R[0].key<R[j].key){R[j+1]=R[j];j=j-1;}3.i=2，3，…,n,实现整个序列的排序。排序算法如下：voidinsort(Listr,intn){//r为给定的表，其记录为r[i]，i=0，1，…，n，x为暂存单元。

for(i=2;i<=n;i++){r[0]=r[i];//r[0]作为标志位

j=i-1;while(r[0].key<r[j].key){r[j+1]=r[j];j--;}//j从i-1至0，r[j].key与r[i].key进行比较

r[j+1]=r[0];}}//insort排序的时间分析：

实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：“移动”的次数：

总的说来，直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。“比较”的次数：“移动”的次数：

2(n-1)9.3冒泡排序排序算法的思想：比较k1和k2,如果这些关键字的值不符合排序顺序,就交换k1和k2；然后对记录k2和k3,k3和k4等等进行相同的工作。直到kn-1和kn为止,到此得到一个最大(或最小)关键字值存在kn的位置上(通常将此过程叫做一趟)。重复这个过程,就得到在位置kn-1,kn-2等处的适当记录,使得所有记录最终被排好序。

例如:将5个记录的关键字7,4,8,3,9进行冒泡排序。排序后k1≤k2≤…≤kn(n=5)。7443347344837773888899999①②③④

因为到第四趟就没有交换的偶对了,所以整个排序结束。算法描述如下:voidbubblesort(List

r,intn){for(m=1;m<=n;m++)

scanf(“%d”,r[m]);k=n;do{all=〝T〞;//all=T,标志没有交换的;all=F,标志有交换的

for(m=1;m<=k-1;m++){i=m+1;if(r[m]>r[i]){max=r[m];r[m]=r[i];r[j]=max;all=〝F〞;}}k--;}while((all==〝T〞)||(k==1)}冒泡排序的结束条件为：最后一趟没有进行“交换”。冒泡排序是一种稳定的排序算法。时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：“移动”的次数：n-10

最坏的情况（关键字在记录序列中逆序有序）：需进行

n-1趟起泡“比较”的次数：“移动”的次数：

NorthChinaElectricPowerUniversity9.4选择排序基本思想：首先在n个记录中选择一个具有最小或最大关键字的记录，将选出的记录与记录集合中的第一个记录交换位置。然后在r[2]至r[n]中选择一个最小或最大的值与r[2]交换位置，…，依此类推，直至r[n-1]和r[n]比较完毕。voidslsort(List

r,intn)//每次从r[j](j=i+1,…n)中选了最小值，与r[i](i=1,2,…,n-1)交换，进行分类{for(i=1;i<=n-1;i++)//共进行n-1趟排序

{m=i;for(j=i+1;j<=n;j++)if(r[j].key<r[m].key)m=j;//m指示关键字最小的记录的序号

if(m!=i){x=r[i];r[i]=r[m];r[m]=x;}}}例关键字序列{055，55，60，13，05，94，17，70},利用选择排序算法进行排序。关键字r[1]055r[2]55r[3]60r[4]13r[5]05r[6]94r[7]17r[8]70i=1,m=505556013055941770i=2,m=405136055055941770i=3,m=705131755055946070i=4,m=405131755055946070i=5,m=505131755055946070i=6,m=705131755055609470i=7,m=805131755055607094不稳定算法的复杂性分析：当选则第一个最小值时需进行n-1次比较，选第二个最小值时需进行n-2次比较，…，选n-1个最小值时需进行n-(n-1)次比较，所以总的比较次数为(n-1)+(n-2)+…+2+1=n(n-1)/2故排序n个记录需要时间为O(n2)。由于执行一次交换，需三次移动记录，最多交换n-1次，故最多移动次数为3(n-1)NorthChinaElectricPowerUniversity9.5快速排序快速排序又称分划交换排序，设输入文件有n个记录R1,R2,…,Rn

,它们对应的关键字是k1,k2,…,kn

。该方法先取序列中任一关键字K(通常取第一个)，然后用K从两头到中间进行比较/交换，就能形成一个分划：凡是小于等于K的被移到左边，凡是大于K的被移到右边。1.快速排序的定义NorthChinaElectricPowerUniversity2.快速排序步骤2)从最末项kn开始起指针j倒向前找到第一个kj

<x.key或

i≥j时，则判i<j?是，kj送ki

，i=i+1；1)选定k1为起点，且将k1送x；3)从ki项起指针i向前扫描，找到第一个ki

>x.key或

i≥j时，则判i<j?是，ki送kj

，j=j-1；4)上述过程进行到i=j时停止，将x送ki

，同时i=i+1；

j=j-1,即x在正确位置上,并分K为K1和K2两个子集合；5)重复调用上述过程，直到将整个集合排序好为止。例:初始关键字[4655134294051770]将46→xij第一次交换后[

55134294051770]ji第二次交换后[17551342940570]ji第三次交换后[17

134294055570]j第四次交换后[1705134294

5570]jii至此，完成第一趟排序1755059446第五趟排序后0513174246557094第一趟排序后[17051342]46[945570]第二趟排序后[1305]17[42]46[945570]第三趟排序后[05]1317[42]46[945570]第四趟排序后0513174246[7055]94

例:初始关键字[4655134294051770]接上例voidqksort(Listr,intL,intP)//将r[L]至r[P]进行排序{}//qksort

3.快速排序算法do{while((r[j].key>=x.key)&&(j>i))j--;//从表尾一端开始比较

if(i<j){r[i]=r[j];i++;while((r[i].key<=x.key)&&(i<j))i++;//再从表的始端起进行比较

if(i<j){r[j]=r[i];j--;}}}while(i!=j);i=L;j=P;x=r[i];//置初值

r[i]=x;i++;j--;//一趟快排结束，将x移至正确位置

if(L<j)qksort(r,L,j);

//反复排序前一部分

if(i<P)qksort(r,i,P);

//反复排序后一部分NorthChinaElectricPowerUniversity快速排序是目前内部排序中最快的方法。若关键字的分布式均匀的，可以粗略的认为每次划分都把文件分成长度相等的两个文件。4.快速排序算法的性能分析但如果原来的文件是有次序的，时间复杂性为O(n2)。因此，快速排序偏爱一个无次序的文件。令T(n)为分类n个记录所需之比较次数,设n=2k，则k=log2n，有：

T(n)≤cn+2T(n/2)(其中cn为进行一趟排序所需的时间)

T(n)≤cn+2(cn/2+2T(n/4))≤2cn+4T(n/4)……≤kcn+2kT(1)=O(nlog2n)5.快速排序算法的稳定性分析例：关键字序列{5，2，02}ij第一次交换后[02202]5→xj第二次交换后[022]02

j至此，完成排序，序列为{02,2,5}第一次交换[022]5ji02→x第一趟无交换

25第二趟5不稳定i02例K={46,79,56,38,40,84}

（1）它的初始堆是：

（2）快速排序第一趟结果：（1）467956384084384056794684（2）40，38，46，56，79，84NorthChinaElectricPowerUniversity各种排序方法的综合比较一、时间性能

按平均的时间性能来分，有三类排序方法：时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序；时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序；时间复杂度为O(n)的排序方法只有基数排序。2.当待排记录序列按关键字顺序有序时:

直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。NorthChinaElectricPowerUniversity二