《七章节内排序.ppt》由会员分享，可在线阅读，更多相关《七章节内排序.ppt（156页珍藏版）》请在三一办公上搜索。
1、第七章 内排序,任课教员：张 铭http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 2,大纲,7.1 基本概念7.2 三种(n2)的简单排序插入排序直接插入排序二分法插入排序冒泡排序选择排序7.3 Shell排序,北京大学信息学院 版权所有，转载或翻印必究 Page 3,大纲（续）,7.4 基于分治法的排序快速排序归并排序7.5 堆排序7.6 分配排序和基数排序7.7 各种排序算法的理论和实验时间代价7.8 排序问题的下限,北京大学信息学院 版权所有，转载或翻印必究 Page 4,7.1基本概念,记录(Record)：结点，进行排序的基本单位关键码(Key)：唯一确定记录的一个
2、或多个域排序码(Sort Key)：作为排序运算依据的一个或多个域序列(Sequence)：线性表，由记录组成的集合,北京大学信息学院 版权所有，转载或翻印必究 Page 5,7.1基本概念（续）,排序(Sorting)将序列中的记录按照排序码特定的顺序排列起来，即排序码域的值具有不减(或不增)的顺序。,北京大学信息学院 版权所有，转载或翻印必究 Page 6,排序问题,给定一个序列R=r1,r2,，rn，其排序码分别为k=k1,k2,，kn排序的目的就是将R中的记录按照特定的顺序重新排列，形成一个新的有序序列R=r1,r2,，rn相应排序码为k=k1,k2,，kn其中k1k2kn或k1k2k
3、n，前者称为不减序，后者称为不增序。,北京大学信息学院 版权所有，转载或翻印必究 Page 7,7.1基本概念（续）,内排序(Internal Sorting)：整个排序过程中所有的记录都可以直接存放在内存中 外排序(External Sorting)：内存无法容纳所有记录，排序过程中还需要访问外存,北京大学信息学院 版权所有，转载或翻印必究 Page 8,7.1基本概念（续）,“正序”序列：待排序序列正好符合排序要求“逆序”序列：把待排序序列逆转过来，正好符合排序要求,北京大学信息学院 版权所有，转载或翻印必究 Page 9,7.1基本概念（续）,“稳定的”(stable)排序算法：如果存在
4、多个具有相同排序码的记录，经过排序后这些记录的相对次序仍然保持不变。,北京大学信息学院 版权所有，转载或翻印必究 Page 10,排序算法的分类,简单排序插入排序(Insert sort)直接选择排序(Selection sort)冒泡排序(Bubble sort)Shell排序(Shell sort),北京大学信息学院 版权所有，转载或翻印必究 Page 11,排序算法的分类（续）,分治排序快速排序(Quicksort)归并排序(Mergesort)堆排序(Heapsort)分配排序(Binsort),北京大学信息学院 版权所有，转载或翻印必究 Page 12,排序算法的衡量标准,时间代价：
5、记录的比较和交换次数 空间代价算法的复杂度,北京大学信息学院 版权所有，转载或翻印必究 Page 13,总的排序类,template class Sorter/总排序类protected:/交换数组中的两个元素static void swap(Record Array,int i,int j);public:/对数组Array进行排序void Sort(Record Array,int n);/输出数组内容void PrintArray(Record array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 14,Compare类,Compare类是用来比较记录的排序码
6、，把它单独定义成模板参数，是为了方便针对不同类型的排序码进行比较。为了简便起见，我们只讨论整数排序的例子。,北京大学信息学院 版权所有，转载或翻印必究 Page 15,int_intCompare 类,class int_intCompare/比较两个整型记录大小public:static bool lt(int x,int y)return xy;static bool le(int x,int y)return x=y;,北京大学信息学院 版权所有，转载或翻印必究 Page 16,swap函数,template void Sorter:swap(Record Array,int i,int
7、 j)/交换数组中的两个元素Record TempRecord=Arrayi;Arrayi=Arrayj;Arrayj=TempRecord;,北京大学信息学院 版权所有，转载或翻印必究 Page 17,PrintArray函数,template void Sorter:PrintArray(Record Array,int n)/输出数组内容for(int i=0;in;i+)coutArrayi;coutendl;,北京大学信息学院 版权所有，转载或翻印必究 Page 18,7.2 三种(n2)的简单排序,插入排序(Insert Sort)冒泡排序(Bubble Sort)选择排序(Sel
8、ection Sort),北京大学信息学院 版权所有，转载或翻印必究 Page 19,7.2.1插入排序,算法思想：逐个处理待排序的记录，每个新记录都要与前面那些已排好序的记录进行比较，然后插入到适当的位置。,北京大学信息学院 版权所有，转载或翻印必究 Page 20,北京大学信息学院 版权所有，转载或翻印必究 Page 21,插入排序类,template class InsertSorter:public Sorter;,北京大学信息学院 版权所有，转载或翻印必究 Page 22,直接插入排序,template class StraightInsertSorter:public Insert
9、Sorter/直接插入排序类public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 23,template void StraightInsertSorter:Sort(Record Array,int n)/Array为待排序数组，n为数组长度for(int i=1;i0;j-)if(Compare:lt(Arrayj,Arrayj-1)swap(Array,j,j-1);else break;/此时i前面记录已排序,北京大学信息学院 版权所有，转载或翻印必究 Page 24,算法分析,稳定空间代价：(1)时间代价：最
10、佳情况：n-1次比较，0次比较，(n)最差情况：比较和交换次数为平均情况：(n2),北京大学信息学院 版权所有，转载或翻印必究 Page 25,优化的插入排序算法,template class ImprovedInsertSorter:public InsertSorter/优化的插入排序类public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 26,template voidImprovedInsertSorter:Sort(Record Array,int n)/Array为待排序数组，n为数组长度Record Te
11、mpRecord;/临时变量/依次插入第i个记录for(int i=1;in;i+)TempRecord=Arrayi;/从i开始往前寻找记录i的正确位置int j=i-1;,北京大学信息学院 版权所有，转载或翻印必究 Page 27,/将那些大于等于记录i的记录后移while(j=0),北京大学信息学院 版权所有，转载或翻印必究 Page 28,二分法插入排序,算法思想：在插入第i个记录时，前面的记录已经是有序的了，可以用二分法查找第i个记录的正确位置。,北京大学信息学院 版权所有，转载或翻印必究 Page 29,template class BinaryInsertSorter:publi
12、c InsertSorter/二分法插入排序类public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 30,template void BinaryInsertSorter:Sort(Record Array,int n)/Array为待排序数组，n为数组长度Record TempRecord;/临时变量/记录已排好序序列的左、右、中位置int left,right,middle;/依次插入第i个记录for(int i=1;in;i+)/保存当前待插入记录TempRecord=Arrayi;,北京大学信息学院 版权所有，
13、转载或翻印必究 Page 31,/记录已排好序序列的左右位置left=0;right=i-1;/开始查找待插入记录的正确位置while(left=right)/中间位置 middle=(left+right)/2;/如果待插入记录比中间记录小,/就在左一半中查找，/否则在右一半中查找if(Compare:lt(TempRecord,Arraymiddle)right=middle-1;,北京大学信息学院 版权所有，转载或翻印必究 Page 32,else left=middle+1;/将前面所有大于当前待插入记录的记录后移for(int j=i-1;j=left;j-)Arrayj+1=Arr
14、ayj;/将待插入记录回填到正确位置Arrayleft=TempRecord;,北京大学信息学院 版权所有，转载或翻印必究 Page 33,算法分析,稳定空间代价：(1)时间代价：插入每个记录需要(log i)次比较最多移动i+1次，最少2次（移动临时记录）因此最佳情况下总时间代价为(nlog n)，最差和平均情况下仍为(n2),北京大学信息学院 版权所有，转载或翻印必究 Page 34,7.2.2 冒泡排序,算法思想：不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。,北京大学信息学院 版权所有，转载或翻印必究 Page 35,北京大学信息学院 版权所有，
15、转载或翻印必究 Page 36,冒泡排序类,template class BubbleSorter:public Sorter/冒泡排序类public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 37,冒泡排序算法,template void BubbleSorter:Sort(Record Array,int n)/冒泡排序，Array为待排数组，n为数组长度/第i个记录冒泡for(int i=1;i=i;j-)if(Compare:lt(Arrayj,Arrayj-1)swap(Array,j,j-1);,北京大学信息
16、学院 版权所有，转载或翻印必究 Page 38,算法分析,稳定空间代价：(1)时间代价：比较次数：交换次数最多为(n2)，最少为0，平均为(n2)。最大，最小，平均时间代价均为(n2)。,北京大学信息学院 版权所有，转载或翻印必究 Page 39,优化的冒泡排序,改进：检查每次冒泡过程中是否发生过交换，如果没有，则表明整个数组已经排好序了，排序结束。避免不必要的比较,北京大学信息学院 版权所有，转载或翻印必究 Page 40,优化的冒泡排序,template class ImprovedBubbleSorter:public Sorter/优化的冒泡排序类public:void Sort(Re
17、cord Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 41,template void ImprovedBubbleSorter:Sort(Record Array,int n)/Array为待排序数组，n为数组长度bool NoSwap;/是否发生交换的标志for(int i=1;i=i;j-),北京大学信息学院 版权所有，转载或翻印必究 Page 42,if(Compare:lt(Arrayj,Arrayj-1)/如果发生了交换，/标志变为假swap(Array,j,j-1);NoSwap=false;/如果没发生过交换，/表示已排好序，结束算法if(
18、NoSwap)return;,北京大学信息学院 版权所有，转载或翻印必究 Page 43,算法分析,稳定空间代价为(1)时间代价：最小时间代价为(n)：最佳情况下只运行第一轮循环其他情况下时间代价仍为(n2),北京大学信息学院 版权所有，转载或翻印必究 Page 44,7.2.3 直接选择排序,算法思想:找出剩下的未排序记录中的最小记录，然后直接与数组中第i个记录交换，比冒泡排序减少了移动次数,北京大学信息学院 版权所有，转载或翻印必究 Page 45,北京大学信息学院 版权所有，转载或翻印必究 Page 46,直接选择排序,template class StraightSelectSorte
19、r:public Sorter/直接选择排序类public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 47,template void StraightSelectSorter:Sort(Record Array,int n)/Array为待排序数组，n为数组长度/依次选出第i小的记录，/即剩余记录中最小的那个for(int i=0;in-1;i+)/首先假设记录i就是最小的int Smallest=i;/开始向后扫描所有剩余记录for(int j=i+1;jn;j+),北京大学信息学院 版权所有，转载或翻印必究 Pag
20、e 48,/如果发现更小的记录，记录它的位置 if(Compare:lt(Arrayj,ArraySmallest)Smallest=j;/将第i小的记录放在数组中第i个位置 swap(Array,i,Smallest);,北京大学信息学院 版权所有，转载或翻印必究 Page 49,算法分析,不稳定 空间代价：(1)时间代价：比较次数：(n2)，与冒泡排序一样交换次数：n-1 总时间代价：(n2),北京大学信息学院 版权所有，转载或翻印必究 Page 50,7.2.4 简单排序算法的时间代价对比,北京大学信息学院 版权所有，转载或翻印必究 Page 51,北京大学信息学院 版权所有，转载或翻印
21、必究 Page 52,北京大学信息学院 版权所有，转载或翻印必究 Page 53,7.3 Shell排序,直接插入排序的两个性质：在最好情况（序列本身已是有序的）下时间代价为(n)对于短序列，直接插入排序比较有效Shell排序有效地利用了直接插入排序的这两个性质。,北京大学信息学院 版权所有，转载或翻印必究 Page 54,Shell排序,算法思想：先将序列转化为若干小序列，在这些小序列内进行插入排序；逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更有序的状态，最后对整个序列进行扫尾直接插入排序，从而完成排序。,北京大学信息学院 版权所有，转载或翻印必究 Page 55,北京大
22、学信息学院 版权所有，转载或翻印必究 Page 56,“增量每次除以2递减”的Shell排序,template class ShellSorter:public Sorter/Shell排序类private:/针对变化的增量而修改的插入排序算法，参数/delta表示当前的增量void ModifiedInsertSort(Record Array,int n,int delta);public:void Sort(Record Array,int n);,北京大学信息学院 版权所有，转载或翻印必究 Page 57,template Void ShellSorter:Sort(Record Ar
23、ray,int n)/Shell排序，Array为待排序数组，/n为数组长度/增量delta每次除以2递减for(int delta=n/2;delta0;delta/=2)/分别对delta个子序列排序 for(int j=0;jdelta;j+)ModifiedInsertSort(,北京大学信息学院 版权所有，转载或翻印必究 Page 58,针对变化的增量而修改的插入排序算法,template void ShellSorter:ModifiedInsertSort(Record Array,int n,int delta)/参数delta表示当前的增量/对子序列中第i个记录排序for(i
24、nt i=delta;i=delta;j-=delta)if(Compare:lt(Arrayj,Arrayj-delta)swap(Array,j,j-delta);else break;,北京大学信息学院 版权所有，转载或翻印必究 Page 59,算法分析,不稳定空间代价：(1)时间代价：(n2)选择适当的增量序列，可以使得时间代价接近(n)。,北京大学信息学院 版权所有，转载或翻印必究 Page 60,增量序列的选择,增量每次除以2递减，时间代价为(n2)增量序列为2k-1，2k-1-1，7，3，1 时，时间代价为(n3/2)选取其他增量序列还可以更进一步减少时间代价,北京大学信息学院
25、版权所有，转载或翻印必究 Page 61,7.4 基于分治法的排序,将原始数组分为若干个子部分然后分别进行排序 两种算法快速排序归并排序,北京大学信息学院 版权所有，转载或翻印必究 Page 62,7.4.1 快速排序,算法思想：选择轴值（pivot）将序列划分为两个子序列L和R，使得L中所有记录都小于或等于轴值，R中记录都大于轴值对子序列L和R递归进行快速排序,北京大学信息学院 版权所有，转载或翻印必究 Page 63,北京大学信息学院 版权所有，转载或翻印必究 Page 64,轴值选择,尽可能使L，R长度相等选择策略：选择最左边记录随机选择选择平均值,北京大学信息学院 版权所有，转载或翻印
26、必究 Page 65,分割过程（Partition）,整个快速排序的关键分割后使得L中所有记录位于轴值左边，R中记录位于轴值右边，即轴值以位于正确位置,北京大学信息学院 版权所有，转载或翻印必究 Page 66,北京大学信息学院 版权所有，转载或翻印必究 Page 67,北京大学信息学院 版权所有，转载或翻印必究 Page 68,快速排序算法,template class QuickSorter:public Sorter/快速排序类private:/选择轴值，返回轴值下标int SelectPivot(int left,int right);/分割,返回轴值位置int Partition(R
27、ecord Array,int left,int right);public:void Sort(Record Array,int left,int right);,北京大学信息学院 版权所有，转载或翻印必究 Page 69,template void QuickSorter:Sort(Record Array,int left,int right)/Array为待排序数组，i,j分别为数组两端/如果子序列中只有0或1个记录，就不需排序if(right=left)return;/选择轴值int pivot=SelectPivot(left,right);/分割前先将轴值放到数组末端swap(A
28、rray,pivot,right);,北京大学信息学院 版权所有，转载或翻印必究 Page 70,/对剩余的记录进行分割pivot=Partition(Array,left,right);/对轴值左边的子序列进行递归快速排序Sort(Array,left,pivot-1);/对轴值右边的子序列进行递归快速排序 Sort(Array,pivot+1,right);,北京大学信息学院 版权所有，转载或翻印必究 Page 71,轴值选择函数,template int QuickSorter:SelectPivot(int left,int right)/参数left,right分别表示序列的左右端下
29、标/选择中间纪录作为轴值return(left+right)/2;,北京大学信息学院 版权所有，转载或翻印必究 Page 72,分割函数,template int QuickSorter:Partition(Record Array,int left,int right)/分割函数，分割后轴值已到达正确位置Record TempRecord;/存放轴值的临时变量int i=left;/i为左指针，j为右指针int j=right;/将轴值存放在临时变量中TempRecord=Arrayj;/开始分割，i,j不断向中间移动，直到相遇,北京大学信息学院 版权所有，转载或翻印必究 Page 73,w
30、hile(i!=j)/i指针右移，直到找到一个大于等于轴值的记录while(Compare:lt(Arrayi,TempRecord)/j指针向左移动一步,北京大学信息学院 版权所有，转载或翻印必究 Page 74,/j指针左移，直到找到一个小于等于轴值的记录while(Compare:gt(Arrayj,TempRecord)/返回分界位置i,北京大学信息学院 版权所有，转载或翻印必究 Page 75,算法分析,最差情况：时间代价：(n2)空间代价：(n)最佳情况：时间代价：(nlog n)空间代价：(log n)平均情况：时间代价：(nlog n)空间代价：(log n),北京大学信息学院
31、 版权所有，转载或翻印必究 Page 76,算法分析（续）,不稳定优化：当快速排序的子数组小于某个长度时，不继续递归，直接进行插入排序。经验表明，最好的组合方式是当n（子数组的长度）小于等于16时就使用插入排序,北京大学信息学院 版权所有，转载或翻印必究 Page 77,优化的快速排序,#define THRESHOLD 16template class ImprovedQuickSorter:public Sorter/优化的快速排序类private:/选择轴值，返回轴值下标int SelectPivot(int left,int right);/分割,返回轴值位置int Partition
32、(Record Array,int left,int right);void DoSort(Record Array,int left,int right);public:void Sort(Record Array,int left,int right);,北京大学信息学院 版权所有，转载或翻印必究 Page 78,template void ImprovedQuickSorter:Sort(Record Array,int left,int right)/优化的快速排序，Array为待排序数组，i,j分别/为数组两端/先对序列进行递归排序DoSort(Array,left,right);/
33、最后对整个序列进行一次直接插入排序ImprovedInsertSorter insert_sorter;insert_sorter.Sort(Array,right-left+1);,北京大学信息学院 版权所有，转载或翻印必究 Page 79,template void ImprovedQuickSorter:DoSort(Record Array,int left,int right)/优化的快速排序，Array为待排序数组，i,j分别为数组/两端/如果序列中只有0或1个记录，就不用排序 if(right THRESHOLD),北京大学信息学院 版权所有，转载或翻印必究 Page 80,/选
34、择轴值int pivot=SelectPivot(left,right);/将轴值放在数组末端swap(Array,pivot,right);/对剩余的记录进行分割pivot=Partition(Array,left,right);/对分割出的子序列进行递归快速排序/对轴值左右分别进行排序DoSort(Array,left,pivot-1);DoSort(Array,pivot+1,right);,北京大学信息学院 版权所有，转载或翻印必究 Page 81,7.4.2 归并排序,算法思想简单地将原始序列划分为两个子序列分别对每个子序列递归排序最后将排好序的子序列合并为一个有序序列，即归并过程,
35、北京大学信息学院 版权所有，转载或翻印必究 Page 82,北京大学信息学院 版权所有，转载或翻印必究 Page 83,两路归并排序,template class TwoWayMergeSorter:public Sorter/两路归并排序类private:/归并过程void Merge(Record Array,Record TempArray,int left,int right,int middle);public:void Sort(Record Array,Record TempArray,int left,int right);,北京大学信息学院 版权所有，转载或翻印必究 Page
36、 84,template void TwoWayMergeSorter:Sort(Record Array,Record TempArray,int left,int right)/Array为待排序数组，left，right分别为数组两端/如果序列中只有0或1个记录，就不用排序if(left right)/从中间划分为两个子序列int middle=(left+right)/2;,北京大学信息学院 版权所有，转载或翻印必究 Page 85,/对左边一半进行递归Sort(Array,TempArray,left,middle);/对右边一半进行递归Sort(Array,TempArray,mi
37、ddle+1,right);/进行归并Merge(Array,TempArray,left,right,middle);,北京大学信息学院 版权所有，转载或翻印必究 Page 86,归并函数,template void TwoWayMergeSorter:Merge(Record Array,Record TempArray,int left,int right,int middle)/归并过程/将数组暂存入临时数组for(int j=left;j=right;j+)TempArrayj=Arrayj;,北京大学信息学院 版权所有，转载或翻印必究 Page 87,int index1=left
38、;/左边子序列的起始位置int index2=middle+1;/右子序列起始位置int i=left;/从左开始归并while(index1=middle),北京大学信息学院 版权所有，转载或翻印必究 Page 88,else Arrayi+=TempArrayindex2+;/处理剩余记录while(index1=middle)Arrayi+=TempArrayindex1+;while(index2=right)Arrayi+=TempArrayindex2+;,北京大学信息学院 版权所有，转载或翻印必究 Page 89,算法分析,空间代价：(n)总时间代价：(nlog n)不依赖于原始
39、数组的输入情况，最大、最小以及平均时间代价均为(nlog n)。,北京大学信息学院 版权所有，转载或翻印必究 Page 90,算法分析（续）,不稳定优化：同优化的快速排序一样，对基本已排序序列直接插入排序R.Sedgewick优化：归并时从两端开始处理，向中间推进,北京大学信息学院 版权所有，转载或翻印必究 Page 91,优化的归并排序,#define THRESHOLD 16template class ImprovedTwoWayMergeSorter:public Sorter/优化的两路归并排序类private:void Merge(Record Array,Record TempA
40、rray,int left,int right,int middle);/归并过程public:void Sort(Record Array,Record TempArray,int left,int right);,北京大学信息学院 版权所有，转载或翻印必究 Page 92,/优化的两路归并排序，Array为待排序数组，left，right分别为数组两端template void ImprovedTwoWayMergeSorter:Sort(Record Array,Record TempArray,int left,int right)DoSort(Array,TempArray,left
41、,right);/最后对整个序列进行一次直接插入排序ImprovedInsertSorter insert_sorter;insert_sorter.Sort(,北京大学信息学院 版权所有，转载或翻印必究 Page 93,template void ImprovedTwoWayMergeSorter:DoSort(Record Array,Record TempArray,int left,int right)/如果序列长度大于阈值(16最佳)，跳出递归if(right THRESHOLD)int middle=(left+right)/2;/从中间划分Sort(Array,TempArray
42、,left,middle);Sort(Array,TempArray,middle+1,right);Merge(Array,TempArray,left,right,middle);else ImprovedInsertSorter insert_sorter;insert_sorter.Sort(,北京大学信息学院 版权所有，转载或翻印必究 Page 94,template void ImprovedTwoWayMergeSorter:Merge(Record Array,Record TempArray,int left,int right,int middle)/归并过程int ind
43、ex1,index2;/两个子序列的起始位置int i,j,k;for(i=left;i=middle;i+)/复制左边的子序列TempArrayi=Arrayi;/复制右边的子序列，但顺序颠倒过来for(j=1;j=right-middle;j+)TempArrayright-j+1=Arrayj+middle;,北京大学信息学院 版权所有，转载或翻印必究 Page 95,/开始归并for(index1=left,index2=right,k=left;k=right;k+)if(Compare:lt(TempArrayindex1,TempArrayindex2)Arrayk=TempAr
44、rayindex1+;else Arrayk=TempArrayindex2-;,北京大学信息学院 版权所有，转载或翻印必究 Page 96,7.5 堆排序,直接选择排序：直接从剩余记录中线性查找最大记录堆排序：基于最大值堆来实现，效率更高,北京大学信息学院 版权所有，转载或翻印必究 Page 97,北京大学信息学院 版权所有，转载或翻印必究 Page 98,北京大学信息学院 版权所有，转载或翻印必究 Page 99,堆排序算法,template class HeapSorter:public Sorter/堆排序类public:void Sort(Record Array,int n);,北
45、京大学信息学院 版权所有，转载或翻印必究 Page 100,template void HeapSorter:Sort(Record Array,int n)/堆排序，Array为待排数组，n为数组长度Record record;MaxHeap max_heap=MaxHeap(Array,n,n);/建堆/依次找出剩余记录中的最大记录，即堆顶for(int i=0;in;i+)max_heap.Removemax(record);,北京大学信息学院 版权所有，转载或翻印必究 Page 101,算法分析,建堆：(n)删除堆顶:(log n)一次建堆,n次删除堆顶总时间代价为(nlog n)空间
46、代价为(1),北京大学信息学院 版权所有，转载或翻印必究 Page 102,7.6 分配排序和基数排序,不需要进行比较需要事先知道记录序列的一些具体情况,北京大学信息学院 版权所有，转载或翻印必究 Page 103,7.6.1 桶式排序,事先知道序列中的记录都位于某个小区间段0，m)内 将具有相同值的记录都分配到同一个桶中，然后依次按照编号从桶中取出记录，组成一个有序序列,北京大学信息学院 版权所有，转载或翻印必究 Page 104,桶式排序算法,template class BucketSorter:public Sorter/桶式排序类public:void Sort(Record Arr
47、ay,int n,int max);,北京大学信息学院 版权所有，转载或翻印必究 Page 105,/桶式排序，Array为待排序数组，数组长度为n,所/有记录都位于区间0,max)上template void BucketSorter:Sort(Record Array,int n,int max)int*TempArray=new Recordn;/临时数组 int*count=new intmax;/小于等于i的元素个数 int i;for(i=0;in;i+)TempArrayi=Arrayi;/所有计数器初始都为0 for(i=0;imax;i+)counti=0;,北京大学信息学院
48、 版权所有，转载或翻印必究 Page 106,/统计每个取值出现的次数 for(i=0;i=0;i-)Array-countTempArrayi=TempArrayi;,北京大学信息学院 版权所有，转载或翻印必究 Page 107,算法分析,时间代价：统计计数时：(n+m)输出有序序列时循环n次总的时间代价为(m+n)适用于m相对于n很小的情况,北京大学信息学院 版权所有，转载或翻印必究 Page 108,算法分析（续）,空间代价：m个计数器，长度为n的临时数组，(m+n)稳定,北京大学信息学院 版权所有，转载或翻印必究 Page 109,7.6.2 基数排序,桶式排序只适合m很小的情况当m很
49、大时，可以将一个记录的值即排序码拆分为多个部分来进行比较基数排序,北京大学信息学院 版权所有，转载或翻印必究 Page 110,基数排序,假设长度为n的序列R=r0，r1，rn-1 记录的排序码K包含d个子排序码K=(kd-1，kd-2，k1，k0)，则称R对排序码(kd-1，kd-2，k1，k0)有序就是对于任意两个记录R i，R j(0 i j n-1)，都满足(k i,d-1，k i,d-2，k i,1，k i,0)(k j,d-1，k j,d-2，k j,1，k j,0)其中k d-1称为最高排序码，k 0称为最低排序码。,北京大学信息学院 版权所有，转载或翻印必究 Page 111,
50、例子,例如：如果我们要对0到9999之间的整数进行排序将四位数看作是由四个排序码决定，即千、百、十、个位，其中千位为最高排序码，个位为最低排序码。基数r=10。可以按千、百、十、个位数字依次进行4次桶式排序4趟分配排序后，整个序列就排好序了。,北京大学信息学院 版权所有，转载或翻印必究 Page 112,基数排序分为两类,高位优先法（MSD，Most Significant Digit first）低位优先法（LSD，Least Significant Digit first）,北京大学信息学院 版权所有，转载或翻印必究 Page 113,高位优先法（MSD，Most Significant
