《概述插入排序交换排序选择排序归并排序基数排序外排序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内排序与外排序内排序与外排序 区分区分规范：排序范：排序过程程能否全部在内存能否全部在内存进展。展。vv排序的排序的时间开开销 它是衡量算法好坏的它是衡量
3、算法好坏的最重要的最重要的标志。通常用算法志。通常用算法执行中的数行中的数据比据比较次数和数据挪次数和数据挪动次数来衡量次数来衡量 静静态态排序中的数据表的排序中的数据表的类类定定义义const int DefaultSize = 100;const int DefaultSize = 100;Template class datalist;Template class datalist;Templateclass ElementTemplateclass Elementfriend calss datalist;friend calss datalist;private:private: T
4、ype key; Type key; field otherdata; field otherdata; ; ; public: public:Type getKey( ) return key;Type getKey( ) return key; void setKey(const Type x) key=x; void setKey(const Type x) key=x;Element&operator=(Element&x)Element&operator=(Element&x) key=x-key;otherdata=x-otherdata; key=x-key;otherdata=
5、x-otherdata; 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) retur
6、n keykey; Type operator (Type &x) return keykey; templateclass datalisttemplateclass datalistprivate:private: Element*Vector; Element*Vector; int MaxSize,CurrentSize; int MaxSize,CurrentSize; int Partition(const int low,const int high) int Partition(const int low,const int high)public;public; datali
7、st (int MaxSz = DefaultSize):MaxSize( MaxSz) ; datalist (int MaxSz = DefaultSize):MaxSize( MaxSz) ; 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个
9、个对象象时，前，前面的面的V0,V1,Vi-1曾曾经排好序，排好序，此此时，用，用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
10、直接插入排序程序直接插入排序程序Templatevoid Templatevoid dataList:sortdataList:sort Elementtemp;int j; Elementtemp;int j; for(int i=1;iCurrentSize;i+) for(int i=1;i0;j-) for(int j=i;j0;j-) if (tempVectorj-1)Vectorj=Vectorj- if (tempVectorj-1)Vectorj=Vectorj-1;1; else break; else break; Vectorj=temp; Vectorj=temp;
11、直接插入排序的时间复杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次次数，数， 最好情况最好情况时两者分两者分别为n-1与与2(n-1)，最坏情况，最坏情况时两者分两者分别为vv KCN=1+2+.+n-1 = n(n-1)/2vv RMN= (1+2)+(2+2)+.+(n-1+2)vv = (n+4)(n-1)/2直接插入排序的稳定性vv直接插入排序是一种直接插入排序是一种稳定的排序方法。定的排序方法。vv原理：关原理：关键码一一样的两个的两个对象，在整象，在整个排序个排序过程中，不会程中，不会经过比比较而相互而相互交交换。折半插入排序(Binary Insert Sort)v
12、v根本思想：当插入第根本思想：当插入第i个个对象象时，前，前面的面的V0,V1,Vi-1曾曾经排好序，排好序，此此时，用折半，用折半查找法找法寻觅Vi的插入的插入位置移。位置移。折半插入排序程序折半插入排序程序template void datalist template void datalist :sort():sort() int left, right; Element temp; int left, right; Element temp; for (int i=1;iCurrentSize;i+) for (int i=1;iCurrentSize;i+) left=0;right
13、=i-1;temp=Vectori; left=0;right=i-1;temp=Vectori; while (left =right) while (left =right) int middle=(left+right)/2; int middle=(left+right)/2; if (temp Vectormiddle) if (temp =left; k-) for (int k=i-1;k=left; k-) Vectork+1=Vectork; Vectork+1=Vectork; Vectorleft = temp; Vectorleft = temp; 折半插入排序的时间复
14、杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次次数数vv 1. KCN 约为 n log 2 n，且与，且与对象象序列的初始序列的初始陈列无关列无关vv 当当n较大大时，总关关键码比比较次数次数比直接插入排序的最坏情况要好得多，比直接插入排序的最坏情况要好得多，但比其最好情况但比其最好情况时要差。要差。vv2. RMN与直接插入排序一与直接插入排序一样。折半插入排序的稳定性vv折半插入排序是一种折半插入排序是一种稳定的排序方法。定的排序方法。vv原理：关原理：关键码一一样的两个的两个对象，在整象，在整个排序个排序过程中，不会程中，不会经过比比较而相互而相互交交换。链表插入排序vv
15、根本思想：用根本思想：用链表来表示已排序的表来表示已排序的数据数据对象，当插入象，当插入Vi时，依次在，依次在链表中表中检查，找到，找到Vi应插入的位置，插入的位置，并修正相并修正相应的的链接指接指针。如此反复，。如此反复，直到直到Vn也插入到也插入到链表中排好序表中排好序为止。止。链链表插入排序的数据构造表插入排序的数据构造template class staticlinklist template class staticlinklist templateclass Elementtemplateclass Elementprivate:private: Type key; int lin
16、k; Type key; int link; public: public: Type getKey() return key; Type getKey() return key; void setKey(const Type x) key=x; void setKey(const Type x) key=x; int getLink()return link; int getLink()return link; void setLink(const int ptr)link=ptr; void setLink(const int ptr)link=ptr; 链链表插入排序的数据构造表插入排序
17、的数据构造templateclass staticlinklisttemplateclass staticlinklistprivate:private: Element * Vector; Element * Vector; int MaxSize, CurrentSize; int MaxSize, CurrentSize;public:public: staticlinklist(int MaxSz=DefaultSize): staticlinklist(int MaxSz=DefaultSize): MaxSize(MaxSize),CurrentSize(0); MaxSize(M
18、axSize),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 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 int staticlinklist template int staticlinklist : S
19、ort(): Sort() Vector0.key=MaxNum; Vector0.key=MaxNum; Vector0.link=1; Vector0.link=1; Vector1.link=0; Vector1.link=0; for(int i=2; i=CurrentSize; i+) for(int i=2; i=CurrentSize; i+) int current =Vector0.link; int pre = 0; int current =Vector0.link; int pre = 0; while (Vectorcurrent.key = while (Vect
20、orcurrent.key = Vectori.key) Vectori.key) pre=i; current=Vectorcurrent.link; pre=i; current=Vectorcurrent.link; Vectori.link=current; Vectori.link=current; Vectorpre.link=i; Vectorpre.link=i; 链表插入排序的时间复杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次次数数vv 1. KCN 最小最小为n-1，最大，最大为 n (n-1)/2vv 2. 对象挪象挪动次数次数为0 。vv链表插入排序方法
21、是表插入排序方法是稳定的。定的。希尔排序vv1959年由年由D.L. Shell提出，又称减少提出，又称减少增量排序增量排序(Diminishing-increment sort) 。vv根本思想：在插入排序中，只比根本思想：在插入排序中，只比较相相邻的的结点，一次比点，一次比较最多把最多把结点挪点挪动一个位置。假一个位置。假设对位置位置间隔隔较大大间隔隔的的结点点进展比展比较，使得，使得结点在比点在比较以以后可以一次跨后可以一次跨过较大的大的间隔，隔，这样就就可以提高排序的速度。可以提高排序的速度。希尔排序的根本过程vv设待排序的待排序的对象序列有象序列有n个个对象，首象，首先取一个整数先取
22、一个整数gapn作作为间隔，将隔，将全部全部对象分象分为gap个子序列，一切个子序列，一切间隔隔为gap的的对象放在同一个序列中，象放在同一个序列中，在每一个子序列中分在每一个子序列中分别施行直接插施行直接插入排序，然后减少入排序，然后减少间隔隔gap，如取，如取gap=gap/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 2
23、5* 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 datalist template void datalist :sort():sort() Elementtemp; Elementtemp; int gap=CurrentSize/2,i,j; int gap=CurrentSize/2,i,j; while(gap!=0) while(gap!=0) for (int i=gap; i C
24、urrentSize;i+) for (int 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; gap=gap/2; gap=gap/2; 希尔排序中gap的取法vvShell最初的方案是最初的方案是 gap= n/2, gap=gap/2，直到，直到gap=1.vvKnuth的
25、方案是的方案是gap = gap/3+1vv其它方案有，都取奇数其它方案有，都取奇数为好；或好；或gap互互质为好等等。好等等。希尔排序的时间复杂度vv对希希尔排序的复排序的复杂度的分析很困度的分析很困难，在，在特定情况下可以准确地估算关特定情况下可以准确地估算关键码的比的比较和和对象挪象挪动次数，但是思索到与增量次数，但是思索到与增量之之间的依的依赖关系，并要关系，并要给出完好的数学出完好的数学分析，目前分析，目前还做不到。做不到。vvKnuth的的统计结论是，平均比是，平均比较次数和次数和对象平均挪象平均挪动次数在次数在n1.25 与与1.6n1.25之之间。vv希希尔排序的排序的稳定性定
26、性vv 希希尔排序是一种不排序是一种不稳定的排序方法。定的排序方法。vv 如序列如序列 3 2 2* 59.3 交换排序vv根本原理，两两比根本原理，两两比较待排序的待排序的对象的象的关关键码，假，假设发生逆序，那么交生逆序，那么交换之，之，直到全部直到全部对象都排好序象都排好序为止。止。vv vv 两种常两种常见的交的交换排序排序vv起泡排序起泡排序(Bubble Sort)vv 快速排序快速排序(Quick Sort)起泡排序的根本过程vv假假假假设设待排序的待排序的待排序的待排序的n n个个个个对对象的序列象的序列象的序列象的序列为为V0,V1,., Vn-1V0,V1,., Vn-1，
27、起始，起始，起始，起始时时排序范排序范排序范排序范围围是从是从是从是从V0V0到到到到Vn-1Vn-1vv在当前的排序范在当前的排序范在当前的排序范在当前的排序范围围之内，自右至左之内，自右至左之内，自右至左之内，自右至左对对相相相相邻邻的两个的两个的两个的两个结结点依次点依次点依次点依次进进展比展比展比展比较较，让值较让值较大的大的大的大的结结点往下移点往下移点往下移点往下移( (下沉下沉下沉下沉) )，让值较让值较小的小的小的小的结结点往上移点往上移点往上移点往上移( (上冒上冒上冒上冒) )。每趟起泡都能保。每趟起泡都能保。每趟起泡都能保。每趟起泡都能保证证值值最小的最小的最小的最小的结
28、结点上移至最左点上移至最左点上移至最左点上移至最左边边，下一遍的排序范，下一遍的排序范，下一遍的排序范，下一遍的排序范围为围为从下一从下一从下一从下一结结点到点到点到点到Vn-1Vn-1。vv在整个排序在整个排序在整个排序在整个排序过过程中，最多程中，最多程中，最多程中，最多执执行行行行(n-1)(n-1)遍。但遍。但遍。但遍。但执执行的遍行的遍行的遍行的遍数能数能数能数能够够少于少于少于少于(n-1)(n-1)，这这是由于在是由于在是由于在是由于在执执行某一遍的各次比行某一遍的各次比行某一遍的各次比行某一遍的各次比较较没有出没有出没有出没有出现结现结点交点交点交点交换时换时，就不用，就不用，
29、就不用，就不用进进展下一遍的比展下一遍的比展下一遍的比展下一遍的比较较。起泡排序例如起泡排序例如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 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(Vector
30、j-1,vectorj) exchange=1; pass+; 起泡排序的时间复杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次数次数vv 1. KCN 为 n * (n-1) /2vv 2. RMN 为 3/2 * n* (n-1) 。vv起泡排序方法是起泡排序方法是稳定的。定的。快速排序的根本过程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
32、 25* 25 49快速排序的快速排序的递归递归算法算法template void QuickSort( const int left, const int right) if (leftright) int pivotpos = Partition (left, right); if (leftright) QuickSort(list,pivotpos+1,right);快速排序的快速排序的递归递归算法算法template int Partition( const int low, const int high) int pivotpos = low; Element pivot = Ve
33、ctorlow; for (int i=low+1; i=high; i+) if(Vectoripivot) pivotpos+; if (pivotpos!i)Swap(Vectorpivotpos, Vectori); Swap(Vectorlow, Vectorpivotpos); return pivotpos;快速排序的时间复杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次数次数vv 1. 平均平均计算算时间为O(n*log2n) ，实验阐明，明，快速排序是我快速排序是我们所所讨论过的内排序中，平均的内排序中，平均计算算时间最快。最快。vv 2. 最坏情况最坏情况总的关
34、的关键码比比较次数次数为 n* (n-1) /2，例如，例如，对一个曾一个曾经排序的序列排序的序列进展快展快速排序。速排序。vv快速排序是不快速排序是不稳定的排序方法。定的排序方法。vv 如序列如序列2, 3, 3*, 19.4 选择排序vv根本原理，将待排序的根本原理，将待排序的结点分点分为已已排序排序(初始初始为空空)和和为未排序两未排序两组，依次将未排序的依次将未排序的结点中点中值最小的最小的结点插入已排序的点插入已排序的组中。中。三种常见的选择排序 直接直接选择排序排序 锦标赛排序排序 堆排序堆排序直接选择排序的根本过程vv在一在一组对象象Vi到到Vn-1中中选择具有具有最小关最小关键
35、码的的对象象vv假假设它不是它不是这组对象中的第一个象中的第一个对象，那么将它与象，那么将它与这组对象中的第一象中的第一个个对象象对调。vv删除具有最小关除具有最小关键码的的对象，在剩象，在剩下的下的对象中反复第象中反复第(1)、(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
36、 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; jCurrentSize; j+) if (VectorjVectork) k=j; if (k!=i) Swap(Vectori, Vectork); 直接选择排序的时间复杂度vv思索关思索关键码的比的比较次数和次数和对象挪象挪动次数次数vv 1. KCN与与对象的初始象的初始陈列无关，列无关，总为 n* (n-1) /2vv 2. RMN与与
37、对象的初始象的初始陈列有关，最少列有关，最少为0，最大，最大为3(n-1) 。如：。如：n-1,0,1,2,., n-2vv直接直接选择排序是不排序是不稳定的排序方法。定的排序方法。锦标赛排序的根本过程vv在一在一组对象象Vi到到Vn-1中中选择具有具有最小关最小关键码的的对象象vv假假设它不是它不是这组对象中的第一个象中的第一个对象，那么将它与象，那么将它与这组对象中的第一象中的第一个个对象象对调。vv删除具有最小关除具有最小关键码的的对象，在剩象，在剩下的下的对象中反复第象中反复第(1)、(2)步，直步，直到剩余到剩余对象只需一个象只需一个为止。止。锦标赛锦标赛排序例如排序例如i (0)
38、(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锦标赛锦标赛排序的算法排序的算法template class DataNodetemplate class DataNodepublic:public: Type data; int index; int active; Type data; int index; int active; template void TournamentSort(template vo
39、id TournamentSort( Type a , int n) Type a , int n) DataNode *tree; DataNode *tree; DataNode item; DataNode item; int bottonRowSize = PowerOfTwo(n); int bottonRowSize = PowerOfTwo(n); int TreeSize = 2* bottomRowSize 1; int TreeSize = 2* bottomRowSize 1; int loadindex = bottomRowSize 1; int loadindex
40、= bottomRowSize 1; tree = new DataNode TreeSize; tree = new DataNode TreeSize; int j=0; int j=0; for (int i= loadindex; iTreeSize; i+) for (int i= loadindex; iTreeSize; i+) treei.index = i; treei.index = i; if (jn) treei.active =1 ; treei.data = aj+; if (jn) treei.active =1 ; treei.data = aj+; else
41、treei.active = 0; else treei.active = 0; i = loadindex; i = loadindex; 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 = treej; else tree(j-1)/2 = treej+1; else tree(j-1)
42、/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 (i) if
43、( 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思索关思索关键码的比的比较次数和次数和对象挪象挪动次数次数vv 1. 比比较次数次数为 O(log2n)vv 2.
44、对象的挪象的挪动次数不超越比次数不超越比较次数。次数。vv所以所以总的的时间复复杂度度为O(n log2n)vv锦标赛排序是排序是稳定的排序方法。定的排序方法。堆排序vv利用第利用第6章引章引见的堆及其运算，可的堆及其运算，可以方便地以方便地实现选择排序的思排序的思绪。vv堆排序分堆排序分为两个步两个步骤：vv根据初始根据初始输入，构成初始堆。入，构成初始堆。vv经过一系列的一系列的对象交象交换和重新和重新调整整进展排序。展排序。堆的定堆的定义完全二叉完全二叉树的数的数组表示表示 Ki K2i+1 & Ki K2i+2 Ki K2i+1 & Ki K2i+2堆排序例如堆排序例如i (0) (1
45、) (2) (3) (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: template void MaxHeap: FilterDown (const int i,const int EndOfHeap
46、 )FilterDown (const int i,const int EndOfHeap ) int current = i; int child = 2*i+1; int current = i; int child = 2*i+1; Type temp = heapi; Type temp = heapi; while ( child = EndOfHeap ) while ( child = EndOfHeap ) if ( child+1 EndOfHeap & if ( child+1 EndOfHeap & heapchildheapchild+1) child+=1; heap
47、child= heapchild) break; if ( temp= heapchild) break; else heapcurrent = heapchild; else heapcurrent = heapchild; current = child; child = 2 * child +1; current = child; child = 2 * child +1; heapcurrent = temp; heapcurrent = temp; 堆排序的算法堆排序的算法堆排序的算法堆排序的算法template void datalist :sort() template void
48、 datalist :sort() for (int i=(CurrentSize 1)/2; i=0; i-) for (int i=(CurrentSize 1)/2; i=0; i-) FilterDown(i, CurrentSize-1); FilterDown(i, CurrentSize-1); for (int i=(CurrentSize 1); i=1; i-) for (int i=(CurrentSize 1); i=1; i-) Swap( heap0, heapi); Swap( heap0, heapi); FilterDown(0,i-1); FilterDow
49、n(0,i-1); 堆排序的时间复杂度vv堆排序的堆排序的时间复复杂性性为O(n log2n) vv 空空间复复杂性性为 O(1)vv堆排序是不堆排序是不稳定的排序方法。定的排序方法。9.5 归并排序vv根本原理，根本原理，经过对两个或两个以上两个或两个以上的有序的有序结点序列的合并来点序列的合并来实现排序。排序。vv假假设是是对两个曾两个曾经排好序的序列的排好序的序列的合并来合并来实现排序，称排序，称为“两路两路归并并(2-way merging) 。两路归并的根本思想vv设有两个有序表有两个有序表A和和B，对象个数分象个数分别为al和和bl，变量量i和和j分分别是两表的是两表的当前指当前指
50、针。设表表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 62 72 93 两路两路归归并的算法并的算法template void merge( template void merge( datalist &
51、mergedList, datalist &mergedList, const int left, const int mid, const int right) const int left, const int mid, const int right) int i=left; j=mid+1; k=left; int i=left; j=mid+1; k=left; while(i=m & j=n) while(i=m & j=n) if (VectoriVectorj) if (VectoriVectorj) mergedList.Vectork=Vectori;i+;k+; merg
52、edList.Vectork=Vectori;i+;k+; else else mergedList.Vectork=Vectorj;j+;k+; mergedList.Vectork=Vectorj;j+;k+;if (I=mid)if (I=mid) for(int n1=k,n2=I;n2=mid;n1+;n2+) for(int n1=k,n2=I;n2=mid;n1+;n2+) mergedList.vectorn1=vectorn2; mergedList.vectorn1=vectorn2; 两种常见的归并排序 迭代的迭代的归并排序算法并排序算法 递归的表的表归并排序并排序迭代的
53、归并排序vv假假设初始的初始的对象序列有象序列有n个个对象，象，我我们首先把它看成是首先把它看成是n个个长度度为1的的有序子序列，先做两两有序子序列，先做两两归并，得到并，得到n/2个个长度度为2的的归并并项假假设n为奇奇数，那么最后一个有序子序列的数，那么最后一个有序子序列的长度度为1；再做两两；再做两两归并，并，如，如此反复，最后得到一个此反复，最后得到一个长度度为n的有的有序序列。序序列。归并排序的过程算法算法template void MergePass( datalist &mergedList, const int len) int i=0; while(i+2*len = Cur
54、rentSize-1) merge(mergedList,i, i+len-1, i+2*len-1); i+=2*len; if (I+len=CurrentSize-1)else for(int j=i;j=CurrentSize-1;j+) mergedlist.Vectorj=Vectorj;迭代的归并排序的时间复杂度vvMergeSort调用用 log2n 次，次，总的的时间复复杂度度为O(n log2n)vv空空间开开销为需求一个与原待排序需求一个与原待排序对象数象数组同同样大小的大小的辅助数助数组。vv vv迭代的迭代的归并排序是并排序是稳定的排序方法。定的排序方法。递归的表归并
55、排序vv首先把整个待排序序列划分首先把整个待排序序列划分为两个两个长度大致相等的部分，分度大致相等的部分，分别称称为左左子表和右子表。子表和右子表。对这些子表分些子表分别递归地地进展排序，然后再把排好序的展排序，然后再把排好序的两个子表两个子表进展展归并。并。递归的表归并的例如存存储储表示的表示的选择选择vv 在在归并并时，假，假设采用基于数采用基于数组的两的两路路归并算法，由于需求并算法，由于需求进展数展数组元元素的素的传送，影响了送，影响了归并的效率。并的效率。vv假假设对排序的排序的对象采用静象采用静态链表的表的存存储表示，那么可以得到一种有效表示，那么可以得到一种有效的的归并排序算法。
56、并排序算法。静静态链态链表的数据构造表的数据构造同同链表插入排序中的数据构造表插入排序中的数据构造template class staticlinklist private: struct Element Type key; field otherdata; int link; public: Type getKey() return key; void setKey(const Type x) key=x; void operator = (Element &item) this = item; void Swap(Element &x, void Swap(Element &x, Elem
57、ent &y) Element &y) Element temp=x; x=y; y=temp; Element temp=x; x=y; y=temp; public:public: staticlinklist(int MaxSz=DefaultSize): staticlinklist(int MaxSz=DefaultSize): MaxSize(MaxSize); MaxSize(MaxSize); void MakEmpty() void MakEmpty() Vector0.link=0; CurrentSize=0; Vector0.link=0; CurrentSize=0;
58、private:private: Element * Vector; Element * Vector; int MaxSize, CurrentSize; int MaxSize, CurrentSize; 静静态链态链表的数据构造表的数据构造 初始初始时，置一切的，置一切的Vectori.link = 0，即每个，即每个链表表结点都是一个独立点都是一个独立的的单链表。函数表。函数ListMerge()将两个将两个有序有序单链表表归并并为一个一个单链表的算表的算法。法。链表的归并算法template int staticlinklist:ListMerge ( const int start
59、1, const int start2) int k=0, i=start1, j=start2; while(i!=0 & j!=0) if (Vectori.key = Vectorj.key) Vectork.link=i;k=i;i=Vectori.link; else Vectork.key=j; k=j; j= Vectorj.link; if (i=0)Vectork.link=j; else list.Vectork.link=i; return list.Vector0.link;template int staticlinklist :sort(int left, int
60、right) if ( left = right ) return left; int middle = (left + right) / 2; return ListMerge (sort(left,middle), sort(middle+1,right);链表的归并排序的时间复杂度vv递归深度深度为O(log2n)，总的的时间复复杂度度为O(n log2n)vv对象的挪象的挪动次数次数为0vv vv链表的表的归并排序是并排序是稳定的排序方法。定的排序方法。9.6 基数排序vv根本原理，采用根本原理，采用“分配和分配和“搜集搜集的方法，用的方法，用对多关多关键码进展排展排序的思想序的思想实
61、现对单关关键码进展排展排序的方法。序的方法。vv下面先引下面先引见多关多关键码排序排序多关键码排序方法例如vv如如对扑克牌的排序扑克牌的排序vv每每张扑克牌有两个扑克牌有两个“关关键码：vv 花花样和面和面值vv 它它们之之间有次序的有次序的优先。先。vv对以上排序，可以先以上排序，可以先对花花样排序，或先排序，或先对面面值排序。排序。多关键码有序的概念vv思索思索对象序列象序列V0,V1,., Vn-1，每个，每个对象象Vi含含d个关个关键码(Ki1,Ki2,., Kid)。假。假设对序列中的恣意两个序列中的恣意两个对象象Vi和和Vj都有都有vv (Ki1,Ki2,., Kid) (Kj1,
62、Kj2,., Kjd)vv那么称序列那么称序列对关关键码(Ki1,Ki2,., Kid)有序，有序，且且K1称称为最高位关最高位关键码，Kd称称为最低位最低位关关键码。多关键码排序vv原理：根据原理：根据组成关成关键码的各位的的各位的值进展排展排序。序。vv实现基数排序的两种方法：基数排序的两种方法：vv 1 最高位最高位优先先(MSD)排序：从关排序：从关键码的的高位到低位高位到低位vv 2 最低位最低位优先先(LSD)排序：从关排序：从关键码的的低位到高位低位到高位vvMSD方法通常是一个方法通常是一个递归的的过程。程。多关键码排序续vvLSD和和MSD方法也可运用于方法也可运用于对一个关
63、一个关键码进展的排序。此展的排序。此时可将可将单关关键码Ki看看成是一个子关成是一个子关键码组：vv (Ki1,Ki2,., Kid)vv如如对关关键码取取值范范围为0到到999的一的一组对象，可看成是象，可看成是(K1,K2,K3)的的组合。合。vvMSD方法按方法按K1,K2,K3的的顺序序对一切一切对象象排序；排序；LSD方法按方法按K3 ,K2 , K1的的顺序序对一切一切对象排序。象排序。链式的基数排序vv基数排序是一种典型的基数排序是一种典型的LSD排序方法，它排序方法，它利用利用“分配和分配和“搜集两种运算搜集两种运算对单关关键码进展排序。展排序。vv此此时可将可将单关关键码K看成是一个子关看成是一个子关键码组：vv (Ki1,Ki2,., Kid)vv排序排序过程：程：设关关键码共有共有d位，位，让j= d, d-1,.,1, 依次依次执行行d次次“分配与分配与“搜集。搜集。
