概述插入排序交换排序选择排序归并排序基数排序外排序课件.ppt

《概述插入排序交换排序选择排序归并排序基数排序外排序课件.ppt》由会员分享，可在线阅读，更多相关《概述插入排序交换排序选择排序归并排序基数排序外排序课件.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、vv概述概述vv插入排序插入排序vv交换排序交换排序vv选择排序选择排序vv归并排序归并排序vv基数排序基数排序vv外排序外排序 第九章 排序什么是排序(Sorting)？vv简单地说，排序就是将一组杂乱无简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来。章的数据按一定的规律排列起来。vv排序是计算机中经常遇到的操作。排序是计算机中经常遇到的操作。排序的几个基本概念vv数据表数据表(Data List)待排序的数据对象的待排序的数据对象的有限集合。有限集合。vv关键码关键码(Key)作为排序依据的数据对象中作为排序依据的数据对象中的属性域。的属性域。vv主关键码主关键码 不同的数据对

2、象若不同的数据对象若关键码互不关键码互不相同相同，则这种关键码称为主关键码。，则这种关键码称为主关键码。vv排序的确切定义排序的确切定义 使一组任意排列的对象使一组任意排列的对象变成一组变成一组按关键码线性有序按关键码线性有序的对象。的对象。排序的几个基本概念vv排序算法的稳定性排序算法的稳定性 判断标准：关键码判断标准：关键码相同的数据对象在排序过程中是否保持前后相同的数据对象在排序过程中是否保持前后次序不变。如次序不变。如 2,2*,1，排序后若为，排序后若为1,2*,2 则该排序方法是不稳定的。则该排序方法是不稳定的。vv内排序与外排序内排序与外排序 区分标准：区分标准：排序过程排序过程

3、是否全部在是否全部在内存内存进行。进行。vv排序的时间开销排序的时间开销 它是衡量算法好坏的它是衡量算法好坏的最重要的标志。通常用算法执行中的最重要的标志。通常用算法执行中的数据比数据比较次数较次数和和数据移动次数数据移动次数来衡量来衡量 静态排序中的数据表的类定义静态排序中的数据表的类定义const const intint DefaultSizeDefaultSize=100;=100;Template class Template class datalistdatalist;Templateclass ElementTemplateclass Elementfriend friend

4、calsscalss datalistdatalist;private:private:Type key;Type key;field field otherdataotherdata;public:public:Type Type getKeygetKey()return key;()return key;void void setKey(constsetKey(const Type x)key=x;Type x)key=x;Element&operator=(Element&x)Element&operator=(Element&x)key=x-key=x-key;otherdatakey

5、;otherdata=x-=x-otherdataotherdata;Type operator=(Type&x)Type operator=(Type&x)return key=x-key;return key=x-key;Type operator=(Type&x)return keykey;Type operator=(Type&x)return keykey;Type operator=(Type&x)return key=x-key;Type operator=(Type&x)return key=x-key;Type operator (Type&x)return keykey;T

6、ype operator (Type&x)return keykey;templateclass templateclass datalistdatalist private:private:Element*Vector;Element*Vector;intint MaxSize,CurrentSizeMaxSize,CurrentSize;intint Partition(const Partition(const intint low,const low,const intint high)high)public;public;datalistdatalist(intint MaxSzMa

7、xSz=DefaultSize):MaxSizeDefaultSize):MaxSize(MaxSzMaxSz););void Swap(Element&x,Element&y)void Swap(Element&x,Element&y)Element temp=x;x=y;y=temp;Element temp=x;x=y;y=temp;void Sort();void Sort();9.2 插入排序(Insert Sorting)vv基本原理，每步将一个待排序的对基本原理，每步将一个待排序的对象，按其关键码大小，插入到前面象，按其关键码大小，插入到前面已经排好序的一组对象适当位置上，已经排

