第九章排序.ppt

第九章第九章 排序排序概述概述 插入排序插入排序快速排序快速排序交换排序交换排序（起泡排序）（起泡排序）选择排序选择排序归并排序归并排序1概述概述排排序序：将将一一组组杂杂乱乱无无章章的的数数据据按按一一定定的的规规律律顺顺次次排列起来。排列起来。数据表数据表(datalist):它是待排序数据元素的有限集合。它是待排序数据元素的有限集合。排排序序码码(key):通通常常数数据据元元素素有有多多个个属属性性域域,即即多多个个数数据据成成员员组组成成,其其中中有有一一个个属属性性域域可可用用来来区区分分元元素素,作作为为排排序序依依据据。该该域域即即为为排排序序码码。每每个个数数据据表表用用哪哪个个属属性性域域作作为为排排序序码码，要要视视具具体体的的应应用用需需要要而而定。定。2排序算法的稳定性排序算法的稳定性:如果在元素序列中有两如果在元素序列中有两 个元个元素素ri和和rj,它们的排序码它们的排序码 ki=kj,且在排序之且在排序之前前,元素元素ri排在排在rj前面。如果在排序之后前面。如果在排序之后,元素元素ri仍在元素仍在元素rj的前面的前面,则称这个排序方法是则称这个排序方法是稳定稳定的的,否则称这个排序方法是不稳定的。否则称这个排序方法是不稳定的。内排序与外排序内排序与外排序:内排序内排序是指在排序期间数据元是指在排序期间数据元素全部存放在素全部存放在内存内存的排序；的排序；外排序外排序是指在排序期是指在排序期间全部元素个数太多，不能同时存放在内存，必间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在须根据排序过程的要求，不断在内、外存内、外存之间移之间移动的排序。动的排序。3排序的时间开销排序的时间开销:排序的时间开销是衡量算法好排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执坏的最重要的标志。排序的时间开销可用算法执行中的行中的数据比较次数数据比较次数与与数据移动次数数据移动次数来衡量。来衡量。算法运行时间代价的大略估算算法运行时间代价的大略估算一般一般都都按平均情况按平均情况进行估算。对于那些受元素排序码序列进行估算。对于那些受元素排序码序列初始排列初始排列及及元素个数元素个数影响较大的算法，需要按影响较大的算法，需要按最好最好情况和情况和最坏最坏情况进行估算。情况进行估算。算法执行时所需的附加存储算法执行时所需的附加存储:评价算法好坏的另评价算法好坏的另一标准。一标准。4待排序数据表的类定义待排序数据表的类定义#include const int DefaultSize=100;template class Element/数据表元素定义public:T key;/排序码 field otherdata;/其他数据成员 Element&operator=(Element&x)key=x.key;otherdata=x.otherdata;return this;5 bool operator=(Element&x)return key=x.key;/判*this与x相等 bool operator=(Element&x)return key=(Element&x)return key=x.key;/判*this大于或等于x bool operator (Element&x)return key x.key;/判*this大于x bool operator (Element&x)return key x.key;/判*this小于x;6template class dataList/数据表类定义private:Element*Vector;/存储排序元素的向量 int maxSize;/向量中最大元素个数 int currentSize;/当前元素个数public:datalist(int maxSz=DefaultSize):/构造函数 maxSize(maxSz),currentSize(0)Vector=new ElementmaxSize;int Length()return currentSize;/取表长度7 void Swap(Element&x,Element&y)Element temp=x;x=y;y=temp;Element&operator(int i)/取第i个元素 return Vectori;int Partition(const int low,const int high);/快速排序划分;8插入排序插入排序 (Insert Sorting)(Insert Sorting)基本方法是：每步将一个待排序的元素，按其排序基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当码大小，插入到前面已经排好序的一组元素的适当位置上位置上,直到元素全部插入为止。直到元素全部插入为止。直接插入排序直接插入排序折半插入排序折半插入排序希尔排序希尔排序9基本思想是基本思想是:当插入第当插入第i(i1)个元素时，前面的个元素时，前面的V0,V1,Vi-1已经排好序。这时，用已经排好序。这时，用Vi的排序码与的排序码与Vi-1,Vi-2,的排序码顺序进行比较，找到插入位置即的排序码顺序进行比较，找到插入位置即将将Vi插入，原来位置上的元素向后顺移。插入，原来位置上的元素向后顺移。10直接插入排序直接插入排序 (Insert Sort)(Insert Sort)11各各趟趟排排序序结结果果21212525494925*25*161608080 1 2 3 4 50 1 2 3 4 5 temp212125494925*25*161608082525i=10 1 2 3 4 5 temp212125254925*25*161608084949i=2120 1 2 3 4 5i=4i=5i=30 1 2 3 4 5 temp21212525494925*25*160808161621212525494925*1616080825*25*0 1 2 3 4 5 temp21212525494925*25*16160808080 1 2 3 4 5 temp1321212525494925*25*161608080 1 2 3 4 5i=4 时的排序过程时的排序过程完成1616160 1 2 3 4 5 temp21212525494925*25*080816164916160 1 2 3 4 5 temp21212525494925*25*08081616i=4j=3i=4j=2142516160 1 2 3 4 5 temp2121494925*25*08081616252525*161621212525494925*25*08080 1 2 3 4 51616i=4j=1i=4j=0i=4j=-10 1 2 3 4 5 temp212525494925*25*0808161621211616直接插入排序的算法直接插入排序的算法#include dataList.htemplate void InsertSort(dataList&L,int left,int right)/依次将元素L.Vectori按其排序码插入到有序表/L.Vectorleft,L.Vectori-1中,使得/L.Vectorleft到L.Vectori有序。Element temp;int i,j;for(i=left+1;i=right;i+)if(Li=left&temp Lj);Lj+1=temp;16设待排序元素个数为设待排序元素个数为currentSize=n,则该算法的主程序执则该算法的主程序执行行n-1趟。排序码趟。排序码比较次数比较次数和和元素移动次数元素移动次数与元素排序码与元素排序码的初始排列有关。的初始排列有关。最好情况下最好情况下，排序前元素已按排序码从小到大有序，每趟，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较只需与前面有序元素序列的最后一个元素比较1次，总的次，总的排序码比较次数为排序码比较次数为 n-1,元素移动次数为元素移动次数为0。最最坏坏情情况况下下,第第 i 趟趟时时第第 i 个个元元素素必必须须与与前前面面 i 个个元元素素都都做做排排序序码码比比较较,并并且且每每做做1次次比比较较就就要要做做1次次数数据据移移动动。则则总总排序码比较次数排序码比较次数KCN和和元素移动次数元素移动次数RMN分别为分别为平均情况下平均情况下，排序的时间复杂度为，排序的时间复杂度为 O(n2)。直接插入排序是一种直接插入排序是一种稳定稳定的排序方法。的排序方法。17折半插入排序折半插入排序 (Binary Insert Sort)(Binary Insert Sort)基本思想是基本思想是:设在顺序表中有一设在顺序表中有一 个元素序列个元素序列 V0,V1,Vn-1。其中。其中,V0,V1,Vi-1 是已经排好序是已经排好序的元素。在插入的元素。在插入Vi 时时,利用利用折半搜索法折半搜索法寻找寻找Vi 的插入位置。的插入位置。18 折半插入排序的折半插入排序的算法算法#include dataList.h template void BinaryInsertSort(dataList&L,const int left,const int right)/利用折半搜索,在L.Vectorleft到L.Vectori-1中/查找L.Vectori应插入的位置,再进行插入。Element temp;int i,low,high,middle,k;for(i=left+1;i=right;i+)temp=Li;low=left;high=i-1;while(low=high)/折半搜索寻找插入位置 middle=(low+high)/2;/取中点19 if(temp=low;k-)Lk+1=Lk;/成块移动,空出插入位置 Llow=temp;/插入 ;20 就就平均性能平均性能来说，来说，折半搜索比顺序搜索快折半搜索比顺序搜索快,所以折所以折半插入排序半插入排序比直接插入排序比直接插入排序平均性能平均性能要快。要快。它所需的它所需的排序码比较次数与待排序元素序列的初排序码比较次数与待排序元素序列的初始排列无关始排列无关，仅依赖于元素个数。在插入第，仅依赖于元素个数。在插入第 i 个个元素时，需要经过元素时，需要经过 log2i +1 次排序码比较次排序码比较,才能才能确定它应插入的位置。因此，将确定它应插入的位置。因此，将 n 个元素个元素(为推导为推导方便方便,设为设为 n=2k)用折半插入排序所进行的排序码用折半插入排序所进行的排序码比较次数为：比较次数为：折半插入排序是一种折半插入排序是一种稳定稳定的排序方法。的排序方法。21当当 n 较较大大时时，总总排排序序码码比比较较次次数数比比直直接接插插入入排排序序的最坏情况要好得多，但比其最好情况要差。的最坏情况要好得多，但比其最好情况要差。在在元元素素的的初初始始排排列列已已经经按按排排序序码码排排好好序序或或接接近近有有序序时时，直直接接插插入入排排序序比比折折半半插插入入排排序序执执行行的的排排序序码码比较次数比较次数要少。要少。折折半半插插入入排排序序的的元元素素移移动动次次数数与与直直接接插插入入排排序序都都依赖于元素的初始排列。依赖于元素的初始排列。22希尔排序希尔排序 (Shell Sort)(Shell Sort)希尔排序方法又称为希尔排序方法又称为缩小增量排序缩小增量排序。该方法的基。该方法的基本思想是本思想是:设待排序元素序列有设待排序元素序列有 n 个元素个元素,首先取一个整数首先取一个整数 gap n 作为间隔，将全部元素分为作为间隔，将全部元素分为 gap 个子序列，个子序列，所有距离为所有距离为 gap 的元素放在同一个子序列中，在的元素放在同一个子序列中，在每一个子序列中分别施行直接插入排序。然后缩每一个子序列中分别施行直接插入排序。然后缩小间隔小间隔 gap,例如取例如取 gap=gap/2，重复上述的子，重复上述的子序列划分和排序工作。直到最后取序列划分和排序工作。直到最后取 gap=1，将所，将所有元素放在同一个序列中排序为止。有元素放在同一个序列中排序为止。23 开始时开始时 gap 的值较大，子序列中的元素较少，排的值较大，子序列中的元素较少，排序速度较快序速度较快;随着排序进展，随着排序进展，gap 值逐渐变小值逐渐变小,子子序列中元素个数逐渐变多，由于前面工作的基础，序列中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然很快。大多数元素已基本有序，所以排序速度仍然很快。242521212525494925*25*161608080 1 2 3 4 5212125*25*i=108084949Gap=325251616492516084925*0821252125*162621212525494925*25*161608080 1 2 3 4 52121i=208084949Gap=225251616491625*082125494925*25*08081616212125*25*25252721212525494925*25*161608080 1 2 3 4 52121i=30808Gap=125251616494925*25*#include#include dataList.htemplate class template void ShellSort(dataList&L,const int left,const int right)int i,j,gap=right-left+1;/增量的初始值Element temp;do gap=gap/3+1;/求下一增量值 for(i=left+gap;i=right;i+)if(Li=left&temp 1);29gap的取法有多种。最初的取法有多种。最初 Shell 提出取提出取 gap=n/2，gap=gap/2，直到，直到gap=1。Knuth 提出取提出取 gap=gap/3 +1。还有人提出都取奇数为好，也有人提出各。还有人提出都取奇数为好，也有人提出各 gap 互质互质为好。为好。对特定的待排序元素序列，可以准确地估算排序码的比对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。较次数和元素移动次数。想想要要弄弄清清排排序序码码比比较较次次数数和和元元素素移移动动次次数数与与增增量量选选择择之之间间的的依依赖赖关关系系，并并给给出出完完整整的的数数学学分分析析，还还没没有有人人能能够够做到。做到。Knuth利利用用大大量量实实验验统统计计资资料料得得出出:当当 n 很很大大时时，排排序序码码平平均均比比较较次次数数和和元元素素平平均均移移动动次次数数大大约约在在 n1.25 到到 1.6n1.25 的的范范围围内内。这这是是在在利利用用直直接接插插入入排排序序作作为为子子序序列列排序方法的情况下得到的。排序方法的情况下得到的。希尔排序是一种希尔排序是一种不稳定不稳定的排序方法。的排序方法。30快速排序快速排序 (Quick Sort)(Quick Sort)基本思想是基本思想是:任取待排序元素序列中的某个元素任取待排序元素序列中的某个元素(例如取第例如取第一个元素一个元素)作为作为基准基准，按照该元素的排序码大小，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：将整个元素序列划分为左右两个子序列：u左侧左侧子序列中所有元素的排序码都子序列中所有元素的排序码都小于或等小于或等于于基准元素的排序码基准元素的排序码 u右侧右侧子序列中所有元素的排序码都子序列中所有元素的排序码都大于大于基准基准元素的排序码元素的排序码31基准元素则排在这两个子序列中间基准元素则排在这两个子序列中间(这也是该这也是该元素最终应安放的位置元素最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，然后分别对这两个子序列重复施行上述方法，直到所有的元素都排在相应位置上为止。直到所有的元素都排在相应位置上为止。3233QuickSort(List)if(List的长度大于的长度大于1)将序列将序列List划分为两个子序列划分为两个子序列 LeftList 和和 RightList;QuickSort(LeftList);QuickSort(RightList);将两个子序列将两个子序列 LeftList 和和 RightList 合并为一个序列合并为一个序列List;算法描述算法描述3421212525494925*25*161608080 1 2 3 4 5212125*25*k=1=1494925*25*16162525161608084949pivotpivot0808252549492121k=2=2k=3=308081616252525*25*2121pivotpivotpivotpivotpivotpivot3521212525494925*25*161608080 1 2 3 4 525*25*k=1=1划分划分划分划分252516162525161608084949pivotpospivotpos080825*25*49490808161625*25*25252121pivotpospivotpos2121比较比较比较比较4 4次次次次交换交换交换交换25,1625,16i ii ipivotpospivotpos2121比较比较比较比较1 1次次次次交换交换交换交换49,0849,084949low pivotposlow pivotpos交换交换交换交换21,0821,08快速排序的算法快速排序的算法#include dataList.htemplate void QuickSort(dataList&L,const int left,const int right)/对元素Vectorleft,.,Vectorright进行排序,/pivot=L.Vectorleft是基准元素,排序结束后它的/位置在pivotPos,把参加排序的序列分成两部分,/左边元素的排序码都小于或等于它,右边都大于它 if(left right)/元素序列长度大于1时 int pivotpos=L.Partition(left,right);/划分 QuickSort(L,left,pivotpos-1);QuickSort(L,pivotpos+1,right);36template int dataList:Partition(const int low,const int high)/数据表类的共有函数 int pivotpos=low;Element pivot=Vectorlow;/基准元素 for(int i=low+1;i=high;i+)/检测整个序列,进行划分 if(Vectori pivot)pivotpos+;if(pivotpos!=i)Swap(Vectorpivotpos,Vectori);Vectorlow=Vectorpivotpos;Vectorpivotpos=pivot;/将基准元素就位 return pivotpos;/返回基准元素位置;37 算法算法quicksort是一个是一个递归的算法递归的算法,其递归树其递归树如图所示。如图所示。从快速排序算法的递归树可知，快速排序从快速排序算法的递归树可知，快速排序的的趟数取决于递归树的高度趟数取决于递归树的高度。38212125*25*25*2525494908081616最最大大递递归归调调用用层层次次数数与与递递归归树树高高度度一一致致，理理想想情情况为况为 log2(n+1)。存储开销为。存储开销为 O(log2n)。平均计算时间为平均计算时间为 O(nlog2n)。在在最最坏坏的的情情况况，即即待待排排序序元元素素序序列列已已经经按按其其排排序序码码从从小小到到大大排排好好序序的的情情况况下下，其其递递归归树树成成为为单单支支树树，每每次次划划分分只只得得到到一一个个比比上上一一次次少少一一个个元元素素的的子子序序列列。必必须须经经过过n-1 趟趟才才能能把把所所有有元元素素定定位位，而而且且第第 i 趟趟需需要要经经过过 n-i 次次排排序序码码比比较较才才能能找找到到第第 i 个个元元素素的的安安放放位位置置，总总的的排排序序码码比比较较次次数数将将达到达到3940用第一个元素作为基准元素用第一个元素作为基准元素 快速排序退化的例子快速排序退化的例子0 1 2 3 4 5 pivot初始初始i=1i=2i=3i=4i=541n其排序速度退化到简单排序的水平其排序速度退化到简单排序的水平,比直接插比直接插入排序还慢。占用附加存储入排序还慢。占用附加存储(栈栈)将达到将达到O(n)。n快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。n对对于于 n 较较大大的的平平均均情情况况而而言言,快快速速排排序序是是“快快速速”的的,但但是是当当 n 很很小小时时,这这种种排排序序方方法法往往往往比其它简单排序方法还要慢。比其它简单排序方法还要慢。n因此，当因此，当n很小时可以用直接插入排序方法。很小时可以用直接插入排序方法。交换排序交换排序 (Exchange Sort)(Exchange Sort)基本思想是基本思想是两两比较两两比较待排序元素的排序码，如果发待排序元素的排序码，如果发生逆序生逆序(即排列顺序与排序后的次序正好相反即排列顺序与排序后的次序正好相反)，则，则交换之。直到所有元素都排好序为止。交换之。直到所有元素都排好序为止。基本方法是：设待排序元素序列中的元素个数为基本方法是：设待排序元素序列中的元素个数为 n。最多作最多作 n-1 趟，趟，i=1,2,n-1。在第。在第 i 趟中从后向趟中从后向前前，j=n-1,n-2,i，顺次两两，顺次两两比较比较Vj-1.key和和Vj.key。如果发生逆序，则交换如果发生逆序，则交换Vj-1和和Vj。又叫又叫冒泡排序冒泡排序.42起泡排序起泡排序 (Bubble Sort)(Bubble Sort)4321212525494925*25*161608080 1 2 3 4 5212125*25*i=1=14949252516162525161608084949ExchangExchang=1=1080825*25*49492121ExchangExchang=1=1i=2=2i=3=308081616ExchangExchang=1=125*25*25252121起泡排序的算法起泡排序的算法template void BubbleSort(dataList&L,const int left,const int right)int pass=left+1,exchange=1;while(pass=pass;j-)4425*25*0 1 2 3 4 5i=4=449491616ExchangExchang=0=0080825252121 if(Lj-1 Lj)/逆序 Swap(Lj-1,Lj);/交换 exchange=1;/标志置为1,有交换 pass+;算法分析算法分析第第i趟趟(1 i n)对待排序元素序列对待排序元素序列Vi-1,Vi,Vright进行排序，进行排序，结果将该序列中排序结果将该序列中排序码码最小最小的元素交换到序列的的元素交换到序列的第一个第一个位置位置(i-1)。45最多做最多做n-1趟起泡就能把所有元素排好序。趟起泡就能把所有元素排好序。在在元元素素的的初初始始排排列列已已经经按按排排序序码码从从小小到到大大排排好好序序时时，此此算算法法只只执执行行一一趟趟起起泡泡，做做n-1次次排排序序码码比比较较，不移动元素。这是不移动元素。这是最好的情形最好的情形。最最坏坏的的情情形形是是算算法法执执行行n-1趟趟起起泡泡,第第i趟趟(1 i n)做做n-i次次排排序序码码比比较较,执执行行n-i次次元元素素交交换换。在在最最坏坏情情形形下下总总的的排排序序码码比比较较次次数数KCN和和元元素素移移动动次次数数RMN为：为：起起泡泡排排序序需需要要一一个个附附加加元元素素以以实实现现元元素素值值的的对对换换。起泡排序是一个起泡排序是一个稳定稳定的排序方法。的排序方法。46选择排序选择排序基本思想是基本思想是:每一趟每一趟(例如第例如第 i 趟趟,i=0,1,n-2)在后面在后面 n-i 个待排序元素中选出排序码最小的元素，个待排序元素中选出排序码最小的元素，作为有序元素序列的第作为有序元素序列的第 i 个元素。待到第个元素。待到第 n-2 趟作趟作完，待排序元素只剩下完，待排序元素只剩下1个个,就不用再选了。就不用再选了。直接选择排序直接选择排序锦标赛排序锦标赛排序堆排序堆排序47直接选择排序直接选择排序 (Select Sort)(Select Sort)直接选择排序的基本步骤是：直接选择排序的基本步骤是：在一组元素在一组元素 ViVn-1 中选择具有最小排中选择具有最小排序码的元素；序码的元素；若它不是这组元素中的第一个元素若它不是这组元素中的第一个元素,则将它与则将它与这组元素中的第一个元素对调这组元素中的第一个元素对调;在这组元素中剔除这个具有最小排序码的元在这组元素中剔除这个具有最小排序码的元素。在剩下的元素素。在剩下的元素Vi+1 Vn-1中重复执中重复执行第行第、步步,直到剩余元素只有一个为止。直到剩余元素只有一个为止。484921212525494925*25*161608080 1 2 3 4 5212125*25*i=0=04949252516162525161608084949080825*25*49492121i=1=1i=2=20808161625*25*25252121初始初始初始初始最小者最小者 0808交换交换交换交换21,0821,08最小者最小者 1616交换交换交换交换25,1625,16最小者最小者 2121交换交换交换交换49,2149,2150494925*25*0 1 2 3 4 525*25*i=4252516160808494925*25*49492121结果结果i=308081625252121最小者最小者 25*无交换无交换最小者最小者 25无交换无交换2525212116160808各趟排序后的结果各趟排序后的结果直接选择排序的算法直接选择排序的算法#include dataList.htemplate void SelectSort(dataList&L,const int left,const int right)for(int i=left;i right;i+)int k=i;/在Li到Lright之间之间找最小排序码元素 for(int j=i+1;j=right;j+)if(Lj Lk)k=j;if(k!=i)Swap(Li,Lk);/交换 ;5152i=1时选择排序的过程时选择排序的过程0 1 2 3 4 51616080825*25*494921212525i k j 49 49 25 2549492525080825*25*16162121i k j 25*25*25 25534949080825*25*212116162525i k j 16 2516 2549492525080825*25*161621210 1 2 3 4 5i k j 21 21 16 16k 指示当前序列中最小者指示当前序列中最小者直接选择排序的排序码直接选择排序的排序码比较次数比较次数 KCN 与元素的初与元素的初始排列无关始排列无关。设整个待排序元素序列有。设整个待排序元素序列有 n 个元素，个元素，则第则第 i 趟选择具有最小排序码元素所需的比较次趟选择具有最小排序码元素所需的比较次数总是数总是 n-i-1 次。总的排序码比较次数为次。总的排序码比较次数为元素移动次数与元素序列初始排列有关元素移动次数与元素序列初始排列有关。当这组元素初始状态是按其排序码从小到大有序的时当这组元素初始状态是按其排序码从小到大有序的时候候,元素的移动次数达到最少元素的移动次数达到最少RMN=0，最坏情况是每一趟都要进行交换，总的元素移动次数最坏情况是每一趟都要进行交换，总的元素移动次数为为 RMN=3(n-1)。直接选择排序是一种直接选择排序是一种不稳定不稳定的排序方法。的排序方法。54锦标赛排序锦标赛排序 (Tournament Sort)(Tournament Sort)它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得 n 个元素的排序码，进行两两比较，得到个元素的排序码，进行两两比较，得到 n/2 个个比较的优胜者比较的优胜者(排序码小者排序码小者)，作为第一步比较的，作为第一步比较的结果保留下来。然后对这结果保留下来。然后对这 n/2 个元素再进行排个元素再进行排序码的两两比较序码的两两比较,如此重复，直到选出一个排如此重复，直到选出一个排序码最小的元素为止。序码最小的元素为止。由于每次两两比较的结果是把排序码小者作为优由于每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，所以称这种比赛树为胜者上升到双亲结点，所以称这种比赛树为胜者胜者树树。55在图例中，最下面是元素排列的初始状态，相当在图例中，最下面是元素排列的初始状态，相当于一棵完全二叉树的叶结点，它存放的是所有参于一棵完全二叉树的叶结点，它存放的是所有参加排序的元素的排序码。加排序的元素的排序码。5608Winner 21080825*2121254925*160863e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5570821080825*2121254925*160863e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5 形成初始胜者树（最小排序码上升到根）形成初始胜者树（最小排序码上升到根）排序码比较次数排序码比较次数:6 Winner(胜者胜者)e5=08VS.VS.VS.VS.VS.VS.581621161625*2121254925*1663e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e4=16VS.VS.输出冠军输出冠军e5=08 并调整胜者树后树的状态并调整胜者树后树的状态VS.5921216325*2121254925*63e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e0=21VS.VS.输出冠军输出冠军e4=16 并调整胜者树后树的状态并调整胜者树后树的状态VS.6025256325*25254925*63e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e1=25VS.VS.输出冠军输出冠军e0=21 并调整胜者树后树的状态并调整胜者树后树的状态VS.6125*25*6325*4925*63e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e3=25*VS.VS.输出冠军输出冠军e1=25 并调整胜者树后树的状态并调整胜者树后树的状态VS.62494963494963e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e2=49VS.VS.输出冠军输出冠军e3=25*并调整胜者树后树的状态并调整胜者树后树的状态VS.63636363e0 e1 e2 e3 e4 e5e6t0t1t2t3t4t5排序码比较次数排序码比较次数:3 Winner(胜者胜者)e6=63VS.VS.输出冠军输出冠军e2=49 并调整胜者树后树的状态并调整胜者树后树的状态VS.胜者树是完全二叉树胜者树是完全二叉树,其高度为其高度为 log2n ,其其中中 n 为待排序元素个数。为待排序元素个数。除第一次选择具有最小排序码的元素需要除第一次选择具有最小排序码的元素需要进行进行 n-1 次排序码比较外次排序码比较外,重构胜者树选择重构胜者树选择次小、再次小排序码所需的比较次数均为次小、再次小排序码所需的比较次数均为 O(log2n)。总排序码比较次数为。总排序码比较次数为O(nlog2n)。64这种排序方法虽然减少了许多排序时间这种排序方法虽然减少了许多排序时间,但但是使用了是使用了较多的附加存储较多的附加存储。如果有如果有 n 个元素，必须使用至少个元素，必须使用至少 2n-1 个结个结点来存放胜者树。点来存放胜者树。锦标赛排序是一个锦标赛排序是一个稳定稳定的排序方法。的排序方法。65堆排序堆排序 (Heap Sort)(Heap Sort)利用堆及其运算利用堆及其运算,可以很容易地实现选择排序的可以很容易地实现选择排序的思路。思路。堆排序分为两个步骤堆排序分为两个步骤u根据初始输入数据，利用堆的调整算法根据初始输入数据，利用堆的调整算法 siftDown()形成初始堆形成初始堆;u通过一系列的通过一系列的元素交换元素交换和和重新调整堆重新调整堆进行排序。进行排序。为了实现元素按排序码为了实现元素按排序码从小到大排序从小到大排序，要求建立，要求建立最大堆最大堆。6667建立初始的最大堆建立初始的最大堆212525*491608012345i212525*164908025431i21 25 49 25*16 08初始排序码集合初始排序码集合初始排序码集合初始排序码集合21 25 49 25*16 08i i=2 =2 时的局部调整时的局部调整时的局部调整时的局部调整68212525*491608012345i492525*16210802543121 25 49 25*16 0849 25 21 25*16 08i i=0 =0 时的局部调整时的局部调整时的局部调整时的局部调整形成最大堆形成最大堆形成最大堆形成最大堆i i=1 =1 时的局部调整时的局部调整时的局部调整时的局部调整最大堆的向下调整算法最大堆的向下调整算法template siftDown(dataList&L,const int start,const int m)/私有函数:从结点start开始到m自上向下比较,/如果子女的值大于双亲的值,则相互交换,将一/个集合局部调整为最大堆。int i=start;int j=2*i+1;/j是i的左子女Element temp=Li;/暂存子树根结点 while(j=m)/逐层比较 if(j m&Lj=Lj)break;/temp排序码大,不调整69 else /否则子女中的大者上移 Li=Lj;i=j;j=2*j+1;/i下降到子女位置 Li=temp;/temp放到合适位置;70最最 大大 堆堆 堆堆 顶顶 L.Vector0具具 有有 最最 大大 的的 排排 序序 码码，将将L.Vector0与与L.Vectorn-1对对调调,把把具具有有最最大大排排序序码码的的元元素素交交换换到到最最后后，再再对对前前面面的的n-1个个元元素素,使使用用堆堆的的调调整整算算法法siftDown(L,0,n-2)，重重新新建建立立最最大大堆堆，具具有有次次最大最大排序码的元素又上浮到排序码的元素又上浮到L.Vector0位置。位置。再再对对调调L.Vector0和和L.Vectorn-2，再再调调用用siftDown(L,0,n-3),对前面的对前面的n-2个元素重新调整，个元素重新调整，。如如此此反反复复执执行行，最最后后得得到到全全部部排排序序好好的的元元素素序序列列。这这个个算法即算法即堆排序算法堆排序算法，其细节在下面的程序中给出。，其细节在下面的程序中给出。71基于初始堆进行堆排序基于初始堆进行堆排序72492525*21