《第八章+内排序【2】.ppt》由会员分享，可在线阅读，更多相关《第八章+内排序【2】.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章第八章 内排序内排序宋国杰宋国杰北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法28.3 Shell排序排序直接插入排序的两个性质直接插入排序的两个性质在最好情况（序列本身已是有序的）下时间代价为在最好情况（序列本身已是有序的）下时间代价为(n)对于短序列，直接插入排序比较有效对于短序列，直接插入排序比较有效Shell排序有效地利用了这两个性质排序有效地利用了这两个性质Shell排序排序又称为又称为“缩小增量排序缩小增量排序”，1959年
2、由年由D.L.Shell提出提出北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法基本思想基本思想先将待排序序列转化为若干小序列（距离相同先将待排序序列转化为若干小序列（距离相同的间隔的间隔gap），在这些小序列内进行插入排序），在这些小序列内进行插入排序逐渐扩大小序列的规模，而减少小序列个数逐渐扩大小序列的规模，而减少小序列个数(以以delta缩小间隔缩小间隔)，使得待排序序列逐渐处于更有，使得待排序序列逐渐处于更有序的状态序的状态最后对整个序列进行扫尾直接插入排序，从而最后对整个序列进行扫
3、尾直接插入排序，从而完成排序完成排序北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法形式化描述形式化描述1)选定一个增量序列选定一个增量序列 nd1d2dt=1，2)其中其中 n 文件长度文件长度；3)di(1it)增量增量(正整数正整数)；4)t 增量个数、排序趟数。增量个数、排序趟数。2)将文件按将文件按 d1 分组，彼此相距分组，彼此相距 d1 的记录划为一组，的记录划为一组，在各组内采用直接插入法进行排序。在各组内采用直接插入法进行排序。3)分别按分别按 d2,dt 重复上述分组和排
4、序工作。重复上述分组和排序工作。Shell 最初提出的增量序列是最初提出的增量序列是 d1=n/2，di+1=di/2北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法5Shell排序过程排序过程北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法6“delta=2delta=2”的的ShellShell排序排序template Void ShellSorter:Sort(Record Arra
5、y,int n)/Shell排序，排序，Array为待排序数组，为待排序数组，/n为数组长度为数组长度/增量增量delta每次除以每次除以2递减递减for(int delta=n/2;delta0;delta/=2)/分别对分别对delta个子序列排序个子序列排序 for(int j=0;jdelta;j+)ModifiedInsertSort(&Arrayj,n-j,delta);北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法7template void ShellSorter:Modi
6、fiedInsertSort(Record Array,int n,int delta)/参数参数delta表示当前的增量表示当前的增量/对子序列中第对子序列中第i个记录排序个记录排序for(int i=delta;i=delta;j-=delta)if(Arrayj Arrayj-delta)swap(Array,j,j-delta);else break;北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法分析分析增量序列可有各种取法：任何正整数的递减序列增量序列可有各种取法：任何正整数的递
7、减序列d1,d2,dt,只要只要 d1n,dt=1,原则上都可作为希尔排序的原则上都可作为希尔排序的增量序列增量序列Hibbard增量序列增量序列2k-1，2k-1-1，7，3，1，Hibbard增量序列的增量序列的Shell排序的效率可以达到排序的效率可以达到(n3/2)选取其他增量序列还可以更进一步减少时间代价选取其他增量序列还可以更进一步减少时间代价希尔排序是一种希尔排序是一种不稳定的排序方法不稳定的排序方法8北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法98.4 8.4 基于分治法
8、的排序基于分治法的排序“分而治之分而治之”的思想的思想将原始序列分为若干个子部分将原始序列分为若干个子部分,然后分别进行然后分别进行排序排序该思想是解决问题的重要方法之一该思想是解决问题的重要方法之一两种算法两种算法快速排序（快速排序（quick sorting）归并排序（归并排序（merge sorting）北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法 快速排序C.A.R.Hoare(霍尔霍尔)1962.北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信
9、息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法11快速排序快速排序基本思想基本思想首先，从待排序序列首先，从待排序序列S中任意选择一个记录中任意选择一个记录k作为轴值作为轴值然后，将剩余的序列划分为两个子序列然后，将剩余的序列划分为两个子序列L和和R，使得，使得L中所中所有记录都小于或等于轴值，有记录都小于或等于轴值，R中记录都大于轴值中记录都大于轴值将将L中所有记录都放在中所有记录都放在k左边左边R中的记录都放在中的记录都放在k的右边的右边k正好处于正确的位置正好处于正确的位置对子序列对子序列L和和R递归进行快速排序，直到仅含递归进行快速排序，直到仅含1或或0个元素个
10、元素北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法12关键问题关键问题轴值选择轴值选择尽可能使尽可能使L，R长度相等长度相等选择策略选择策略选择最左边记录选择最左边记录随机选择随机选择选择中间位置值选择中间位置值序列分割序列分割整个快速排序的关键整个快速排序的关键分割后使得分割后使得L中所有记录位于轴值左边，中所有记录位于轴值左边，R中记录位于轴值右边，即轴中记录位于轴值右边，即轴值已位于正确位置值已位于正确位置 北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京
11、大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法13分割过程描述分割过程描述开始前，将轴值与最后一个记录交换，并将轴值保存在一开始前，将轴值与最后一个记录交换，并将轴值保存在一个临时变量中（最后位置为个临时变量中（最后位置为空闲位置空闲位置）用指针用指针left,right扫描整个序列，初值位于序列的两端扫描整个序列，初值位于序列的两端首先，首先，left指针从左边开始扫描，找到大于轴值的元素停下，指针从左边开始扫描，找到大于轴值的元素停下，将该元素放在空闲位置上，将该元素放在空闲位置上，left位置成为空闲位置位置成为空闲位置然后，从然后，从right前面位置寻找
12、小于轴值的元素，找到后停下，前面位置寻找小于轴值的元素，找到后停下，将该元素放在将该元素放在left位置的空闲位置上，位置的空闲位置上，right位置成为空闲位位置成为空闲位置置重复上述过程，直至重复上述过程，直至left与与right相遇，整个过程结束相遇，整个过程结束分割过程完毕分割过程完毕北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法left快速排序的过程快速排序的过程212108082525494925*25*1616初始关键字初始关键字08082525494925*25*1616
13、212108082525494925*25*161608082525494925*25*161608082525494925*25*161608082525494925*25*16162121pivot一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序leftrightrightrightleftleftrightrightleftrightleft北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法08082525494925*25*16162121完成一
14、趟排序完成一趟排序分别进行快速排序分别进行快速排序08082525494925*25*16162121有序序列有序序列08082525494925*25*16162121212125*25*25*2525494908081616算法算法quicksort是一个递归的算法是一个递归的算法,其递归树如图所示其递归树如图所示北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法16快速排序算法快速排序算法template class QuickSorter:public Sorter/快速排序类快速排序
15、类private:int SelectPivot(int left,int right);/选择轴值，返回轴值下标选择轴值，返回轴值下标int Partition(Record Array,int left,int right);/分割分割,返回轴值位置返回轴值位置public:void Sort(Record Array,int left,int right);template int QuickSorter:SelectPivot(int left,int right)/参数参数left,right分别表示序列的左右端下标分别表示序列的左右端下标return(left+right)/2;/
16、选择中间纪录作为轴值选择中间纪录作为轴值 北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法17快速排序函数快速排序函数template void QuickSorter:Sort(Record Array,int left,int right)/Array为待排序数组，为待排序数组，i,j分别为数组两端分别为数组两端if(right=left)/如果子序列中只有如果子序列中只有0或或1个记录，就不需排序个记录，就不需排序return;int pivot=SelectPivot(left,ri
17、ght);/选择轴值选择轴值swap(Array,pivot,right);/将轴值放在数组末端将轴值放在数组末端pivot=Partition(Array,left,right);/对剩余的记录进行分割对剩余的记录进行分割 Sort(Array,left,pivot-1);/对轴值左边的子序列进行递归快速排序对轴值左边的子序列进行递归快速排序 Sort(Array,pivot+1,right);/对轴值右边的子序列进行递归快速排序对轴值右边的子序列进行递归快速排序 北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据
18、结构与算法数据结构与算法18分割函数分割函数template int QuickSorter:Partition(Record Array,int left,int right)/分割函数，分割后轴值已到达正确位置分割函数，分割后轴值已到达正确位置 Record TempRecord;/存放轴值的临时变量存放轴值的临时变量 int i=left;/i为左指针，为左指针，j为右指针为右指针 int j=right;/将轴值存放在临时变量中将轴值存放在临时变量中 TempRecord=Arrayj;北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据
19、结构与算法数据结构与算法数据结构与算法数据结构与算法19/开始分割，开始分割，i,j不断向中间移动，直到相遇不断向中间移动，直到相遇while(i!=j)/i指针右移，直到找到一个大于等于轴值的记录指针右移，直到找到一个大于等于轴值的记录while(Compare:le(Arrayi,TempRecord)&(ji)i+;/如果如果i,j未相遇就将逆序元素换到右边空闲位置未相遇就将逆序元素换到右边空闲位置if(i i)j-;/如果如果i,j未相遇就将逆序元素换到左边空闲位置未相遇就将逆序元素换到左边空闲位置if(ij)Arrayi=Arrayj;i+;/i指针向右移动一步指针向右移动一步Arr
20、ayi=TempRecord;/把轴值回填到分界位置把轴值回填到分界位置i上上return i;/返回分界位置返回分界位置i 北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法20算法复杂性分析算法复杂性分析快速排序的趟数取决于递归树的高度快速排序的趟数取决于递归树的高度如果每次划分对一个对象定位后如果每次划分对一个对象定位后,该对象左右两侧子序列的长度相同该对象左右两侧子序列的长度相同,则下则下 一步将是对两个长度减半的子序列进行排序一步将是对两个长度减半的子序列进行排序,这是最理想的情况这
21、是最理想的情况在在 n个元素的序列中个元素的序列中,对一个对象定位所需时间为对一个对象定位所需时间为 O(n)。若设。若设 t(n)是对是对 n 个元素的序列进行排序所需的时间个元素的序列进行排序所需的时间,而且每次对一个对象正确定位后而且每次对一个对象正确定位后,正好正好把序列划分为长度相等的两个子序列把序列划分为长度相等的两个子序列,此时此时,总的计算时间为总的计算时间为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 lo
22、g2n)北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法21算法复杂性分析算法复杂性分析可以证明可以证明,函数函数quicksort的平均计算时间也是的平均计算时间也是O(nlog2n)。实验结果表明。实验结果表明:就就平均计算时间而言平均计算时间而言,快速排序是所有内排序方法中最好的一个快速排序是所有内排序方法中最好的一个快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数最大递归调用层次数与递归树的高度一致最大递归调用层
23、次数与递归树的高度一致,理想情况为理想情况为 log2(n+1)。因此，。因此，要求存储开销为要求存储开销为 O(log2n)。在最坏的情况在最坏的情况,其递归树成为单支树（与轴值的选择策略有关）其递归树成为单支树（与轴值的选择策略有关）,每次划分每次划分只得到一个比上一次少一个对象的子序列。总的排序码比较次数将达只得到一个比上一次少一个对象的子序列。总的排序码比较次数将达快速排序是一种快速排序是一种不稳定的排序方法（不稳定的排序方法（why?）北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算
24、法22优化的快速排序优化的快速排序优化思想优化思想当快速排序的子数组小于某个长度时，其计算效当快速排序的子数组小于某个长度时，其计算效率不如直接插入排序高率不如直接插入排序高经验表明经验表明最好的组合方式是当最好的组合方式是当n（子数组的长度）小于等（子数组的长度）小于等于于9或或16或或28时就使用插入排序（视测试环境有时就使用插入排序（视测试环境有关）关）北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法23优化快速排序算法优化快速排序算法#define THRESHOLD 9 或或 16
25、 或或 28template void ModQuickSort(Record Array,int left,int right)/优化的快速排序，优化的快速排序，if(right-left+1 THRESHOLD)/对长度大于阈值对长度大于阈值(28最佳最佳)的长子串处理的长子串处理int pivot=SelectPivot(left,right);/选择轴值选择轴值swap(Array,pivot,right);/将轴值放在数组末端将轴值放在数组末端pivot=Partition(Array,left,right);/分割后轴值已到达正确位置分割后轴值已到达正确位置ModQuickSort
26、(Array,left,pivot-1);/对轴值左边的子序列进行递归快速排序对轴值左边的子序列进行递归快速排序ModQuickSort(Array,pivot+1,right);/对轴值右边的子序列进行递归快速排序对轴值右边的子序列进行递归快速排序template void Quicksort(Record*Array,int n)ModQuickSort(Array,0,n-1);/调用优化的递归快排，不处理小子串调用优化的递归快排，不处理小子串InsertSort(Array,n);/最后这个序列进行扫尾插入排序最后这个序列进行扫尾插入排序北京大学信息科学技术学院北京大学信息科学技术学院
27、北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法242 2、归并排序、归并排序基本思想基本思想简单地将原始序列划分为两个子序列简单地将原始序列划分为两个子序列分别对每个子序列递归排序分别对每个子序列递归排序最后将排好序的子序列合并为一个有序序列，即最后将排好序的子序列合并为一个有序序列，即归并过程归并过程快速排序侧重于快速排序侧重于分割过程分割过程，而归并排序侧重于，而归并排序侧重于归归并过程并过程北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据
28、结构与算法(25 34 45 32 78 12 34 64)(25 34 45 32)(78 12 34 64)(25 34)(45 32)(78 12)(34 64)(25)(34)(45)(32)(78)(12)(34)(64)(25 34)(32 45)(12 78)(34 64)(25 32 34 45)(12 34 64 78)(12 25 32 34 34 45 64 78)先先划划分分再再归归并并归并思想归并思想北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法26两路归并排序算
29、法两路归并排序算法template void MergeSort(Record Array,Record TempArray,int left,int right)/Array为待排序数组，为待排序数组，left，right两端两端int middle;if(left right)/如果序列中只有如果序列中只有0或或1个记录，就不用排序个记录，就不用排序middle=(left+right)/2;/从中间划分为两个子序列从中间划分为两个子序列MergeSort(Array,TempArray,left,middle);/对左边一半进行递归对左边一半进行递归MergeSort(Array,Tem
30、pArray,middle+1,right);/对右边一半进行递归对右边一半进行递归Merge(Array,TempArray,left,right,middle);/进行归并进行归并北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法27template void Merge(Record Array,Record TempArray,int left,int right,int middle)int i,j,index1,index2;for(j=left;j=right;j+)/将数组暂存
31、入临时数组将数组暂存入临时数组TempArrayj=Arrayj;index1=left;/左边子序列的起始位置左边子序列的起始位置index2=middle+1;/右边子序列的起始位置右边子序列的起始位置i=left;/从左开始归并从左开始归并while(index1=middle&index2=right)/取较小者插入合并数组中取较小者插入合并数组中if(TempArrayindex1=TempArrayindex2)/为保稳定，相等时左边优先为保稳定，相等时左边优先Arrayi+=TempArrayindex1+;else Arrayi+=TempArrayindex2+;北京大学信息
32、科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法while(index1=middle)/只剩左序列，可以直接复制只剩左序列，可以直接复制Arrayi+=TempArrayindex1+;while(index2=right)/与上个循环互斥，直接复制剩余的右序列与上个循环互斥，直接复制剩余的右序列Arrayi+=TempArrayindex2+;北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法归并排
33、序性能分析容易看出，对容易看出，对 n 个记录进行归并排序的时间复杂度为个记录进行归并排序的时间复杂度为(nlogn)。即：。即：每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)，总共需进行总共需进行 logn 趟。趟。归并排序需要附加一倍的存储量归并排序需要附加一倍的存储量O(n)，归并排序是辅助存归并排序是辅助存储量最多的一种排序方法。储量最多的一种排序方法。是是稳定排序算法稳定排序算法北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法30优化的归并排序优化的归并排序R.Sedg
34、ewick优化思想优化思想1.把数组暂时复制到临时数组时，将第二个子数组中元素的把数组暂时复制到临时数组时，将第二个子数组中元素的顺序颠倒了一下。这样，两个子数组从两端开始处理，向顺序颠倒了一下。这样，两个子数组从两端开始处理，向中间推进，使得这两个子数组的两端互相成为另一个数组中间推进，使得这两个子数组的两端互相成为另一个数组的的“监视哨监视哨”，从而不用，从而不用像像Merge算法算法那样需要检查子序列那样需要检查子序列结束的情况结束的情况2.另外，当子数组小于某个长度（例如另外，当子数组小于某个长度（例如28）时，也不继续递）时，也不继续递归，而是在最后对整个序列使用插入排序归，而是在最
35、后对整个序列使用插入排序北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法31优化的归并排序算法优化的归并排序算法#define THRESHOLD 28template void ModMergeSort(Record Array,Record TempArray,int left,int right)/Array为待排序数组，为待排序数组，left，right两端两端int middle;/如果序列长度大于阈值如果序列长度大于阈值(28最佳最佳)，跳出递归，跳出递归if(right-lef
36、t+1 THRESHOLD)middle=(left+right)/2;/从中间划分为两个子序列从中间划分为两个子序列ModMergeSort(Array,TempArray,left,middle);/对左边一半进行递归对左边一半进行递归ModMergeSort(Array,TempArray,middle+1,right);/对右边一半进行递归对右边一半进行递归ModMerge(Array,TempArray,left,right,middle);/进行归并进行归并/若长度小于等于阈值，采用直接插入排序若长度小于等于阈值，采用直接插入排序 else InsertSort(&Arraylef
37、t,right-left+1);北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法32template void ModMerge(Record Array,Record TempArray,int left,int right,int middle)int index1,index2;/两个子序列的起始位置两个子序列的起始位置int i,j,k;for(i=left;i=middle;i+)/复制左边的子序列复制左边的子序列TempArrayi=Arrayi;for(j=1;j=right-
38、middle;j+)/复制右边的子序列，但顺序颠倒过来复制右边的子序列，但顺序颠倒过来TempArrayright-j+1=Arrayj+middle;/开始归并，取较小者插入合并数组中开始归并，取较小者插入合并数组中for(index1=left,index2=right,k=left;k=right;k+)if(TempArrayindex1=TempArrayindex2)/为稳定，相等时左边优先为稳定，相等时左边优先Arrayk=TempArrayindex1+;else Arrayk=TempArrayindex2-;/算法复杂性本质没有发生改变，但性能得到了一些优化算法复杂性本质没
39、有发生改变，但性能得到了一些优化归并函数归并函数北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法338.5 堆排序堆排序直接选择排序：直接从剩余记录中线性查找最大直接选择排序：直接从剩余记录中线性查找最大(小小)记录记录堆排序堆排序基于最大（小）堆来实现，效率更高基于最大（小）堆来实现，效率更高堆的分类堆的分类堆的完全二叉树表示堆的完全二叉树表示堆可以用一棵完全二叉树表示，则堆可以用一棵完全二叉树表示，则 K2i+1 是是 Ki 的左孩子的左孩子;K2i+2 是是 Ki 的右孩子。的右孩子。
40、或或(最小堆最小堆)(最大堆最大堆)KiK2i+1KiK2i+2KiK2i+1KiK2i+2(i=0,1,n/2-1)北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法基本思想基本思想1.对所有记录建立最大堆对所有记录建立最大堆2.取出堆顶的最大记录移到数组末端，放在下标取出堆顶的最大记录移到数组末端，放在下标n-1的的位置；重新将剩下的位置；重新将剩下的n-1个记录建堆，再取新堆顶最个记录建堆，再取新堆顶最大的记录，放到数组第大的记录，放到数组第n-2位；位；不断重复这一操；不断重复这一操作
41、，直到堆为空。作，直到堆为空。3.这时数组正好是按从小到大排序这时数组正好是按从小到大排序北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法35例：对刚才建好的最大堆进行排序：0808 25 21 25*16 25 21 25*16 4949交换交换交换交换 0 0号与号与号与号与 5 5号记录号记录号记录号记录 r0 rn-1r0 rn-14949252525*25*21211616080801234549 25 21 25*16 0849 25 21 25*16 08初始最大堆初始最大堆初
42、始最大堆初始最大堆252525*25*1616212102543108084949北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法361616 25*21 08 25*21 08 25 4925 49交换交换交换交换 0 0号与号与号与号与 4 4 号记录号记录号记录号记录0808 25 2125 21 25*16 25*16 4949从从从从 0 0 号到号到号到号到 4 4 号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆0808252525*25*212116
43、164949012345161625*25*08082525212149490254310808252525*25*080825 25 2525*2121 08 08 16 16 4949北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法370808 16 21 16 21 25*25*2525 49 49交换交换交换交换 0 0 号与号与号与号与 3 3 号记录号记录号记录号记录25*16 21 08 25*16 21 08 25 4925 49从从从从 0 0号到号到号到号到 3 3号号号
44、号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆25*25*161608082121252549490123450808161625*25*252521214949025431161625*25*北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法380808 16 16 21 25*21 25*2525 49 49交换交换交换交换 0 0号与号与号与号与2 2 号记录号记录号记录号记录21 16 08 21 16 08 25*25*2525 49 49从从从从 0 0 号到
45、号到号到号到 2 2号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆2121161625*25*0808252549490123450808161625*25*25252121494902543121210808北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法390808 16 21 25*16 21 25*2525 49 49交换交换交换交换 0 0 号与号与号与号与1 1 号记录号记录号记录号记录排序完毕。排序完毕。排序完毕。排序完毕。16 08 16 08 2
46、121 25*25*2525 49 49从从从从 0 0 号到号到号到号到 1 1 号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆1616080825*25*2121252549490123450808161625*25*25252121494902543116160808北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法40堆排序算法堆排序算法template void sort(Record Array,int n)int i;MaxHeap max_heap=
47、MaxHeap(Array,n,n);/建堆建堆/依次找出剩余记录中的最大记录，即堆顶依次找出剩余记录中的最大记录，即堆顶for(i=0;i n;i+)max_heap.RemoveMax();北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法41算法分析算法分析非稳定性排序非稳定性排序建堆：建堆：(n)删除一次堆顶重新建堆：删除一次堆顶重新建堆：(log n)一次建堆一次建堆,n次删除堆顶，总时间代价为次删除堆顶，总时间代价为(nlog n)理论上，堆排序最佳、最差、平均情况下的时间代价理论上，堆排序最佳、最差、平均情况下的时间代价均为均为(nlog n)辅助空间代价：辅助空间代价：(1)北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院北京大学信息科学技术学院数据结构与算法数据结构与算法数据结构与算法数据结构与算法再见再见联系信息：联系信息：电子邮件：电子邮件： 电电 话：话：62754785 办公地点：理科办公地点：理科2号楼号楼2307室室