8、好序的一组对象适当位置上，直到对象全部插入为止。直到对象全部插入为止。三种常见的插入排序vv分类原理，根据往已经排好序的有分类原理，根据往已经排好序的有序数据表中寻找插入位置的方法的序数据表中寻找插入位置的方法的不同而区分。不同而区分。vv 直接插入排序直接插入排序(Insert Sort)vv 折半插入排序折半插入排序(Binary Insert Sort)vv 链表插入排序链表插入排序 vv 希尔排序希尔排序(Shell Sort)直接插入排序(Insert Sort)vv基本思想：当插入第基本思想：当插入第i个对象时，前个对象时，前面的面的V0,V1,Vi-1已经排好序，已经排好序，此时

9、，用此时，用vi的关键码与的关键码与Vi-1,Vi-2,的关键码顺序进行比较，找到的关键码顺序进行比较，找到插入位置即将插入位置即将Vi插入，原来位置上插入，原来位置上对象向后顺移。对象向后顺移。直接插入排序举例i (0)(1)(2)(3)(4)(5)temp 21 25 49 25*16 08 251 21 25 49 25*16 08 492 21 25 49 25*16 08 25*3 21 25 25*49 16 08 164 16 21 25 25*49 08 08 5 08 16 21 25 25*49 直接插入排序程序直接插入排序程序Templatevoid Templatevo

10、id dataListdataList:sort:sort Element Elementtemp;inttemp;int j;j;for(intfor(int i=1;i i=1;i0;j-)j=i;j0;j-)if(tempVectorj-1)Vectorj=Vectorj-if(tempVectorj-1)Vectorj=Vectorj-1;1;else break;else break;Vectorj=temp;Vectorj=temp;直接插入排序的时间复杂度vv考虑关键码的比较次数和对象移动次考虑关键码的比较次数和对象移动次数，数，最好情况时两者分别为最好情况时两者分别为n-1与与

11、2(n-1)，最坏情况时两者分别为最坏情况时两者分别为vv KCN=1+2+.+n-1=n(n-1)/2vv RMN=(1+2)+(2+2)+.+(n-1+2)=(n+4)(n-1)/2直接插入排序的稳定性vv直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。vv原理：关键码相同的两个对象，在整原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互个排序过程中，不会通过比较而相互交换。交换。折半插入排序(Binary Insert Sort)vv基本思想：当插入第基本思想：当插入第i个对象时，前个对象时，前面的面的V0,V1,Vi-1已经排好序，已经排好序，此时，用

12、折半查找法寻找此时，用折半查找法寻找Vi的插入的插入位置移。位置移。折半插入排序程序折半插入排序程序template void template void datalistdatalist :sort():sort()intint left,right;Element temp;left,right;Element temp;for(for(intint i=1;i i=1;iCurrentSize;iCurrentSize;i+)+)left=0;right=i-1;temp=Vectori;left=0;right=i-1;temp=Vectori;while(left =right)wh

13、ile(left =right)intint middle=(left+right)/2;middle=(left+right)/2;if(temp Vectormiddle)if(temp=left;k-)k=i-1;k=left;k-)Vectork+1=Vectork;Vectork+1=Vectork;Vectorleft=temp;Vectorleft=temp;折半插入排序的时间复杂度vv考虑关键码的比较次数和对象移动次考虑关键码的比较次数和对象移动次数数 1.KCN 约为约为 n log 2 n，且与对象序列且与对象序列的初始排列无关的初始排列无关 当当n较大时，总关键码比较次数

14、比直较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但接插入排序的最坏情况要好得多，但比其最好情况时要差。比其最好情况时要差。2.RMN与直接插入排序相同。与直接插入排序相同。折半插入排序的稳定性vv折半插入排序是一种稳定的排序方法。折半插入排序是一种稳定的排序方法。vv原理：关键码相同的两个对象，在整原理：关键码相同的两个对象，在整个排序过程中，不会通过比较而相互个排序过程中，不会通过比较而相互交换。交换。链表插入排序vv基本思想：用链表来表示已排序的基本思想：用链表来表示已排序的数据对象，当插入数据对象，当插入Vi时，依次在链时，依次在链表中检查，找到表中检查，找到Vi应插入的位

