北京师范大学数据结构教学资料 第9章——排序.ppt

140-1,概述插入排序交换排序选择排序归并排序基数排序,第九章 排序,140-2,概述,排序：将一组杂乱无章的数据按一定的规律顺次排列起来。数据表(dataList):它是待排序数据元素的有限集合。排序码(key):通常数据元素有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分元素,作为排序依据。该域即为排序码。每个数据表用哪个属性域作为排序码，要视具体的应用需要而定。,140-3,排序算法的稳定性:如果在元素序列中有两 个元素ri和rj,它们的排序码 ki=kj,且在排序之前,元素ri排在rj前面。如果在排序之后,元素ri仍在元素rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。内排序与外排序:内排序是指在排序期间数据元素全部存放在内存的排序；外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。,140-4,排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受元素排序码序列初始排列及元素个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储:评价算法好坏的另一标准。,140-5,待排序数据表的类定义,#include const int DefaultSize=100;template class dataList/数据表类定义private:T*Vector;/存储排序元素的向量 int maxSize;/向量中最大元素个数 int currentSize;/当前元素个数public:dataList(int maxSz=DefaultSize):/构造函数 maxSize(maxSz),currentSize(0)Vector=new TmaxSize;,140-6,int Length()return currentSize;/取表长度 void Swap(T,140-7,插入排序(Insert Sorting),基本方法是：每步将一个待排序的元素，按其排序码大小，插入到前面已经排好序的一组元素的适当位置上,直到元素全部插入为止。基本思想是:当插入第i(i1)个元素时，前面的V0,V1,Vi-1已经排好序。这时，用Vi的排序码与Vi-1,Vi-2,的排序码顺序进行比较，找到插入位置即将Vi插入，原来位置上的元素向后顺移。,直接插入排序(Insert Sort),140-8,各趟排序结果,i=1,i=2,140-9,0 1 2 3 4 5,i=4,i=5,i=3,140-10,i=4 时的排序过程,完成,i=4j=2,140-11,25,16,0 1 2 3 4 5 temp,21,49,25*,08,16,25,i=4j=1,i=4j=0,i=4j=-1,140-12,直接插入排序的算法,#include dataList.htemplate void InsertSort(dataList,140-13,do Lj+1=Lj;j-;while(j=left 算法分析设待排序元素个数为currentSize=n,则该算法的主程序执行n-1趟。排序码比较次数和元素移动次数与元素排序码的初始排列有关。,140-14,最好情况下，排序前元素已按排序码从小到大有序，每趟只需与前面有序元素序列的最后一个元素比较1次，总的排序码比较次数为 n-1,元素移动次数为0。最坏情况下,第 i 趟时第 i 个元素必须与前面 i 个元素都做排序码比较,并且每做1次比较就要做1次数据移动。则总排序码比较次数KCN和元素移动次数RMN分别为,140-15,平均情况下排序的时间复杂度为 o(n2)。直接插入排序是一种稳定的排序方法。基本思想是:设在顺序表中有一 个元素序列 V0,V1,Vn-1。其中,V0,V1,Vi-1 是已经排好序的元素。在插入Vi 时,利用折半搜索法寻找Vi 的插入位置。折半插入排序的算法#include dataList.h,折半插入排序(Binary Insertsort),140-16,template void BinaryInsertSort(dataList/取中点,140-17,if(temp=low;k-)Lk+1=Lk;/成块移动,空出插入位置 Llow=temp;/插入 算法分析折半搜索比顺序搜索快,所以折半插入排序就,140-18,平均性能来说比直接插入排序要快。它所需的排序码比较次数与待排序元素序列的初始排列无关，仅依赖于元素个数。在插入第 i 个元素时，需要经过 log2i+1 次排序码比较,才能确定它应插入的位置。因此，将 n 个元素(为推导方便,设为 n=2k)用折半插入排序所进行的排序码比较次数为：折半插入排序是一个稳定的排序方法。,140-19,当 n 较大时，总排序码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。在元素的初始排列已经按排序码排好序或接近有序时，直接插入排序比折半插入排序执行的排序码比较次数要少。折半插入排序的元素移动次数与直接插入排序相同，依赖于元素的初始排列。,140-20,希尔排序方法又称为缩小增量排序。该方法的基本思想是:设待排序元素序列有 n 个元素,首先取一个整数 gap n 作为间隔，将全部元素分为 gap 个子序列，所有距离为 gap 的元素放在同一个子序列中，在每一个子序列中分别,希尔排序(Shell Sort),140-21,施行直接插入排序。然后缩小间隔 gap,例如取 gap=gap/2，重复上述的子序列划分和排序工作。直到最后取 gap=1，将所有元素放在同一个序列中排序为止。开始时 gap 的值较大，子序列中的元素较少，排序速度较快;随着排序进展，gap 值逐渐变小,子序列中元素个数逐渐变多，由于前面工作的基础，大多数元素已基本有序，所以排序速度仍然很快。,140-22,140-23,21,25,49,25*,16,08,0 1 2 3 4 5,21,i=2,08,49,Gap=2,25,16,49,16,25*,08,21,25,49,25*,08,16,21,25*,25,140-24,21,25,49,25*,16,08,0 1 2 3 4 5,21,i=3,08,Gap=1,25,16,49,25*,#include dataList.htemplate,希尔排序的算法,140-25,void Shellsort(dataList,140-26,Lj+gap=temp;/将vectori回送 while(gap 1);算法分析Gap的取法有多种。最初 shell 提出取 gap=n/2，gap=gap/2，直到gap=1。knuth 提出取 gap=gap/3+1。还有人提出都取奇数为好，也有人提出各 gap 互质为好。对特定的待排序元素序列，可以准确地估算排序码的比较次数和元素移动次数。,140-27,想要弄清排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。Knuth利用大量实验统计资料得出:当 n 很大时，排序码平均比较次数和元素平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。希尔排序是一种不稳定的排序方法。,140-28,交换排序(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。,起泡排序(Bubble Sort),140-29,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i=1,49,25,16,25,16,08,49,Exchang=1,08,25*,49,21,Exchang=1,i=2,i=3,08,16,Exchang=1,25*,25,21,140-30,25*,0 1 2 3 4 5,i=4,49,16,Exchang=0,08,25,21,起泡排序的算法,template void BubbleSort(dataList j-),140-31,if(Lj-1 Lj)/逆序 Swap(Lj-1,Lj);/交换 exchange=1;/标志置为1,有交换 pass+;算法分析第i趟对待排序元素序列Vi-1,Vi,Vright进行排序，结果将该序列中排序码最小的元素交换到序列的第一个位置(i-1)。,140-32,最多做n-1趟起泡就能把所有元素排好序。在元素的初始排列已经按排序码从小到大排好序时，此算法只执行一趟起泡，做n-1次排序码比较，不移动元素。这是最好的情形。最坏的情形是算法执行n-1趟起泡,第i趟(1 in)做n-i次排序码比较,执行n-i次元素交换。在最坏情形下总的排序码比较次数KCN和元素移动次数RMN为：,140-33,起泡排序需要一个附加元素以实现元素值的对换。起泡排序是一个稳定的排序方法。基本思想是任取待排序元素序列中的某个元素(例如取第一个元素)作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：左侧子序列中所有元素的排序码都小于或等于基准元素的排序码,快速排序(Quick Sort),140-34,右侧子序列中所有元素的排序码都大于基准元素的排序码基准元素则排在这两个子序列中间(这也是该元素最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的元素都排在相应位置上为止。,140-35,QuickSort(List)if(List的长度大于1)将序列List划分为两个子序列 LeftList 和 RightList;QuickSort(LeftList);QuickSort(RightList);将两个子序列 LeftList 和 RightList 合并为一个序列List;,算法描述,140-36,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i=1,49,25*,16,25,16,08,49,pivot,08,25,49,21,i=2,i=3,08,16,25,25*,21,pivot,pivot,pivot,140-37,21,25,49,25*,16,08,0 1 2 3 4 5,25*,i=1划分,25,16,25,16,08,49,pivotpos,08,25*,49,08,16,25*,25,21,pivotpos,21,比较4次交换25,16,i,i,pivotpos,21,比较1次交换49,08,49,low pivotpos,交换21,08,140-38,快速排序的算法,#include dataList.htemplate void QuickSort(dataList,140-39,QuickSort(L,pivotpos+1,right);template int dataList:Partition(const int low,const int high)/数据表类的共有函数 int pivotpos=low;T pivot=Vectorlow;/基准元素for(int i=low+1;i=high;i+)/检测整个序列,进行划分,140-40,if(Vectori pivot)pivotpos+;if(pivotpos!=i)Swap(Vectorpivotpos,Vectori);/小于基准的交换到左侧去 Vectorlow=Vectorpivotpos;Vectorpivotpos=pivot;/将基准元素就位 return pivotpos;/返回基准元素位置算法分析,140-41,算法quicksort是一个递归的算法,其递归树如图所示。算法partition利用序列第一个元素作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环，只要是排序码小于基准元素排序码的元素都移到序列左侧，最后基准元素安,140-42,到位,函数返回其位置。从快速排序算法的递归树可知，快速排序的趟数取决于递归树的高度。如果每次划分对一个元素定位后，该元素的左侧子序列与右侧子序列的长度相同，则下 一步将是对两个长度减半的子序列进行排序，这是最理想的情况。在 n个元素的序列中，对一个元素定位所需时间为 O(n)。若设 t(n)是对 n 个元素的序列进行排序所需的时间，且每次对一个元素正确定位后，正好把序列分为长度相等的两个子序列，,140-43,此时,总的计算时间为：T(n)cn+2T(n/2)/c 是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)可以证明，函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言，快速排序是内排序方法中最好的一个。快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数。,140-44,最大递归调用层次数与递归树高度一致，理想情况为log2(n+1)。存储开销为 O(log2n)。在最坏的情况，即待排序元素序列已经按其排序码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个元素的子序列。必须经过n-1 趟才能把所有元素定位，而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个元素的安放位置，总的排序码比较次数将达到,140-45,用第一个元素作为基准元素,快速排序退化的例子,08 16 21 25 25*49,08,0 1 2 3 4 5 pivot,初始,16 21 25 25*49,08,16,21 25 25*49,21,08 16,25,25 25*49,08 16 21,25*49,25*,08 16 21 25,49,08 16 21 25 25*,i=1,i=2,i=3,i=4,i=5,140-46,用居中排序码元素作为基准元素,08 16 21 25 25*49,0 1 2 3 4 5 pivot,21,初始,08 16,21,25 25*49,08,25*,08,16,21,25,25*,49,i=1,i=2,其排序速度退化到简单排序的水平,比直接插入排序还慢。占用附加存储(栈)将达到O(n)。改进办法:取每个待排序元素序列的第一个元素、最后一个元素和位置接近正中的 3 个元素，取其排序码居中者作为基准元素。,140-47,快速排序是一种不稳定的排序方法。对于 n 较大的平均情况而言,快速排序是“快速”的,但是当 n 很小时,这种排序方法往往比其它简单排序方法还要慢。因此，当n很小时可以用直接插入排序方法。,140-48,选择排序,基本思想是:每一趟(例如第 i 趟,i=0,1,n-2)在后面 n-i 个待排序元素中选出排序码最小的元素，作为有序元素序列的第 i 个元素。待到第 n-2 趟作完，待排序元素只剩下1个,就不用再选了。,140-49,直接选择排序(Select Sort),直接选择排序的基本步骤是：在一组元素 ViVn-1 中选择具有最小排序码的元素；若它不是这组元素中的第一个元素,则将它与这组元素中的第一个元素对调;在这组元素中剔除这个具有最小排序码的元素。在剩下的元素Vi+1 Vn-1中重复执行第、步,直到剩余元素只有一个为止。,140-50,21,25,49,25*,16,08,0 1 2 3 4 5,21,25*,i=0,49,25,16,25,16,08,49,08,25*,49,21,i=1,i=2,08,16,25*,25,21,初始,最小者 08交换21,08,最小者 16交换25,16,最小者 21交换49,21,140-51,49,25*,0 1 2 3 4 5,25*,i=4,25,16,08,49,25*,49,21,结果,i=3,08,16,25,21,最小者 25*无交换,最小者 25无交换,25,21,16,08,各趟排序后的结果,140-52,直接选择排序的算法,#include dataList.htemplate void SelectSort(dataList/交换,140-53,i=1时选择排序的过程,140-54,k 指示当前序列中最小者,140-55,直接选择排序的排序码比较次数 KCN 与元素的初始排列无关。设整个待排序元素序列有 n 个元素，则第 i 趟选择具有最小排序码元素所需的比较次数总是 n-i-1 次。总的排序码比较次数为元素移动次数与元素序列初始排列有关。当这组元素初始状态是按其排序码从小到大有序的时候,元素的移动次数达到最少RMN=0，。,140-56,最坏情况是每一趟都要进行交换，总的元素移动次数为 RMN=3(n-1)。直接选择排序是一种不稳定的排序方法。若待排序的数据元素顺序存放于单链表中，每一趟排序先在链表中选择关键码值最大的元素，将它从链中摘下，再插入一个初始为空的新链表的首部。当所有元素都从原链表中摘下并插入到新链表中，则新链表中元素已经有序链接起来。,链表直接选择排序,140-57,链表直接选择排序的算法,#include staticList.htemplate int selectSort(staticLinkedList/s指示当前最大元素 while(p!=0),140-58,if(Lp.data Ls.data)s=p;r=q;/记忆当前找到的排序码最大结点 q=p;p=Lp.link;if(s=f)f=Lf.link;/结点s从链中摘下 else Lr.link=Ls.link;Ls.link=L0.link;L0.link=s;/结点s插入到结果链表的前端,140-59,它的思想与体育比赛时的淘汰赛类似。首先取得 n 个元素的排序码，进行两两比较，得到 n/2 个比较的优胜者(排序码小者)，作为第一步比较的结果保留下来。然后对这 n/2 个元素再进行排序码的两两比较,如此重复，直到选出一个排序码最小的元素为止。由于每次两两比较的结果是把排序码小者作为优胜者上升到双亲结点，所以称这种比赛树为胜者树。,锦标赛排序(Tournament Tree Sort),140-60,在图例中，最下面是元素排列的初始状态，相当于一棵完全二叉树的叶结点，它存放的是所有参加排序的元素的排序码。,140-61,在胜者树中，位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。胜者树最顶层是树的根，表示最后选择出来的具有最小排序码的元素。外结点的个数为n时，内结点的个数为n-1。定义根到最远层内结点的路径长度s为从根到该内结点路径上的分支条数，则有s=log2(n-1)这样，最远层最左端的内结点的编号为2s，最远层的内结点个数为n-2s，而最远层外结点个数等于最远层内结点个数的2倍。,140-62,上例中，外结点数n=7，s=log26=2，最远层最左端的内结点编号为 2s=4，该层的内结点数共有m=n-2s=7-4=3，最远层的外结点数为lowExt=2m=6，次远层最左端的外部结点编号为lowExt+1=7。,140-63,若已知某外结点的编号为 i，则其双亲结点（内结点）的编号为 k，则：其中offset=2s+1-1，指最远层最左端外结点之前结点（包括所有内结点和次远层外结点）个数。i lowExt 即最远层外结点，i lowExt 即次远层外结点。,140-64,胜者树的类定义,template class WinnerTree private:int maxSize;/允许的最大选手数int n;/当前大小(外部结点数)int lowExt;/最远层外部结点数int offset;/偏移(加1即为第1个外结点)int*t;/胜者树数组T*e;/选手数组void Play(int k,int lc,int rc,int(*Winner)(int a,int b);,140-65,public:const T maxValue=;/序列中不可能的大值 WinnerTree(int TreeSize=20)/构造函数:maxSize(TreeSize),n(0)t=new intTreeSize;WinnerTree()delete t;/析构函数 bool Initial(T a,int size,int(*Winner)(int a,int b);bool rePlay(int i,int(*Winner)(int a,int b);/重构 void Update()et1=maxValue;/修改 int Winner()const return(n!=0)?t1:0;/取最终胜者,140-66,int Winner(int i)const return(i bool WinnerTree:Initial(T a,int size,int(*Winner)(int a,int b)/a是胜者树选手数组,size是选手数，函数Winner/用于得到两选手a,b比赛的胜者,初始化胜者树的算法,140-67,if(size maxSize|size 2)return false;n=size;e=a;int i,s;for(s=1;2*s=n-1;s+=s);/计算s=2log2(n-1)lowExt=2*(n-s);offset=2*s-1;for(i=2;i=lowExt;i+=2)/最远层外结点比赛 Play(offset+i)/2,i-1,i,Winner);/选手i-1和i比赛,胜者升入双亲(offset+i)/2 if(n%2=0)i=lowExt+2；/次远层外结点比赛 else/当n为奇数时,内结点要与外结点比赛 Play(n/2,tn-1,lowExt+1,Winner);,140-68,i=lowExt+3;/i再进到次远层其他外结点 for(;i=n;i+=2)/其他次远层外结点比赛 Play(i-lowExt+n-1)/2,i-1,i,Winner);return true;通过初始化操作，形成胜者树，最后胜者进入树的根结点。此操作调用n/2次Play算法，而Play算法逐层向上比较，次数不超过 log2n。,140-69,template void WinnerTree:Play(int k,int lc,int rc,int(*Winner)(int a,int b)/通过比赛对树初始化。在tk处开始比赛,lc和rc是/tk的左子女和右子女。tk=Winner(lc,rc);/在elc和erc间选出胜者 while(k 1/到双亲结点,140-70,重新比赛,重构胜者树的算法,一旦选手 i 最后胜者，就将其值改为“”，使得以后不再参选。此时，需要重新进行外结点ei到根t1路径上的比赛。重新执行从胜者对应的外结点到根的路径上的比赛次数等于ei到根t1的路径上的分支数。template bool WinnerTree:rePlay(int i,int(*Winner(int a,int b)/针对元素i值的改变，重新组织胜者树。,140-71,if(i n)return false;int k,lc,rc;/比赛结点及其左右子女 if(i=lowExt)/最远层外结点 k=(offset+i)/2;/计算 i 的双亲 lc=2*k-offset;rc=lc+1;/计算左右子女 else/次远层外结点 k=(i-lowExt+n-1)/2;if(2*k=n-1)lc=t2*k;rc=i;else lc=2*k-n+1+lowExt;rc=lc+1;,140-72,tk=Winner(lc,rc);k/=2;for(;k=1;k/=2)/逐层向上比赛直到根 tk=Winner(t2*k,t2*k+1);template void TournamentSort(T a,const int left,const int right)/建立树的顺序存储数组tree,将数组a 中的元素复,锦标赛排序的算法,140-73,/复制到胜者树中,对它们进行排序,并把结果返送/回数组中,left 和right是排序元素的起点和终点。size=right-left+1;/待排序元素个数WinnerTree WT(size);/胜者树对象T datasize+1;/存储输入数据int i;for(i=1;i datai;WT.Initial(data,size,Winner);/构造初始胜者树for(i=0;i size;i+)ai=WT.Winner();/输出胜者 WT.Update();/修改胜者的值,140-74,WT.rePlay(t1,Winner);/重构胜者树 if(WT.Winner()=maxValue)break;胜者树是完全二叉树,其高度为 log2n,其中 n 为待排序元素个数。除第一次选择具有最小排序码的元素需要进行 n-1 次排序码比较外,重构胜者树选择次小、再次小排序码所需的比较次数均为 O(log2n)。总排序码比较次数为O(nlog2n)。,140-75,形成初始胜者树（最小排序码上升到根）,排序码比较次数:6,Winner(胜者),e6=08,VS.,VS.,VS.,VS.,VS.,VS.,140-76,排序码比较次数:3,Winner(胜者),e5=16,VS.,VS.,输出冠军e6=08 并调整胜者树后树的状态,VS.,140-77,排序码比较次数:3,Winner(胜者),e1=21,VS.,VS.,输出冠军e5=16 并调整胜者树后树的状态,VS.,140-78,排序码比较次数:3,Winner(胜者),e2=25,VS.,VS.,输出冠军e1=21 并调整胜者树后树的状态,VS.,140-79,排序码比较次数:3,Winner(胜者),e4=25*,VS.,VS.,输出冠军e2=25 并调整胜者树后树的状态,VS.,140-80,排序码比较次数:3,Winner(胜者),e3=49,VS.,VS.,输出冠军e4=25*并调整胜者树后树的状态,VS.,140-81,排序码比较次数:3,Winner(胜者),e7=63,VS.,VS.,输出冠军e3=49 并调整胜者树后树的状态,VS.,140-82,这种排序方法虽然减少了许多排序时间,但是使用了较多的附加存储。如果有 n 个元素，必须使用至少 2n-1 个结点来存放胜者树。锦标赛排序是一个稳定的排序方法。,140-83,堆排序(Heap Sort),利用堆及其运算,可以很容易地实现选择排序的思路。堆排序分为两个步骤根据初始输入数据，利用堆的调整算法 siftDown()形成初始堆;通过一系列的元素交换和重新调整堆进行排序。为了实现元素按排序码从小到大排序，要求建立最大堆。,140-84,建立初始的最大堆,140-85,21,25,25*,49,16,08,0,1,2,3,4,5,i,49,25,25*,16,21,08,0,2,5,4,3,1,21 25 49 25*16 08,49 25 21 25*16 08,i=0 时的局部调整形成最大堆,i=1 时的局部调整,140-86,最大堆的向下调整算法,template siftDown(dataList/temp排序码大不调整,140-87,else/否则子女中的大者上移 Li=Lj;i=j;j=2*j+1;/i下降到子女位置 Li=temp;/temp放到合适位置;最大堆堆顶L.Vector0具有最大的排序码，将L.Vector0与L.Vectorn-1对调,把具有最大,基于初始堆进行堆排序,140-88,排序码的元素交换到最后，再对前面的n-1个元素,使用堆的调整算法siftDown(L,0,n-2)，重新建立最大堆，具有次最大排序码的元素又上浮到L.Vector0位置。再对调L.Vector0和L.Vectorn-2，再调用siftDown(L,0,n-3),对前面的n-2个元素重新调整，。如此反复执行，最后得到全部排序好的元素序列。这个算法即堆排序算法，其细节在下面的程序中给出。,140-89,49,25,25*,21,16,08,0,1,2,3,4,5,08,25,25*,16,21,49,0,2,5,4,3,1,49 25 21 25*16 08,08 25 21 25*16 49,交换 0 号与 5 号元素,5 号元素就位,初始最大堆,140-90,25,25*,08,21,16,49,0,1,2,3,4,5,16,25*,08,25,21,49,0,2,5,4,3,1,25 25*21 08 16 49,16 25*21 08 25 49,交换 0 号与 4 号元素,4 号元素就位,从 0 号到 4 号 重新调整为最大堆,140-91,25*,16,08,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,25*16 21 08 25 49,08 16 21 25*25 49,交换 0 号与 3 号元素,3 号元素就位,从 0 号到 3 号 重新调整为最大堆,140-92,21,16,25*,08,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,21 16 08 25*25 49,08 16 21 25*25 49,交换 0 号与 2 号元素,2 号元素就位,从 0 号到 2 号 重新调整为最大堆,140-93,16,08,25*,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,16 08 21 25*25 49,08 16 21 25*25 49,交换 0 号与 1 号元素,1 号元素就位,从 0 号到 1 号 重新调整为最大堆,140-94,堆排序的算法,template void HeapSort(dataList,140-95,算法分析设堆中有 n 个结点,且 2k-1 n 2k,则对应的完全二叉树有 k 层。在第 i 层上的结点数2i-1(i=1,k)。在第一个形成初始堆的 for 循环中对每一个非叶结点调用了一次堆调整算法siftDown(),该循环所用的计算时间为：其中,i 是层次编号,2i-1 是第 i 层的最大结点数,(k-i)是第 i 层结点能够移动的最大距离。,140-96,第二个 for 循环中调用了n-1次siftDown()算法,该循环的计算时间为O(nlog2n)。因此,堆排序的时间复杂性为O(nlog2n)。该算法的附加存储主要是在第二个 for 循环中用来执行元素交换时所用的一个临时元素。因此，该算法的空间复杂性为O(1)。堆排序是一个不稳定的排序方法。,140-97,归并排序(Merge Sort),归并，是将两个或两个以上的有序表合并成一个新的有序表。元素序列L1中有两个有序表Vectorleft.mid和Vectormid+1.right。它们可归并成一个有序表,存于另一元素序列L2的Vectorleft.right 中。这种方法称为两路归并(2-way merging)。变量 i 和 j 分别是表Vectorleft.mid和Vector mid+1.right的检测指针。k 是存放指针。,140-98,当 i 和 j 都在两个表的表长内变化时,根据对应项的排序码的大小,依次把排序码小的元素排放到新表 k 所指位置中；当 i 与 j 中有一个已经超出表长时，将另一 个表中的剩余部分照抄到新表中。,140-99,迭代的归并排序算法,迭代的归并排序算法就是利用两路归并过程进行排序。其基本思想是：设初始元素序列有 n 个元素，首先把它看成是 n 个长度为 1 的有序子序列（归并项），做两两归并，得到 n/2 个长度为 2 的归并项（最后一个归并项的长度为1）；再做两两归并，得到 n/4 个长度为 4 的归并项（最后一个归并项长度可以短些），如此重复，最后得到一个长度为 n 的有序序列。,140-100,迭代的归并排序算法,21,25,25*,25*,93,62,72,08,37,16,54,49,21,25,49,62,93,08,72,16,37,54,21,25,25*,49,08,62,72,93,16,37,54,08,08,21,16,25,21,25*,25,49,25*,62,37,72,49,93,54,16,37,54,62,72,93,len=1,len=2,len=4,len=8,len=16,140-101,两路归并算法,#include dataList.htemplate void merge(dataList/s1,s2是检测指针,t是存放指针,140-102,while(i=mid/若第二个表未检测完,复制,140-103,一趟归并排序的算法,设L1.Vector0.n-1中 n 个记录已经分为一些长度为 len 的归并项，将这些归并项两两归并成长度为2len的归并项,结果放到L2 中。如果n不是2len的整数倍，则一趟归并到最后，可能遇到两种情形：剩下一个长度为len的归并项和另一个长度不足len的归并项,可用merge算法将它们归并成一个长度小于 2len 的归并项。只剩下一个归并项，其长度小于或等于 len,将它直接复制到结果表中。,140-104,template void MergePass(dataList,140-105,(两路)归并排序的主算法,template void MergeSort(dataList,140-106,在迭代的归并排序算法中,函数MergePass()做一趟两路归并排序,要调用merge()函数 n/(2*len)O(n/len)次,函数MergeSort()调用MergePass()正好log2n次，而每次merge()要执行比较O(len)次,所以算法总的时间复杂度为O(nlog2n)。归并排序占用附加存储较多,需要另外一个与原待排序元素数组同样大小的辅助数组。这是这个算法的缺点。归并排序是一个稳定的排序方法。,140-107,递归的链表归并排序,与快速排序类似，归并排序也可以利用划分为子序列的方法递归实现。算法的思路是：首先把整个待排序序列划分为两个长度大致相等的部分，分别称之为左子表和右子表。对这些子表分别递归地进行排序，然后再把排好序的两个子表进行归并。图示：待排序元素序列的排序码为 21,25,49,25*,16,08，先是进行子表划分，待到子表中只有一个元素时递归到底。再实施归并，逐步退出递归调用的过程。,140-108,21 25 49 25*16 08,21 25 49,25*16 08,21,25,49,25 49,21,25*,16 08,25*,16,08,21 25 49 25*16 08,16 08,25*,25 49,21,递归,21,25*,16,08,49,25,25*16 08,21 25 49,回推,140-109,静态链表的两路归并算法,#include staticList.htemplate int ListMerge(staticLinkedList,140-110,else Lk.link=j;k=j;j=Lj.link;if(i=0)Lk.link=j;/i链检测完,j链接上 else Lk.link=i;/j链检测完,i链接上 return L0.link;/返回结果链头指针template int rMergeSort(staticLinkedlist&L,const int left,const int right)/对链表L.Vectorleft.right进行排序。各个