数据结构与算法分析：第七章内排序

第8章内排序数据结构与算法分析1内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限2内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限3排序Sorting每个记录内都有一个关键码域,这个域的值正是比较器所用到的.线性顺序:比较.给定一组记录r1,r2,…,rn,其关键码分别为k1,k2,…,kn,排序问题就是要将这些记录排成顺序为rs1,rs2,…,rsn的一个序列,满足条件ks1ks2

…

ksn.4排序的稳定性在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的

例设49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——稳定排序后:13,27,38,49,49,65,76,97——不稳定5稳定排序的应用例股票交易系统考虑一种股票交易(清华紫光)1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；

2）股票交易系统按如下原则交易：

A）申购价高者先成交 B）申购价相同者按申购时间先后顺序成交申购队列：用线性表表示交易前：将申购队列按申购价排序，显然为满足交易原则B），要求排序方法是稳定的申购队列((09,10),(06,10.5),(033,9.8),(051,10))排序后：((06,10.5),(09,10),(051,10),(033,9.8))6排序方法分类按记录的存放位置分类有内排序：待排记录放在内存外排序：待排记录放在外存（数量大）性能分类简单但相对较慢的排序算法，(n2)先进的排序算法，(nlogn)一种特殊的方法，(n)待排序的记录序列通常有下列三种存贮方法顺序表静态链表：在排序过程，只需修改指针，不需要移动记录待排记录本身放在连续单元中，同时另建一索引表用于存放各记录存贮位置；排序时不移动记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置7排序算法性能分析分析排序算法时,需测量的代价:关键码比较的次数记录交换的次数8约定本章中排序算法的输入都是存储在数组中的一组记录将按关键字递增的顺序排序除非特别说明，本章中排序算法都适用于处理具有重复关键码的问题为简洁起见，对待排记录只写出其关键字序列关键字都采用了整数，或使用比较器假设定义了一个swap函数9内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限10插入排序示例11插入排序基本思想输入： 序列R1,R2,…,Rn

(凌乱无序)基本思想： 插入排序逐个处理待排序的记录。每个新记录与前面已排序的子序列进行比较，将它插入到子序列中正确的位置。12插入排序算法template<classElem,classComp>voidinssort(ElemA[],intn){for(inti=1;i<n;i++)for(intj=i;(j>0)&&(Comp::lt(A[j],A[j-1]));j--)swap(A,j,j-1);}BestCase:WorstCase:AverageCase:13插入排序算法分析最佳情况数组中的关键码按从小到大正序排列。没有记录移动总的比较次数为n-1次最佳情况下插入排序的时间代价为(n)14插入排序算法分析最差情况数组中的原始数据是逆序的。每个记录都必须移动到数组的顶端比较的次数为i交换的次数为i最差情况下总的比较次数为=

(n2)15插入排序算法分析－比较次数平均情况当处理到第i个记录时，内层for循环的执行次数依赖于该记录“无序”的程度逆置的数目（即数组中位于一个给定值之前，并比它大的值的数目）将决定比较及交换的次数平均情况下，在数组的前i-1个记录中有一半关键码比第i个记录的关键码值大平均的时间代价是最差情况的一半，为i=

(n2)16平均情况每执行一次内层for循环就要比较一次并交换一次每一轮的最后一次比较找到应该插入的位置，此时没有发生交换总排序次数是总比较次数减去n-1插入排序算法分析－交换次数最佳情况下为0，在最差及平均情况下为

(n2)17例子例:初始关键字:[49][38659776132749]i=1:[3849]659776132749]i=2:[384965]9776132749]i=3:[38496597]76132749]i=5:[133849657697]2749]i=6:[13273849657697]49]i=7:[1327384949657697]i=4:[3849657697]132749]无序源记录文件有序函数18插入排序算法的特点特点

1)算法简单

2)时间复杂度为（n2）3)初始序列基本（正向）有序时，时间复杂度为(n)4)稳定排序该方法适用于记录基本（正向）有序或n较少的情况19内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限20冒泡排序BubbleSort21冒泡排序基本思想输入： 序列R1,R2,…,Rn

(凌乱无序)基本思想：