15、置，应插入的位置，并修改相应的链接指针。如此重复，并修改相应的链接指针。如此重复，直到直到Vn也插入到链表中排好序为止。也插入到链表中排好序为止。链表插入排序的数据结构链表插入排序的数据结构template class template class staticlinkliststaticlinklist templateclass Elementtemplateclass Elementprivate:private:Type key;Type key;intint link;link;public:public:Type Type getKeygetKey()return key;()re

16、turn key;void void setKey(constsetKey(const Type x)key=x;Type x)key=x;intint getLink()returngetLink()return link;link;void void setLink(constsetLink(const intint ptr)linkptr)link=ptrptr;链表插入排序的数据结构链表插入排序的数据结构templateclass templateclass staticlinkliststaticlinklist private:private:Element *Vector;Ele

17、ment *Vector;intint MaxSizeMaxSize,CurrentSizeCurrentSize;public:public:staticlinklist(intstaticlinklist(int MaxSzMaxSz=DefaultSizeDefaultSize):):MaxSize(MaxSize),CurrentSize(0);MaxSize(MaxSize),CurrentSize(0);链表插入排序示例链表插入排序示例i index (0)(1)(2)(3)(4)(5)(6)key MaxNum 21 25 49 25*16 8 link 1 0 0 0 0 0

18、02 link 1 2 0 0 0 0 03 link 1 2 3 0 0 0 04 link 1 2 4 0 3 0 05 link 5 2 4 0 3 1 06 link 6 2 4 0 3 1 5链表插入排序的算法链表插入排序的算法template template intint staticlinkliststaticlinklist :Sort():Sort()Vector0.key=Vector0.key=MaxNumMaxNum;Vector0.link=1;Vector0.link=1;Vector1.link=0;Vector1.link=0;for(intfor(int i

19、=2;i=i=2;i=CurrentSizeCurrentSize;i+);i+)intint current=Vector0.link;current=Vector0.link;intint pre=0;pre=0;while(Vectorcurrent.key=while(Vectorcurrent.key=Vectori.key)Vectori.key)pre=i;current=Vectorcurrent.link;pre=i;current=Vectorcurrent.link;Vectori.link=current;Vectori.link=current;Vectorpre.l

20、ink=i;Vectorpre.link=i;链表插入排序的时间复杂度vv考虑关键码的比较次数和对象移动次考虑关键码的比较次数和对象移动次数数 1.KCN 最小为最小为n-1，最大为最大为 n(n-1)/2 2.对象移动次数为对象移动次数为0。链表插入排序方法是稳定的。链表插入排序方法是稳定的。希尔排序vv1959年由年由D.L.Shell提出，又称缩小提出，又称缩小增量排序增量排序(Diminishing-increment sort)。vv基本思想：在插入排序中，只比较相基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔

21、较大距离一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就后能够一次跨过较大的距离，这样就可以提高排序的速度。可以提高排序的速度。希尔排序的基本过程vv设待排序的对象序列有设待排序的对象序列有n个对象，首个对象，首先取一个整数先取一个整数gapn作为间隔，将作为间隔，将全部对象分为全部对象分为gap个子序列，所有距个子序列，所有距离为离为gap的对象放在同一个序列中，的对象放在同一个序列中，在每一个子序列中分别施行直接插在每一个子序列中分别施行直接插入排序，然后缩小间隔入排序，然后缩小间隔gap，如取如取gap=ga

22、p/2，重复上述的子序列划重复上述的子序列划分和排序工作，直到最后分和排序工作，直到最后取取gap为为1为止。为止。希尔排序示例希尔排序示例i (0)(1)(2)(3)(4)(5)gap 21 25 49 25*16 08 1 21 -25*3 25 -16 49 -08 21 16 08 25*25 492 21 -08 -25 2 16 -25*-49 08 16 21 25*25 493 08 16 21 25*25 49 1 08 16 21 25*25 49希尔排序的算法希尔排序的算法template void template void datalistdatalist :sort

