1、v概述概述v插入排序插入排序v交换排序交换排序v选择排序选择排序v归并排序归并排序v基数排序基数排序v各种内排方法比较各种内排方法比较第八章第八章 排序排序概概 述述n排序：排序：将一个数据元素的任意序列，重新将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排列成一个按关键字有序的序列。n数据表数据表(datalist):它是待排序数据对象的它是待排序数据对象的有限集合。有限集合。n主关键字主关键字(key):数据对象有多个属性域数据对象有多个属性域,即多个数据成员组成即多个数据成员组成,其中有一个属性域可用其中有一个属性域可用来区分对象来区分对象,作为排序依据，称为关键字。也作为
2、排序依据，称为关键字。也称为称为关键字关键字。n排序方法的稳定性排序方法的稳定性:如果在对象序列中有两如果在对象序列中有两 个对象个对象ri和和rj,它们的关键字它们的关键字 ki=kj,且在排序之前且在排序之前,对象对象ri排在排在rj前面。如果在前面。如果在排序之后排序之后,对象对象ri仍在对象仍在对象rj的前面的前面,则称则称这个排序方法是稳定的这个排序方法是稳定的,否则称这个排序方法否则称这个排序方法是不稳定的是不稳定的。n内排序与外排序内排序与外排序:内排序是指在排序期间内排序是指在排序期间数据对象全部存放在内存的排序；外排序是数据对象全部存放在内存的排序；外排序是指在排序期间全部对
3、象个数太多，不能同时指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。断在内、外存之间移动的排序。n排序的时间开销排序的时间开销:排序的时间开销是排序的时间开销是衡量算法好坏的最重要的标志。排序的衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。数与数据移动次数来衡量。ntypedef struct int key;datatype other;rectype;rectype Rn;内排序分类内排序分类依不同原则依不同原则插入排
4、序插入排序、交换排序交换排序、选择排序选择排序、归归并排序并排序、和基数排序等和基数排序等。依所须工作量依所须工作量简单排序简单排序-时间复杂度时间复杂度o(n2)先进排序方法先进排序方法-时间复杂度时间复杂度o(n logn)基数排序基数排序-时间复杂度时间复杂度o(d.n)插入排序插入排序(Insert Sorting)n基本思想基本思想 当插入第当插入第i(i 1)个对象时个对象时,前面的前面的R0,R1,Ri-1已经排好序。这时已经排好序。这时,用用Ri的关键字与的关键字与Ri-1,Ri-2,的关键字顺的关键字顺序进行比较序进行比较,找到插入位置即将找到插入位置即将Ri插入插入,原原来
5、位置上的对象向后顺移。来位置上的对象向后顺移。基本思想基本思想 每步将一个待排序的对象每步将一个待排序的对象,按其按其关键字大小关键字大小,插入到前面已经排好序的一组插入到前面已经排好序的一组对象的适当位置上对象的适当位置上,直到对象全部插入为止。直到对象全部插入为止。直接插入排序直接插入排序 (Insert Sort)直接插入直接插入排序过程排序过程0 1 2 3 4 5 temp i=1i=20 1 2 3 4 5 temp2549i=325*i=4i=5161608直接插入排序的算法直接插入排序的算法 InsertSort(rectype R,int n)int i,j;for(i=2;
6、i n;i+)R0=Ri;j=i 1;/从后向前顺序比较从后向前顺序比较 while(R0.key Rj.key)Rj+1=Rj-;Rj+1=R0;算法分析算法分析n设待排序对象个数为设待排序对象个数为 n,则该算法的主程序执行则该算法的主程序执行n-1趟。趟。n关键字比较次数和对象移动次数与对象关键字的关键字比较次数和对象移动次数与对象关键字的初始排列有关。初始排列有关。n最好情况下最好情况下,排序前对象已按关键字从小到大有排序前对象已按关键字从小到大有序序,每趟只需与前面有序对象序列的最后一个对每趟只需与前面有序对象序列的最后一个对象比较象比较1次次,移动移动2次对象次对象,总的关键字比较
7、次数为总的关键字比较次数为 n-1,对象移动次数为对象移动次数为 2(n-1)。n最坏情况下最坏情况下,第第 i 趟时第趟时第 i 个对象必须与前个对象必须与前面面 i 个对象都做关键字比较个对象都做关键字比较,并且每做并且每做1次次比较就要做比较就要做1次数据移动。则总关键字比较次数据移动。则总关键字比较次数次数KCN和对象移动次数和对象移动次数RMN分别为分别为n在平均情况下的关键字比较次数和对象移在平均情况下的关键字比较次数和对象移动次数约为动次数约为 n2/4。因此，直接插入排序的。因此，直接插入排序的时间复杂度为时间复杂度为 o(n2)。n直接插入排序是一种稳定的排序方法。直接插入排
8、序是一种稳定的排序方法。111122142221nininnniRMNnnniKCN/)()(,/)(22折半插入排序折半插入排序(Binary Insertsort)基本思想基本思想 设在顺序表中有一设在顺序表中有一 个对象序列个对象序列 R0,R1,Rn-1。其中。其中,R0,R1,Ri-1 是已经排好序的对象。在插入是已经排好序的对象。在插入Ri 时时,利用折利用折半搜索法寻找半搜索法寻找Ri 的插入位置。的插入位置。折半插入排序的算法折半插入排序的算法typedef int SortData;Roid BinInsSort(SortData R,int n)SortData temp;
9、int Left,Right;for(int i=1;i n;i+)Left=0;Right=i-1;temp=Ri;while(Left=Right)int mid=(Left+Right)/2;if(temp=Left;k-)Rk+1=Rk;/记录后移记录后移 RLeft=temp;/插入插入 折半插入排序折半插入排序0 1 2 3 4 5 temp i=1i=20 1 2 3 4 5 temp3i=354i=48i=516n折半搜索比顺序搜索查找快折半搜索比顺序搜索查找快,所以折半插入所以折半插入排序就平均性能来说比直接插入排序要快。排序就平均性能来说比直接插入排序要快。n它所需的关键字
10、比较次数与待排序对象序它所需的关键字比较次数与待排序对象序列的初始排列无关列的初始排列无关,仅依赖于对象个数。在仅依赖于对象个数。在插入第插入第 i 个对象时个对象时,需要经过需要经过 log2i +1 次关次关键字比较键字比较,才能确定它应插入的位置。因此才能确定它应插入的位置。因此,将将 n 个对象个对象(为推导方便为推导方便,设为设为 n=2k)用折半用折半插入排序所进行的关键字比较次数为：插入排序所进行的关键字比较次数为：1122log1logninni算法分析算法分析 n当当 n 较大时较大时,总关键字比较次数比直接插入总关键字比较次数比直接插入排序的最坏情况要好得多排序的最坏情况要
11、好得多,但比其最好情况但比其最好情况要差。要差。n在对象的初始排列已经按关键字排好序或在对象的初始排列已经按关键字排好序或接近有序时接近有序时,直接插入排序比折半插入排序直接插入排序比折半插入排序执行的关键字比较次数要少。折半插入排执行的关键字比较次数要少。折半插入排序的对象移动次数与直接插入排序相同序的对象移动次数与直接插入排序相同,依依赖于对象的初始排列。赖于对象的初始排列。n折半插入排序是一个稳定的排序方法。折半插入排序是一个稳定的排序方法。n折半插入排序的时间复杂度为折半插入排序的时间复杂度为o(n2)。希尔排序希尔排序(Shell Sort)n基本思想基本思想设待排序对象序列有设待排
12、序对象序列有 n 个对象个对象,首首先取一个整数先取一个整数 gap n 作为间隔作为间隔,将全部对将全部对象分为象分为 gap 个子序列个子序列,所有距离为所有距离为 gap 的对的对象放在同一个子序列中象放在同一个子序列中,在每一个子序列中在每一个子序列中分别施行直接插入排序。然后缩小间隔分别施行直接插入排序。然后缩小间隔 gap,例如取例如取 gap=gap/2，重复上述的子序列划，重复上述的子序列划分和排序工作。直到最后取分和排序工作。直到最后取 gap=1,将所将所有对象放在同一个序列中排序为止。有对象放在同一个序列中排序为止。n希尔排序方法又称为缩小增量排序。希尔排序方法又称为缩小
13、增量排序。i=3Gap=30 1 2 3 4 50 1 2 3 4 5i=2Gap=2i=1Gap=1希尔排序过程希尔排序过程 ShellSort(rectype R,int n)rectype temp;int gap=n/2;/gap是间隔是间隔 while(gap!=0)/循环循环,直到直到gap为零为零 for(int i=gap;i=gap;j=j-gap)if(temp Rj-gap)Rj=Rj-gap;else break;Rj=temp;gap=(int)(gap/2);希尔排序的算法希尔排序的算法n开始时开始时 gap 的值较大的值较大,子序列中的对象较少子序列中的对象较少,
14、排序速度排序速度较快较快;随着排序进展随着排序进展,gap 值逐渐变小值逐渐变小,子序列中对象子序列中对象个数逐渐变多个数逐渐变多,由于前面大多数对象已基本有序由于前面大多数对象已基本有序,所所以排序速度仍然很快。以排序速度仍然很快。nGap的取法有多种。的取法有多种。shell 提出取提出取 gap=n/2，gap=gap/2，直到直到gap=1。n对特定的待排序对象序列，可以准确地估算关键字的对特定的待排序对象序列，可以准确地估算关键字的比较次数和对象移动次数。比较次数和对象移动次数。n希尔排序所需的比较次数和移动次数约为希尔排序所需的比较次数和移动次数约为n 1.3当当n趋于无穷时可减少
15、到趋于无穷时可减少到n(log2 n)2交换排序交换排序(Exchange Sort)n基本方法基本方法设待排序对象序列中的对象个数为设待排序对象序列中的对象个数为n n。一般地，一般地，第第i i趟起泡排序从趟起泡排序从1 1到到n-i+1n-i+1依次比较相邻依次比较相邻两个记录地关键字，两个记录地关键字，如果发生逆序，则交换之，如果发生逆序，则交换之，其结果是这其结果是这n-i+1n-i+1个记录中，关键字最大的记录被个记录中，关键字最大的记录被交换到第交换到第n-i+1n-i+1的位置上，的位置上，最多作最多作n-1n-1趟。趟。基本思想基本思想是两两比较待排序对象的关键字是两两比较待
16、排序对象的关键字,如发生逆序如发生逆序(即排列顺序与排序后的次序正好即排列顺序与排序后的次序正好相反相反)，则交换之，则交换之,直到所有对象都排好序为止。直到所有对象都排好序为止。起泡排序起泡排序 (Bubble Sort)初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序起泡排序的过程起泡排序的过程初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序起泡排序的过程起泡排序的过程起泡排序的算法起泡排序的算法BubbleSort(rectype R,int n)int i,j,noswap;rectype temp;for(i=0;i=i;j-)if(Rj+1.key Rj.k
17、ey)/逆序逆序 temp=R j+1;/交换交换 R j+1=R j;R j =temp;noswap=0;/标志置为标志置为0,0,有交换有交换 if(noswap)break;思考题：如何实现双起泡思考题：如何实现双起泡 n第第i趟对待排序对象序列趟对待排序对象序列Ri-1,Ri,Rn-1进行排序进行排序,结果将该序列中关键字最小的结果将该序列中关键字最小的对象交换到序列的第一个位置对象交换到序列的第一个位置(i-1),其它对其它对象也都向排序的最终位置移动。象也都向排序的最终位置移动。n最多做最多做n-1趟起泡就能把所有对象排好序。趟起泡就能把所有对象排好序。n在对象的初始排列已经按关
18、键字从小到大在对象的初始排列已经按关键字从小到大排好序时排好序时,此算法只执行一趟起泡此算法只执行一趟起泡,做做n-1次次关键字比较关键字比较,不移动对象。这是最好的情形。不移动对象。这是最好的情形。n最坏的情形是算法执行最坏的情形是算法执行n-1趟起泡趟起泡,第第i趟趟(1 i n)做做 n-i 次关键字比较次关键字比较,执行执行 n-i 次对象次对象交换。这样在最坏情形下总的关键字比较次交换。这样在最坏情形下总的关键字比较次数数KCN和对象移动次数和对象移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(n起泡排序是一个稳定的排序方法。起泡排序是
19、一个稳定的排序方法。快速排序快速排序(Quick Sort)n基本思想基本思想是任取待排序对象序列中的某个是任取待排序对象序列中的某个对象对象(例如取第一个对象例如取第一个对象)作为基准作为基准,按照该按照该对象的关键字大小对象的关键字大小,将整个对象序列划分为将整个对象序列划分为左右两个子序列：左右两个子序列：u左侧子序列中所有对象的关键字都小于或左侧子序列中所有对象的关键字都小于或等于基准对象的关键字等于基准对象的关键字 u右侧子序列中所有对象的关键字都大于基右侧子序列中所有对象的关键字都大于基准对象的关键字准对象的关键字n基准对象则排在这两个子序列中间基准对象则排在这两个子序列中间(这也
20、是这也是该对象最终应安放的位置该对象最终应安放的位置)。n然后分别对这两个子序列重复施行上述方然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为法，直到所有的对象都排在相应位置上为止。止。n基准对象也称为基准对象也称为枢轴（或支点）记录。枢轴（或支点）记录。QuickSort(List)if(List的长度大于的长度大于1)将序列将序列List划分为两个子序列划分为两个子序列 LeftList 和和 Right List;QuickSort(LeftList);QuickSort(RightList);将两个子序列将两个子序列 LeftList 和和 RightList
21、合并为一个序列合并为一个序列List;快速排序算法描述快速排序算法描述快速排序的过程快速排序的过程初始关键字初始关键字prikey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji ji完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列快速排序的算法快速排序的算法 QuickSort(rectype R,int low,int high)/在序列在序列low high 中递归地进行快速排序中递归地进行快速排序 if(low high)int i=Partition(R,low,high);/划分划分 QuickSo
22、rt(R,low,i-1);/对左序列同样处理对左序列同样处理 QuickSort(R,i+1,high);/对右序列同样处理对右序列同样处理 int Partition(rectype R,int low,int high)R0=Rlow;/子表的第一个记录作基准对象子表的第一个记录作基准对象 tempkey=Rlow.key;/基准对象关键字基准对象关键字 While(lowhigh)While(low=tempkey)high-;Rlow=Rhigh;/小于基准的移到区间的左侧小于基准的移到区间的左侧 While(lowhigh&Rlow.key=tempkey)low+;Rhigh=R
23、low;/大于基准的移到区间的右侧大于基准的移到区间的右侧 Rlow=R0;return low;n算法算法quicksort是一个递归的算法是一个递归的算法,其递归树其递归树如图所示。如图所示。n算法算法partition利用序列第一个对象作为基准，利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法将整个序列划分为左右两个子序列。算法中执行了一个循环中执行了一个循环,只要是关键字小于基准只要是关键字小于基准对象关键字的对象都移到序列左侧对象关键字的对象都移到序列左侧,最后基最后基准对象安放到位准对象安放到位,函数返回其位置。函数返回其位置。算法分析算法分析n快速排序的趟数取决于
24、递归树的高度。快速排序的趟数取决于递归树的高度。n如果每次划分对一个对象定位后如果每次划分对一个对象定位后,该对象的该对象的左侧子序列与右侧子序列的长度相同左侧子序列与右侧子序列的长度相同,则下则下 一步将是对两个长度减半的子序列进行排序一步将是对两个长度减半的子序列进行排序,这是最理想的情况。这是最理想的情况。n在在 n个元素的序列中个元素的序列中,对一个对象定位所需对一个对象定位所需时间为时间为 O(n)。若设。若设 t(n)是对是对 n 个元素的序个元素的序列进行排序所需的时间列进行排序所需的时间,而且每次对一个对而且每次对一个对 象正确定位后象正确定位后,正好把序列划分为长度相等正好把
25、序列划分为长度相等的两个子序列的两个子序列,此时此时,总的计算时间为：总的计算时间为：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)n可以证明可以证明,函数函数quicksort的平均计算时间也的平均计算时间也是是O(nlog2n)。实验结果表明。实验结果表明:就平均计算时就平均计算时间而言间而言,快速排序是所有内排序方法中最好快速排序是所有内排序方法中最好的一个。的一个。n快速排序是递归的，需要有一个栈存放每层快速排
26、序是递归的，需要有一个栈存放每层递归调用时的指针和参数。递归调用时的指针和参数。n最大递归调用层次数与递归树的高度一致最大递归调用层次数与递归树的高度一致,理想情况为理想情况为 log2(n+1)。因此，要求存储。因此，要求存储开销为开销为 O(log2n)。n在最坏的情况在最坏的情况,即待排序对象序列已经按即待排序对象序列已经按其关键字从小到大排好序的情况下其关键字从小到大排好序的情况下,其递其递归树成为单支树归树成为单支树,每次划分只得到一个比每次划分只得到一个比上一次少一个对象的子序列。总的关键字上一次少一个对象的子序列。总的关键字比较次数将达比较次数将达n快速排序是一种不稳定的排序方法
27、。快速排序是一种不稳定的排序方法。2121211nnninni)()(基本思想基本思想 每一趟每一趟(例如第例如第 i 趟趟,i=0,1,n-2)在后面在后面 n-i 个待排序个待排序记录中选出关键字最小的记录记录中选出关键字最小的记录,作为作为有序序列中的第有序序列中的第 i 个记录。待到第个记录。待到第n-2 趟作完趟作完,待排序记录只剩下待排序记录只剩下1个个,就不用再选了。就不用再选了。选择排序选择排序n直接选择排序是一种简单的排序方法直接选择排序是一种简单的排序方法,它的它的基本步骤是：基本步骤是：在一组对象在一组对象 RiRn-1 中选择具有最中选择具有最小关键字的对象；小关键字的
28、对象；若它不是这组对象中的第一个对象若它不是这组对象中的第一个对象,则将则将它与这组对象中的第一个对象对调它与这组对象中的第一个对象对调;在这组对象中剔除这个具有最小关键字在这组对象中剔除这个具有最小关键字的对象。在剩下的对象的对象。在剩下的对象Ri+1Rn-1中中重复执行第重复执行第、步步,直到剩余对象只有直到剩余对象只有一个为止。一个为止。直接选择排序直接选择排序(Select Sort)0 1 2 3 4 5最小者最小者最小者最小者最小者最小者 直接选择排序的过程直接选择排序的过程最小者最小者0 1 2 3 4 5结果结果最小者最小者各趟排序后的结果各趟排序后的结果直接选择排序的算法直接
29、选择排序的算法SelectSort(rectype R,int n)int i,j,k;rectype temp;for(i=0;i n-1;i+)k=i;/选择具有最小关键字的对象选择具有最小关键字的对象 for(j=i+1;j n;j+)if(Rj.key Rk.key)k=j;/当前具最小关键字的对象当前具最小关键字的对象 if(k!=i)/对换到第对换到第 i 个位置个位置 temp=Ri;Ri=Rk;Rk=temp;n直接选择排序的关键字比较次数直接选择排序的关键字比较次数 KCN 与对象的初与对象的初始排列无关。设整个待排序对象序列有始排列无关。设整个待排序对象序列有 n 个对象个
30、对象,则第则第 i 趟选择具有最小关键字对象所需的比较次趟选择具有最小关键字对象所需的比较次数总是数总是 n-i-1 次。总的关键字比较次数为次。总的关键字比较次数为20211ninninKCN)()(n对象的移动次数与对象序列的初始排列有关。当对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键字从小到大有序这组对象的初始状态是按其关键字从小到大有序的时候的时候,对象的移动次数对象的移动次数RMN=0，达到最少。，达到最少。n最坏情况是每一趟都要进行交换，总的对象移动最坏情况是每一趟都要进行交换，总的对象移动次数为次数为 RMN=3(n-1)。n直接选择排序是一种不稳定的排
31、序方法。直接选择排序是一种不稳定的排序方法。堆排序堆排序堆堆(Heap)设有一个关键字集合，按完全设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同一组中。对它们从根开始，自顶向下，同一层自左向右从层自左向右从 0开始连续编号。若满足开始连续编号。若满足 Ki K2i&Ki K2i+1或或 Ki K2i&Ki K2i+1,则称该关键字集合构成一个堆。则称该关键字集合构成一个堆。前者成为小根堆，后者称为大根堆。前者成为小根堆，后者称为大根堆。完全二叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1完全二
32、叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1090987877878454565653131532323531717堆排序堆排序(Heap Sort)n利用堆及其运算利用堆及其运算,可以很容易地实现选择排可以很容易地实现选择排序的思路。序的思路。n堆排序分为两个步骤堆排序分为两个步骤u 根据初始输入数据，利用堆的调整算法根据初始输入数据，利用堆的调整算法 SIFT()形成初始堆形成初始堆;u 通过一系列的对象交换和重新调整堆进行通过一系列的对象交换和重新调整堆进行排序。排序。自下向上逐步调整为小根堆自下向上逐步调整为小根堆5353171778780923456587i0923
33、456587 i=4i=3i初始小根堆的建立过程初始小根堆的建立过程5353171778780923456587i0923456587i=2i53171778780923456587i0923456587i=1i5353171778780923456587i0923456587i53建成堆建成堆初始大根堆的建立过程初始大根堆的建立过程123456136542初始关键字集合初始关键字集合i=3 时的局部调整时的局部调整123456136542i=1 时的局部调整时的局部调整形成大根堆形成大根堆i=2 时的局部调整时的局部调整大根堆的筛选算法大根堆的筛选算法SIFT(rectype R,int i
34、,int m)int j=2*i;rectype temp=Ri;while(j=m)if(j m&Rj.key=Rj)break;else Ri=Rj;/大子女上移大子女上移 i=j;j=2*i;/向下继续调整向下继续调整 Ri=temp;/回放到合适位置回放到合适位置将表转换成堆将表转换成堆for(i=n/2;i=1;i-)SIFT(R,i,n);基于初始堆基于初始堆(大顶堆大顶堆)进行堆排序进行堆排序n最大堆堆顶最大堆堆顶R0具有最大的关键字具有最大的关键字,将将R0与与 Rn-1对调对调,把具有最大关键字的对象交换把具有最大关键字的对象交换到最后到最后,再对前面的再对前面的n-1个对象
35、个对象,使用堆的调使用堆的调整算法整算法SIFT(0,n-2),重新建立最大堆重新建立最大堆,具有具有次最大关键字的对象又上浮到次最大关键字的对象又上浮到R0位置。位置。n再对调再对调R0和和Rn-2,调用调用SIFT(0,n-3),对前对前n-2个对象重新调整，个对象重新调整，。n如此反复执行，最后得到全部排序好的对象如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法，序列。这个算法即堆排序算法，012345025431基于初始堆进行堆排序基于初始堆进行堆排序012345025431012345025431012345025431012345025431堆排序的算法堆排序的算法
36、HeapSort(rectype R )/对表对表R1到到Rn进行排序进行排序,使得表中使得表中对象关键字非递减有序。对象关键字非递减有序。int i;rectype temp;for(i=n/2;i=1;i-)SIFT(R,i,n);/初始堆初始堆 for(i=n;i=1;i-)temp=R1;R1=Ri;/交换交换 Ri=temp;SIFT(R,1,i-1);/重建最大堆重建最大堆 n若设堆中有若设堆中有 n 个结点个结点,且且 2k-1 n 2k,则对则对应的完全二叉树有应的完全二叉树有 k 层。在第层。在第 i 层上的结点层上的结点数数 2i (i=0,1,k-1)。在第一个形成初在第
37、一个形成初始堆的始堆的 for 循环中对每一个非叶结点调用了循环中对每一个非叶结点调用了 一次堆调整算法一次堆调整算法SIFT(),因此该循环所用的因此该循环所用的计算时间为：计算时间为：n其中其中,i 是层序号是层序号,2i 是第是第 i 层的最大结点数层的最大结点数,(k-i-1)是第是第 i 层结点能够移动的最大距离。层结点能够移动的最大距离。2022kiiik1 1堆排序的算法分析堆排序的算法分析n第二个第二个for循环中调用了循环中调用了n-1次次SIFT()算法算法,该该循环的计算时间为循环的计算时间为O(nlog2n)。因此。因此,堆排序堆排序的时间复杂性为的时间复杂性为O(nl
38、og2n)。n该算法的附加存储主要是在第二个该算法的附加存储主要是在第二个for循环中循环中用来执行对象交换时所用的一个临时对象。用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为因此，该算法的空间复杂性为O(1)。n堆排序是一个不稳定的排序方法。堆排序是一个不稳定的排序方法。njnjjikkjkjjjkkjjkkii4 411111111202222222122)(归并排序归并排序(Merge Sort)n归并归并将两个或两个以上的有序表合并成一个将两个或两个以上的有序表合并成一个新的有序表。新的有序表。n两路归并两路归并(2-way merging)原始序列原始序列R 中中两
39、个有序表两个有序表 Rl Rm和和Rm+1 Rn，它们可归并成一个有序表它们可归并成一个有序表,存于另一对象序存于另一对象序列列R1的的 l n 中。中。08 21 25 25*49 62 72 93 16 37 54 low mid mid+1 highR08 16 21 25 25*37 49 54 62 72 93 low highkR1n设变量设变量 i 和和 j 是表是表Rl m和和R m+1 n的当前检的当前检测指针。测指针。k 是存放指针。是存放指针。u当当 i 和和 j 都在两个表的表长内变化时都在两个表的表长内变化时,根据对应根据对应项的关键字的大小项的关键字的大小,依次把关
40、键字小的对象排放依次把关键字小的对象排放到新表到新表 k 所指位置中；所指位置中；u当当 i 与与 j 中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一 个表个表中的剩余部分照抄到新表中。中的剩余部分照抄到新表中。ijmerge(rectype R,rectype R1,int low,int mid,int high)int i=low,j=mid+1,k=low;while(i=mid&j=high)/两两比较将较小的并入两两比较将较小的并入 if(Ri=Rj)R1 k=Ri;i+;k+;else R1 k=Rj;j+;k+;while(i=mid)R1k=Ri;i+;k+;/
41、将将mid前剩余的并入前剩余的并入 while(j=high)R1k=Rj;j+;k+;/将将mid后剩余的并入后剩余的并入两路归并算法两路归并算法一趟归并排序的情形一趟归并排序的情形n设设R0到到Rn-1中中 n 个对象已经分为一些长个对象已经分为一些长度为度为 len 的归并项的归并项,将这些归并项两两归并将这些归并项两两归并,归并成长度为归并成长度为 2len 的归并项的归并项,结果放到结果放到R1 中。中。n如果如果n不是不是2len的整数倍的整数倍,则一趟归并到最后则一趟归并到最后,可能遇到两种情形：可能遇到两种情形：u 剩下一个长度为剩下一个长度为len的归并项和另一个长的归并项和
42、另一个长度不足度不足len的归并项的归并项,可用可用merge算法将它算法将它们归并成一个长度小于们归并成一个长度小于 2len 的归并项。的归并项。u只剩下一个归并项，其长度小于或等于只剩下一个归并项，其长度小于或等于 len,将它直接抄到将它直接抄到R1 中。中。迭代的归并排序算法迭代的归并排序算法n迭代的归并排序算法就是利用两路归并过程迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：进行排序的。其基本思想是：n假设初始对象序列有假设初始对象序列有 n 个对象，首先把它看个对象，首先把它看成是成是 n 个长度为个长度为 1 的有序子序列的有序子序列(归并项归并项)，先做两两
43、归并，得到先做两两归并，得到 n/2 个长度为个长度为 2 的归的归并项并项(如果如果 n 为奇数，则最后一个有序子序为奇数，则最后一个有序子序列的长度为列的长度为1)；再做两两归并，；再做两两归并，如此重，如此重复，最后得到一个长度为复，最后得到一个长度为 n 的有序序列。的有序序列。MergePass(rectype R,rectype R1,int len)int i=0;while(i+2*len-1=n-1)merge(R,R1,i,i+len-1,i+2*len-1);i+=2*len;/循环两两归并循环两两归并 if(i+len=n-1)merge(R,R1,i,i+len-1,
44、n-1);else for(int j=i;j=n-1;j+)R1 j=Rj;v归并排序的主算法归并排序的主算法 MergeSort(rectype R,int n)/按对象关键字非递减的顺序对表中对象排序按对象关键字非递减的顺序对表中对象排序 rectype R1n;int len=1;while(len n)MergePass(R,R1,len);len*=2;MergePass(R1,R,len);len*=2;n在迭代的归并排序算法中在迭代的归并排序算法中,函数函数MergePass()做一趟两路归并排序做一趟两路归并排序,要调用要调用merge()函数函数 n/(2*len)O(n/
45、len)次次,函数函数MergeSort()调调用用MergePass()正好正好 log2n 次次,而每次而每次merge()要执行比较要执行比较O(len)次次,所以算法总的时间复杂所以算法总的时间复杂度为度为O(nlog2n)。n归并排序占用附加存储较多归并排序占用附加存储较多,需要另外一个与需要另外一个与原待排序对象数组同样大小的辅助数组。这原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。是这个算法的缺点。n归并排序是一个稳定的排序方法。归并排序是一个稳定的排序方法。基数排序基数排序多关键字排序多关键字排序例例 对对52张扑克牌按以下次序排序：张扑克牌按以下次序排序：23A23
46、A23A23A两个关键字：花色两个关键字：花色（）面值面值（23A）并且并且“花色花色”地位高于地位高于“面值面值”多关键字排序方法多关键字排序方法最高位优先法（最高位优先法（MSD)：先对最高位关键字先对最高位关键字k1（如如花色）排序，将序列分成若干子序列，每个子序列花色）排序，将序列分成若干子序列，每个子序列有相同的有相同的k1值；然后让每个子序列对次关键字值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字重复，直至就每个子序列对最低位关键字kd排序；排序；最后将所有子序列依次连接在
47、一起成为一个有序序最后将所有子序列依次连接在一起成为一个有序序列列最低位优先法最低位优先法(LSD)：从最低位关键字：从最低位关键字kd起进行排起进行排序，然后再对高一位的关键字排序，序，然后再对高一位的关键字排序，依次重依次重复，直至对最高位关键字复，直至对最高位关键字k1排序后，便成为一个排序后，便成为一个有序序列有序序列 链式基数排序链式基数排序 基数排序：借助基数排序：借助“分配分配”和和“收集收集”对单逻辑关键字对单逻辑关键字进行排序的一种方法进行排序的一种方法 链式基数排序方法：用链表作存储结构的基数排序链式基数排序方法：用链表作存储结构的基数排序 设置设置10个队列，个队列，fi
48、和和ei分别为第分别为第i个队列的头指针个队列的头指针和尾指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至记录的指针值，将链表中记录分配至10个链队列个链队列中，每个队列记录的关键字的个位相同中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队记录的指针域，令其指向下一个非空队列的队头记录，重新将列的队头记录，重新将10个队列链成一个队列链成一个链表个链表 重复上述两步，进行第二趟、第三趟分重复上述两步，进行第二趟、第三趟分配和
49、收集，分别对十位、百位进行，最配和收集，分别对十位、百位进行，最后得到一个有序序列后得到一个有序序列例：例：初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一趟分配一趟分配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f
50、3f4f5f6f7f8f9二趟分配二趟分配008109278930063083184505278008109589269一趟收集：一趟收集：008063083109184269278505589930三趟收集：三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三趟分配三趟分配063083269278505589505008109930063269278083184589二趟收集：二趟收集：各种排序方法的比较各种排序方法的比较 比比较较次次数数 移移动动次次数数附附加加存存储储排排 序序 方方 法法最最好好最最差差最最好好最最差差稳