比较并交换相邻元素对,直到所有元素都被放到正确的地方为止22冒泡排序代码template<classElem,classComp>voidbubsort(ElemA[],intn){for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}BestCase:WorstCase:AverageCase:23冒泡排序算法分析不考虑数组中结点的组合情况，内层for循环比较的次数总会是i，因此时间代价为(n2)冒泡排序的最佳、平均和最差情况的运行时间几乎是相同的假定交换的概率是平均情况下比较次数的一半，代价为(n2)24例:[4938659776132749]一趟:[38496576132749]97二趟:[384965132749]7697三趟:[3849132749]657697四趟:[38132749]49657697五趟:[132738]4949657697六趟:[1327]384949657697七趟:[13]27384949657697例子25冒泡排序特点没有什么特殊的价值一种相对较慢的排序、没有插入排序易懂，而且没有较好的最佳情况执行时间冒泡排序为后面将要讨论的一种更好的排序提供了基础26内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限27选择排序SelectionSort28选择排序的基本思想对于n个记录的数组，共进行n1趟排序。每一趟在ni+1个(i=1,2,…,n1)记录中通过ni次关键字的比较选出关键码最小的记录和第i个记录进行交换29选择排序的代码template<classElem,classComp>voidselsort(ElemA[],intn){for(inti=0;i<n-1;i++){

intlowindex=i;//Rememberitsindexfor(intj=n-1;j>i;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))

lowindex=j;//Putitinplaceswap(A,i,lowindex);}}BestCase:WorstCase:AverageCase:30选择排序算法分析实质是延迟交换的冒泡排序比较的次数仍为(n2)但是交换的次数要比冒泡法少得多最佳情况n-1次交换（重写）最差情况n-1次交换平均情况(n)3113 [38 65 97 76 49 27 49]一趟ik例：[49 38 65 97 76 13 27 49]初始关键字ik13 27[65 97 76 49 38 49]二趟13 2738[97 76 49 65 49]ik三趟13 273849[76 97 65 49]四趟13 27384949[97 65 76]五趟13 27384949 65[97 76]六趟13 27384949 6576 97 七趟例子32选择排序的特点对于处理那些作一次交换花费代价（时间）较多的问题，选择排序是很有效的33交换指向记录的指针34交换排序算法的时间代价InsertionBubbleSelectionComparisons:BestCase(n)Q(n2)Q(n2)AverageCaseQ(n2)Q(n2)Q(n2)WorstCaseQ(n2)Q(n2)Q(n2)SwapsBestCase00(n)AverageCaseQ(n2)Q(n2)(n)WorstCaseQ(n2)Q(n2)(n)35交换排序ExchangeSorting迄今为止介绍的排序算法依靠交换（比较）相邻的元素.交换排序的最小时间代价（平均来说）到底是多少呢?每对元素平均需要n(n-1)/2交换.36内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限37Shell排序38Shell排序的基本思想插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到(n)。shell排序即是从这两点出发，给出插入排序的改进方法基本思想 先将整个待排记录序列分割成若干个较小的子序列，对子序列分别进行插入排序；待整个序列中的记录“基本有序”时,再对全体记录进行一次插入排序39Shell排序代码//ModifiedversionofInsertionSorttemplate<classElem,classComp>voidinssort2(ElemA[],intn,intincr){for(inti=incr;i<n;i+=incr)for(intj=i;(j>=incr)&&(Comp::lt(A[j],A[j-incr]));j-=incr)swap(A,j,j-incr);}template<classElem,classComp>voidshellsort(ElemA[],intn){//Shellsort

for(inti=n/2;i>2;i/=2)//Foreachincr

for(intj=0;j<i;j++)//Sortsublists

inssort2<Elem,Comp>(&A[j],n-j,i);inssort2<Elem,Comp>(A,n,1);}40Shell排序的分析与特点性能分析分析Shell排序是很困难的，因此我们必须不加证明地承认Shell排序的平均运行时间是Θ(n1.5)(对于选择“增量每次除以3”递减)。选取其他增量序列可以减少这个上界。因此，Shell排序确实比插入排序或在第7.2节中讲到的任何一种运行时间为Θ(n2)的排序算法要快有人在大量实验的基础上推出，当N在某个特定范围内，所需比较和移动次数约为n1.3当n时，可减少到n(log2n)2增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于141待排序列为39，80，76，41，13，29，50，78，30，11，100，7，41，86步长因子分别取5、3、1，则排序过程如下：p=5 3980764113295078301110074186子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}

第一趟排序结果：29

7

41

301139

50

76

4113100

80

78

86