23、():sort()Elementtemp;Elementtemp;intint gap=CurrentSize/2,i,j;gap=CurrentSize/2,i,j;while(gap!=0)while(gap!=0)for(for(intint i=gap;i i=gap;i=gap;j-=gap)for(j=i;j=gap;j-=gap)if(tempVectorj-gap)if(tempVectorj-gap)Vectorj=Vectorj-gap;Vectorj=Vectorj-gap;else break;else break;Vectorj=temp;Vectorj=temp;g

24、ap=gap/2;gap=gap/2;希尔排序中gap的取法vvShell最初的方案是最初的方案是 gap=n/2,gap=gap/2，直到直到gap=1.vvKnuth的的方案是方案是gap=gap/3+1vv其它方案有，都取奇数为好；或其它方案有，都取奇数为好；或gap互质为好等等。互质为好等等。希尔排序的时间复杂度vv对希尔排序的复杂度的分析很困难，在对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键码的比特定情况下可以准确地估算关键码的比较和对象移动次数，但是考虑到与增量较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学之间的依赖关系，并要给出完整的数学分

25、析，目前还做不到。分析，目前还做不到。vvKnuth的统计结论是，平均比较次数和的统计结论是，平均比较次数和对象平均移动次数在对象平均移动次数在n1.25 与与1.6n1.25之间。之间。vv希尔排序的稳定性希尔排序的稳定性 希尔排序是一种不稳定的排序方法。希尔排序是一种不稳定的排序方法。如序列如序列 3 2 2*59.3 交换排序vv基本原理，两两比较待排序的对象的基本原理，两两比较待排序的对象的关键码，如果发生逆序，则交换之，关键码，如果发生逆序，则交换之，直到全部对象都排好序为止。直到全部对象都排好序为止。两种常见的交换排序两种常见的交换排序vv起泡排序起泡排序(Bubble Sort)

26、vv 快速排序快速排序(Quick Sort)起泡排序的基本过程vv假设待排序的假设待排序的假设待排序的假设待排序的n n个对象的序列为个对象的序列为个对象的序列为个对象的序列为V0,V1,.,Vn-1V0,V1,.,Vn-1，起始时排序范围是从起始时排序范围是从起始时排序范围是从起始时排序范围是从V0V0到到到到Vn-1Vn-1vv在当前的排序范围之内，自右至左对相邻的两个结在当前的排序范围之内，自右至左对相邻的两个结在当前的排序范围之内，自右至左对相邻的两个结在当前的排序范围之内，自右至左对相邻的两个结点依次进行比较，让值较大的结点往下移点依次进行比较，让值较大的结点往下移点依次进行比较，

27、让值较大的结点往下移点依次进行比较，让值较大的结点往下移(下沉下沉下沉下沉)，让值较小的结点往上移让值较小的结点往上移让值较小的结点往上移让值较小的结点往上移(上冒上冒上冒上冒)。每趟起泡都能保证。每趟起泡都能保证。每趟起泡都能保证。每趟起泡都能保证值最小的结点上移至最左边，下一遍的排序范围为值最小的结点上移至最左边，下一遍的排序范围为值最小的结点上移至最左边，下一遍的排序范围为值最小的结点上移至最左边，下一遍的排序范围为从下一结点到从下一结点到从下一结点到从下一结点到Vn-1Vn-1。vv在整个排序过程中，最多执行在整个排序过程中，最多执行在整个排序过程中，最多执行在整个排序过程中，最多执行

28、(n-1)(n-1)遍。但执行的遍。但执行的遍。但执行的遍。但执行的遍数可能少于遍数可能少于遍数可能少于遍数可能少于(n-1)(n-1)，这是因为在执行某一遍的各这是因为在执行某一遍的各这是因为在执行某一遍的各这是因为在执行某一遍的各次比较没有出现结点交换时，就不用进行下一遍的次比较没有出现结点交换时，就不用进行下一遍的次比较没有出现结点交换时，就不用进行下一遍的次比较没有出现结点交换时，就不用进行下一遍的比较。比较。比较。比较。起泡排序示例起泡排序示例i (0)(1)(2)(3)(4)(5)21 25 49 25*16 08 1 08 21 25 49 25*16 2 08 16 21 25

29、 49 25*3 08 16 21 25 25*49 4 08 16 21 25 25*49起泡排序的算法起泡排序的算法Templatevoid datalist:sort()int pass=1;int exchange=1;while(pass=pass;j-)if(Vectorj-1Vectorj)swap(Vectorj-1,vectorj)exchange=1;pass+;起泡排序的时间复杂度vv考虑关键码的比较次数和对象移动考虑关键码的比较次数和对象移动次数次数 1.KCN 为为 n*(n-1)/2 2.RMN 为为 3/2*n*(n-1)。起泡排序方法是稳定的。起泡排序方法是稳定

30、的。快速排序的基本过程vv快速排序法是一种所需比较次数较少，快速排序法是一种所需比较次数较少，目前在内部排序中速度较快的方法。目前在内部排序中速度较快的方法。vv其思想是取待排序的结点序列中某个其思想是取待排序的结点序列中某个结点的值作为控制值，采用某种方法把结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。然后分点的值都大于等于这个控制值。然后分别对这两个子序列重复实施上述方法别

31、对这两个子序列重复实施上述方法.快速排序示例快速排序示例i (0)(1)(2)(3)(4)(5)pivot（基基准准)21 25 49 25*16 08 211 08 16 21 25*25 49 08(左左),25*(右右)2 08 16 21 25*25 49 25(右右)3 08 16 21 25*25 49 4 08 16 21 25*25 49快速排序的递归算法快速排序的递归算法template void QuickSort(const int left,const int right)if(leftright)int pivotpos=Partition(left,right);i