例子（续）p=3 2974130113950764113100807886子序列分别为{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。第二趟排序结果：13

73929

11

41

30

764150

868078

100例子（续）43p=1 1373929114130764150868078100

此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：7111329303941415076788086100

例子（续）44Shell排序的特点特点

1）时间复杂度，取决于增量序列的选择，选择的好，效率优于插入排序

2）不稳定排序方法

3）适用于n较大情况（中等大小规模）45内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限46快速排序Quicksort的基本思想1）选定一记录R，将所有其他记录关键字k’与记录R的关键字k比较,

若

k’<k则将记录换至R之前,若k’

>k则将记录换至R之后2）继续对R前后两部分记录进行快速排序，直至排序范围为1我们将待排序列按关键码作为轴值（pivot）分成两部分的过程，称为一次划分（一趟排序）47快速排序Quicksort代码template<classElem,classComp>voidqsort(ElemA[],inti,intj){if(j<=i)return;//Listtoosmall

intpivotindex=findpivot(A,i,j);swap(A,pivotindex,j);//Putpivotatend//kwillbefirstpositiononrightside

intk=partition<Elem,Comp>(A,i-1,j,A[j]);swap(A,k,j);//Putpivotinplace

qsort<Elem,Comp>(A,i,k-1);

qsort<Elem,Comp>(A,k+1,j);}template<classElem>intfindpivot(ElemA[],inti,intj){return(i+j)/2;}48QuicksortPartitiontemplate<classElem,classComp>intpartition(ElemA[],intl,intr,

Elem&pivot){

do{//Movetheboundsinuntiltheymeetwhile(Comp::lt(A[++l],pivot));while((r!=0)&&Comp::gt(A[--r],pivot));swap(A,l,r);//Swapout-of-placevalues}while(l<r);//Stopwhentheycross

swap(A,l,r);//Reverselastswapreturnl;//Returnfirstposonright}ThecostforpartitionisQ(n).49PartitionExamplepivot50QuicksortExample51CostofQuicksort最佳情况:每次将数列分割为等长的两部分.最差情况:糟糕的分割.平均情况:T(n)=n+1+1/(n-1)(T(k)+T(n-k))k=1n-152快速排序举例初始关键字：{49，38，65，97，76，13，27，49}pivotkey49jji1次交换后：{27，38，65，97，76，13，，49}iji2次交换后：{27，38，，97，76，13，65，49}ijj3次交换后：{27，38，13，97，76，，65，49}iji4次交换后：{27，38，13，，76，97，65，49}jij一趟完成后：{27，38，13，49，76，97，65，49}53

273865977613

27

49ii例待排记录

49

38659776132749

jj273865

97761365

49jj273813

4976976549jji被指定的关键字从后向前，将关键字与49比较，直至遇到小于49的关键字，前移从后向前，将关键字与49比较，直至遇到小于49的关键字，前移从前向后，将关键字与49比较，直至遇到大于49的关键字，后移从前向后，将关键字与49比较，直至遇到大于49的关键字，后移273813977613

6549ii从后向前，将关键字与49比较，直至遇到i=j,将49放至i处49一趟快速排序结束54[273813]49[769765

49]

[13

2738]49[49657697][13]

27[38]49[4965]76[97]1327384949657697两趟快速排序结束三趟快速排序结束快速排序结束55快速排序的特点轴值的取值影响性能时间复杂度为（nlog2n）不稳定快速排序的优化:更好的轴值对于小的子数列采用更好的排序算法用栈来模拟递归调用56内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限57Mergesort的基本思想基本思想：

将两个或多个有序表归并成一个有序表2路归并

1）设有n个待排记录，初始时将它们分为n个长度为1的有序子表；

2）

两两归并相邻有序子表，得到若干个长度2为的有序子表；

3）

重复2）直至得到一个长度为n的有序表58初始关键字序例：[49] [38] [65] [97] [76] [13] [27] [49][38,49] [65,97] [13,76] [27,49]第一趟[38,49,65,97] [13,27,49,76] 第二趟[13, 27, 38, 49, 49, 65, 76, 97]第三趟Mergesort举例59归并排序MergesortListmergesort(Listinlist){if(inlist.length()<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),

mergesort(l2));}60归并排序的实现template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],

intleft,intright){

intmid=(left+right)/2;if(left==right)return;

mergesort<Elem,Comp>(A,temp,left,mid);

mergesort<Elem,Comp>(A,temp,mid+1,right);

for(inti=left;i<=right;i++)//Copytemp[i]=A[i];

inti1=left;inti2=mid+1;for(intcurr=left;curr<=right;curr++){

if(i1==mid+1)//LeftexhaustedA[curr]=temp[i2++];elseif(i2>right)//RightexhaustedA[curr]=temp[i1++];

elseif(Comp::lt(temp[i1],temp[i2]))A[curr]=temp[i1++];elseA[curr]=temp[i2++];}}61优化归并排序template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],

intleft,intright){

if((right-left)<=THRESHOLD){

inssort<Elem,Comp>(&A[left],right-left+1);return;}

inti,j,k,mid=(left+right)/2;if(left==right)return;

mergesort<Elem,Comp>(A,temp,left,mid);

mergesort<Elem,Comp>(A,temp,mid+1,right);

for(i=mid;i>=left;i--)temp[i]=A[i];for(j=1;j<=right-mid;j++)

temp[right-j+1]=A[j+mid];

for(i=left,j=right,k=left;k<=right;k++)if(temp[i]<temp[j])A[k]=temp[i++];elseA[k]=temp[j--];}62MergesortCostMergesortcost:在最佳、平均、最差情况下，时间复杂度为(nlogn)当输入的待排序数据存储在链表中时，归并排序是一个很好的选择.归并排序需要两倍的空间代价.63归并排序的特点需要辅助空间:(n)整个归并需要[log2n]趟时间复杂度:(nlog2n)它是稳定的排序方法思想可以推广到“多-路归并“64内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限65堆排序的基本思想基本思想：一个基于“最大值堆”(max-heap)排序算法的思想是很直接的。首先将数组转化为一个满足堆定义的序列。然后将堆顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数组。应该注意的是每次应将堆顶的最大元素取出放到数组的最后。66堆排序Heapsorttemplate<classElem,classComp>voidheapsort(ElemA[],intn){//HeapsortElemmval;

maxheap<Elem,Comp>H(A,n,n);for(inti=0;i<n;i++)//NowsortH.removemax(mval);//Putmaxatend}用最大值堆,到最后结束时,就排出了一个由小到大排列的数组.67堆排序的性能分析堆排序的时间代价:建堆要用(n)时间并且n次取堆的最大元素要用(logn) (2nlogn)寻找K个最大元素的时间代价: (n+klogn)68HeapsortExample(1)69HeapsortExample(2)70堆排序的特点基于堆数据结构，具有许多优点：整棵树是平衡的，而且它的数组实现方式对空间的利用率也很高，可以利用有效的建堆函数一次性把所有值装入数组中。堆排序的最佳、平均、最差执行时间均为(nlogn)更适合于外排序，处理那些数据集太大而不适合在内存中排序的情况71内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限72分配排序Binsort

的基本思想一个简单、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];关键码用来确定一个记录在排序中的最终位置扩展分配排序算法的方法:允许关键码重复,也就是使数组B中的每个元素成为一个链表的头结点.允许关键码范围大于记录数n.73分配排序的代码template<classElem>voidbinsort(ElemA[],intn){List<Elem>B[MaxKeyValue];

Elemitem;for(i=0;i<n;i++)B[A[i]].append(A[i]);for(i=0;i<MaxKeyValue;i++)for(B[i].setStart();B[i].getValue(item);B[i].next())output(item);}74分配排序的性能分析时间代价：分配排序的时间代价初看起来是(n)。实际上时间代价为(n+MaxKeyValue)如果MaxKeyValue很大，那么这个算法的时间代价可能会为(n2)或更差。75基数排序RadixSort(1)76基数排序(2)template<classElem,classComp>voidradix(ElemA[],ElemB[],

intn,intk,intr,intcnt[]){//cnt[i]stores#ofrecordsinbin[i]

intj;for(inti=0,rtok=1;i<k;i++,rtok*=r){

for(j=0;j<r;j++)cnt[j]=0;

//Count#ofrecordsforeachbinfor(j=0;j<n;j++)cnt[(A[j]/rtok)%r]++;

//cnt[j]willbelastslotofbinj.for(j=1;j<r;j++)

cnt[j]=cnt[j-1]+cnt[j];

for(j=n-1;j>=0;j--)\B[--cnt[(A[j]/rtok)%r]]=A[j];for(j=0;j<n;j++)A[j]=B[j];}}77基数排序的例子78基数排序的时间代价Cost:Q(nk

+rk)n,k,和

r

之间有关系吗?如果关键码很小，那么基数排序的时间代价为Q(n).如果有n

个不同的关键码,那么关键码的长度最小要大于logn.因而,在一般情况下基数排序的时间代价为Q(nlogn)79内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限80对各种排序算法的实验比较(1)81对各种排序算法的实验比较(2)82内容排序术语与记号三种代价为(n2)的排序方法插入排序起泡排序选择排序交换排序算法的时间代价Shell排序快速排序归并排序堆排序分配排序和基数排序对各种排序算法的实验比较排序问题的下限83排序问题的下限我们想知道对所有可能的排序算法的时间代价的下限.排序算法的时间代价（在平均、最差情况）为O(n