32、f(leftright)QuickSort(list,pivotpos+1,right);快速排序的递归算法快速排序的递归算法template int Partition(const int low,const int high)int pivotpos=low;Element pivot=Vectorlow;for(int i=low+1;i=high;i+)if(Vectoripivot)pivotpos+;if(pivotpos!i)Swap(Vectorpivotpos,Vectori);Swap(Vectorlow,Vectorpivotpos);return pivotpos;快速

33、排序的时间复杂度vv考虑关键码的比较次数和对象移动次数考虑关键码的比较次数和对象移动次数 1.平均计算时间为平均计算时间为O(n*log2n)，实验表明，实验表明，快速排序是我们所讨论过的内排序中，平均快速排序是我们所讨论过的内排序中，平均计算时间最快。计算时间最快。2.最坏情况总的关键码比较次数为最坏情况总的关键码比较次数为 n*(n-1)/2，例如，对一个已经排序的序列进行快速例如，对一个已经排序的序列进行快速排序。排序。快速排序是不稳定的排序方法。快速排序是不稳定的排序方法。如序列如序列2,3,3*,19.4 选择排序vv基本原理，将待排序的结点分为已基本原理，将待排序的结点分为已排序排

34、序(初始为空初始为空)和为未排序两组，和为未排序两组，依次将未排序的结点中值最小的结依次将未排序的结点中值最小的结点插入已排序的组中。点插入已排序的组中。三种常见的选择排序vv 直接选择排序直接选择排序vv 锦标赛排序锦标赛排序vv 堆排序堆排序直接选择排序的基本过程vv在一组在一组对象对象Vi到到Vn-1中中选择具有选择具有最小关键码的对象最小关键码的对象vv若它不是这组对象中的第一个对象，若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象则将它与这组对象中的第一个对象对调。对调。vv删除具有最小关键码的对象，在剩删除具有最小关键码的对象，在剩下的对象中重复第下的对象中重复第(1

35、)、(2)步，直步，直到剩余对象只有一个为止。到剩余对象只有一个为止。直接选择排序示例直接选择排序示例i (0)(1)(2)(3)(4)(5)k 21 25 49 25*16 08 50 08 25 49 25*16 21 41 08 16 49 25*25 21 52 08 16 21 25*25 49 3 3 08 16 21 25*25 49 44 08 16 21 25*25 49 直接选择排序的算法直接选择排序的算法template void datalist :sort()for(int i=0;iCurrentSize-1;i+)int k=i;for(int j=i+1;jCu

36、rrentSize;j+)if(VectorjVectork)k=j;if(k!=i)Swap(Vectori,Vectork);直接选择排序的时间复杂度vv考虑关键码的比较次数和对象移动次数考虑关键码的比较次数和对象移动次数 1.KCN与对象的初始排列无关，总为与对象的初始排列无关，总为 n*(n-1)/2 2.RMN与对象的初始排列有关，最少为与对象的初始排列有关，最少为0，最大，最大为为3(n-1)。如：如：n-1,0,1,2,.,n-2直接选择排序是不稳定的排序方法。直接选择排序是不稳定的排序方法。锦标赛排序的基本过程vv在一组在一组对象对象Vi到到Vn-1中中选择具有选择具有最小关键

37、码的对象最小关键码的对象vv若它不是这组对象中的第一个对象，若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象则将它与这组对象中的第一个对象对调。对调。vv删除具有最小关键码的对象，在剩删除具有最小关键码的对象，在剩下的对象中重复第下的对象中重复第(1)、(2)步，直步，直到剩余对象只有一个为止。到剩余对象只有一个为止。锦标赛排序示例锦标赛排序示例i (0)(1)(2)(3)(4)(5)(6)21 25 49 25*16 08 63?21 25*08 63 21 08 08 21 25 49 25*16 08 63?21 25*16 63 21 16 16锦标赛排序的算法锦标赛排序

38、的算法template class template class DataNodeDataNode public:public:Type data;Type data;intint index;index;intint active;active;template void template void TournamentSortTournamentSort(Type a,Type a,intint n)n)DataNodeDataNode *tree;*tree;DataNodeDataNode item;item;intint bottonRowSizebottonRowSize=Powe

39、rOfTwo(nPowerOfTwo(n););intint TreeSizeTreeSize=2*=2*bottomRowSizebottomRowSize 1;1;intint loadindexloadindex=bottomRowSizebottomRowSize 1;1;tree=new tree=new DataNodeDataNode TreeSizeTreeSize;intint j=0;j=0;for(for(intint i=i=loadindexloadindex;i;iTreeSizeTreeSize;i+);i+)treei.index=i;treei.index=i

40、;if(jn)treei.active=1;treei.data=aj+;if(jn)treei.active=1;treei.data=aj+;else treei.active=0;else treei.active=0;i=i=loadindexloadindex;while(i)while(i)j=i;j=i;while(j2*i)while(j2*i)if(!treej+1.active|treej.data if(!treej+1.active|treej.data treej+1.data)treej+1.data)tree(j-1)/2=treej;tree(j-1)/2=tr

41、eej;else tree(j-1)/2=treej+1;else tree(j-1)/2=treej+1;j+=2;j+=2;i=(i-1)/2;i=(i-1)/2;for(i=0;in-1;i+)ai=tree0.data;treetree0.index.active=0;UpdateTree(tree,tree0.index);an-1=tree0.data;template void UpdateTree (DataNode *tree,int i)if(i%2=0)tree(i-1)/2=treei-1;else tree(i-1)/2=treei+1;i=(i-1)/2;while

42、(i)if(i%2=0)j=i-1;else j=i+1;if(!treei.active|!treej.active)if(treei.active)tree(i-1)/2=treei;else tree(i-1)/2=treej;else if(treei.data treej.data)tree(i-1)/2=treei;else tree(i-1)/2=treej;i=(i-1)/2;锦标赛排序的时间复杂度vv考虑关键码的比较次数和对象移动考虑关键码的比较次数和对象移动次数次数 1.比较次数为比较次数为 O(log2n)2.对象的移动次数不超过比较次数。对象的移动次数不超过比较次数。所

43、以总的时间复杂度为所以总的时间复杂度为O(n log2n)锦标赛排序是稳定的排序方法。锦标赛排序是稳定的排序方法。堆排序vv利用第利用第6章介绍的堆及其运算，可章介绍的堆及其运算，可以方便地实现选择排序的思路。以方便地实现选择排序的思路。vv堆排序分为两个步骤：堆排序分为两个步骤：vv根据初始输入，形成初始堆。根据初始输入，形成初始堆。vv通过一系列的对象交换和重新调整通过一系列的对象交换和重新调整进行排序。进行排序。堆的定义堆的定义完全二叉树的数组表示完全二叉树的数组表示 Ki K2i+1&Ki K2i+2 Ki K2i+1&Ki K2i+2堆排序示例堆排序示例i (0)(1)(2)(3)(

44、4)(5)21 25 49 25*16 08 初始堆为：初始堆为：21 25 4925*16 08调整后的最大堆为：调整后的最大堆为：49 25 2125*16 08堆排序示例（续）堆排序示例（续）交换交换0号与号与5号元素后为：号元素后为：08 25 2125*16 49调整后的堆为：调整后的堆为：25 25*2108 16 最大堆的向下调整算法最大堆的向下调整算法最大堆的向下调整算法最大堆的向下调整算法template void MaxHeap:FilterDown(const int i,const int EndOfHeap)int current=i;int child=2*i+1;

45、Type temp=heapi;while(child=EndOfHeap)if(child+1 EndOfHeap&heapchild=heapchild)break;else heapcurrent=heapchild;current=child;child=2*child+1;heapcurrent=temp;堆堆堆堆排序的算法排序的算法排序的算法排序的算法template void datalist:sort()for(int i=(CurrentSize 1)/2;i=0;i-)FilterDown(i,CurrentSize-1);for(int i=(CurrentSize 1)

46、;i=1;i-)Swap(heap0,heapi);FilterDown(0,i-1);堆排序的时间复杂度vv堆排序的时间复杂性为堆排序的时间复杂性为O(n log2n)vv 空间复杂性为空间复杂性为 O(1)堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。9.5 归并排序vv基本原理，通过对两个或两个以上基本原理，通过对两个或两个以上的有序结点序列的合并来实现排序。的有序结点序列的合并来实现排序。vv如果是对两个已经排好序的序列的如果是对两个已经排好序的序列的合并来实现排序，称为合并来实现排序，称为“两路归并两路归并”(2-way merging)。两路归并的基本思想vv设有两个有序表设

47、有两个有序表A和和B，对象个数分对象个数分别为别为al和和bl，变量变量i和和j分别是两表的分别是两表的当前指针。设表当前指针。设表C是归并后的新有是归并后的新有序表，变量序表，变量k是它的当前指针。是它的当前指针。i和和j对对A和和B遍历时，依次将关键码小的遍历时，依次将关键码小的对象放对象放到到C中，当中，当A或或B遍历结束时，遍历结束时，将另一个表的剩余部分照抄到新表将另一个表的剩余部分照抄到新表中。中。两路归并的示例 initList 08 21 25 25*49 62 72 93 16 37 54归并后为归并后为 mergedList 08 16 21 25 25*37 49 54

48、62 72 93 两路归并的算法两路归并的算法template void merge(template void merge(datalistdatalist&mergedListmergedList,const const intint left,const left,const intint mid,const mid,const intint right)right)intint i=left;j=mid+1;k=left;i=left;j=mid+1;k=left;while(i=m&j=n)while(i=m&j=n)if(VectoriVectorj)if(VectoriVecto

49、rj)mergedList.VectorkmergedList.Vectork=Vectori;i+;k+;=Vectori;i+;k+;else else mergedList.VectorkmergedList.Vectork=Vectorj;j+;k+;=Vectorj;j+;k+;if(I=mid)if(I=mid)for(intfor(int n1=k,n2=I;n2=mid;n1+;n2+)n1=k,n2=I;n2=mid;n1+;n2+)mergedList.vectorn1=vectorn2;mergedList.vectorn1=vectorn2;两种常见的归并排序vv 迭代

50、的归并排序算法迭代的归并排序算法vv 递归的表归并排序递归的表归并排序迭代的归并排序vv假设初始的对象序列有假设初始的对象序列有n个对象，个对象，我们首先把它看成是我们首先把它看成是n个长度为个长度为1的的有序子序列，先做两两归并，得到有序子序列，先做两两归并，得到n/2个长度为个长度为2的归并项（如果的归并项（如果n为奇为奇数，则最后一个有序子序列的长度数，则最后一个有序子序列的长度为为1）；再做两两归并，）；再做两两归并，如此，如此重复，最后得到一个长度重复，最后得到一个长度为为n的有序的有序序列。序列。归并排序的过程算法算法template void MergePass(datalist