《第七章内排序》由会员分享，可在线阅读，更多相关《第七章内排序（156页珍藏版）》请在金锄头文库上搜索。
1、第七章第七章 内排序内排序任课教员：张任课教员：张 铭铭http:/ 版版权所有，转载或翻印必究权所有，转载或翻印必究大纲大纲n7.1 基本概念基本概念n7.2 三种三种(n2)的简单排序的简单排序n插入排序插入排序n直接插入排序直接插入排序n二分法插入排序二分法插入排序n冒泡排序冒泡排序n选择排序选择排序n7.3 Shell排序排序北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 大纲（续）大纲（续）n7.4 基于分治法的排序基于分治法的排序n快速排序快速排序n归并排序归并排序n7.5 堆排序堆排序n7.6 分配排序和基数排序分配排序和基数排序n7
2、.7 各种排序算法的理论和实验时各种排序算法的理论和实验时间代价间代价n7.8 排序问题的下限排序问题的下限北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.1基本概念基本概念n记录记录(Record)：结点，进行排序的结点，进行排序的基本单位基本单位n关键码关键码(Key)：唯一确定记录的一个唯一确定记录的一个或多个域或多个域n排序码排序码(Sort Key)：作为排序运算依作为排序运算依据的一个据的一个或多个域或多个域n序列序列(Sequence)：线性表，由记录线性表，由记录组成的集合组成的集合北京大学信息学院北京大学信息学院 版版权所有，
3、转载或翻印必究权所有，转载或翻印必究 Page 7.1基本概念（续）基本概念（续）n排序排序(Sorting) 将序列中的记将序列中的记录按照排序码特定的顺序排列起录按照排序码特定的顺序排列起来，来，即排序码域的值具有不减即排序码域的值具有不减( (或不增或不增) )的顺序的顺序。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序问题排序问题n给定一个序列给定一个序列R =r r1 1, r, r2 2, , ，r rn n，其其排序码分别为排序码分别为k =k k1 1, k, k2 2, , ，k kn nn排序的目的就是将排序的目的就是将
4、R中的记录按照特定的中的记录按照特定的顺序重新排列，形成一个新的有序序列顺序重新排列，形成一个新的有序序列R= r r1 1, r, r2 2, , ，r rn nn相应排序码为相应排序码为k =k k1 1, k, k2 2, , ，k kn nn其中其中k k1 1kk2 2kkn n或或k k1 1kk2 2kkn n ，前者称为不减序，前者称为不减序，后者称为不增序。后者称为不增序。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.1基本概念（续）基本概念（续）n内排序内排序(Internal Sorting)：整整个排序过程中所有的记
5、录都可以个排序过程中所有的记录都可以直接存放在内存中直接存放在内存中 n外排序外排序(External Sorting)：内内存无法容纳所有记录，排序过程存无法容纳所有记录，排序过程中还需要访问外存中还需要访问外存 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.1基本概念（续）基本概念（续）n“正序正序”序列序列 ：待排序序列正：待排序序列正好符合排序要求好符合排序要求 n“逆序逆序” 序列序列 ：把待排序序列：把待排序序列逆转过来，正好符合排序要求逆转过来，正好符合排序要求 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有
6、，转载或翻印必究 Page 7.1基本概念（续）基本概念（续）n“稳定的稳定的”(stable)排序算法排序算法 ：如果存在多个具有相同排序码：如果存在多个具有相同排序码的记录，经过排序后这些记录的的记录，经过排序后这些记录的相对次序仍然保持不变相对次序仍然保持不变 。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序算法的分类排序算法的分类n简单排序简单排序n插入排序插入排序(Insert sort)n直接选择排序直接选择排序(Selection sort)n冒泡排序冒泡排序(Bubble sort)nShell排序排序(Shell sort)
7、北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序算法的分类（续）排序算法的分类（续）n分治排序分治排序n快速排序快速排序(Quicksort)n归并排序归并排序(Mergesort)n堆排序堆排序(Heapsort)n分配排序分配排序 (Binsort)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序算法的衡量标准排序算法的衡量标准n时间代价：记录的比较和交换次时间代价：记录的比较和交换次数数 n空间代价空间代价n算法的复杂度算法的复杂度 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印
8、必究权所有，转载或翻印必究 Page 总的排序类总的排序类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 Compare类类nCom
9、pare类是用来比较记录的类是用来比较记录的排序码，把它单独定义成模板参排序码，把它单独定义成模板参数，是为了方便针对不同类型的数，是为了方便针对不同类型的排序码进行比较。为了简便起见，排序码进行比较。为了简便起见， 我们只讨论整数排序的例子。我们只讨论整数排序的例子。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page int_intCompare 类类class int_intCompare/比较两个整型记录大小比较两个整型记录大小public:static bool lt(int x,int y) return xy;static bool le(
10、int x,int y) return x=y; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page swap函数函数template void Sorter:swap(Record Array,int i,int j) /交换数组中的两个元素交换数组中的两个元素Record TempRecord = Arrayi;Arrayi = Arrayj;Arrayj = TempRecord;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page PrintArray函数函数template void Sorter:Pr
11、intArray(Record Array, int n) /输出数组内容输出数组内容for(int i=0;in;i+)coutArrayi ;coutendl;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.2 三种三种(n2)的简单排序的简单排序n插入排序插入排序(Insert Sort)n冒泡排序冒泡排序(Bubble Sort)n选择排序选择排序 (Selection Sort)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.2.1插入排序插入排序 n算法思想：算法思想：n逐个处理待排
12、序的记录，每个新逐个处理待排序的记录，每个新记录都要与前面那些已排好序的记录都要与前面那些已排好序的记录进行比较，然后插入到适当记录进行比较，然后插入到适当的位置。的位置。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 插入排序类插入排序类 template class InsertSorter:public Sorter; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 直接插入排序直接插入排序templa
13、te class StraightInsertSorter:public InsertSorter /直接插入排序类直接插入排序类public:void Sort(Record Array,int n);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void StraightInsertSorter:Sort(Record Array, int n) /Array为待排序数组，为待排序数组，n为数组长度为数组长度for (int i=1; i0;j-)if (Compare:lt(Arrayj, Arrayj-1)swap(Ar
14、ray, j, j-1);else break;/此时此时i前面记录已排序前面记录已排序北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n稳定稳定n空间代价：空间代价：(1) n时间代价：时间代价：n最佳情况：最佳情况：n-1次比较，次比较，0次比较，次比较，(n) n最差情况：比较和交换次数为最差情况：比较和交换次数为n平均情况：平均情况：(n2) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 优化的插入排序算法优化的插入排序算法 template class ImprovedIns
15、ertSorter:public InsertSorter /优化的插入排序类优化的插入排序类public:void Sort(Record Array,int n);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template voidImprovedInsertSorter:Sort(Record Array, int n) /Array为待排序数组，为待排序数组，n为数组长度为数组长度Record TempRecord;/ 临时变量临时变量/ 依次插入第依次插入第i个记录个记录for (int i=1; i=0) & (Compare:l
16、t(TempRecord, Arrayj)Arrayj+1 = Arrayj; j = j - 1;/此时此时j后面就是记录后面就是记录i的正确位置，回填的正确位置，回填 Arrayj+1 = TempRecord; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 二分法插入排序二分法插入排序 n算法思想：算法思想：n在插入第在插入第i个记录时，前面的记录个记录时，前面的记录已经是有序的了，可以用二分法已经是有序的了，可以用二分法查找第查找第i个记录的正确位置个记录的正确位置 。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转
17、载或翻印必究 Page template class BinaryInsertSorter:public InsertSorter /二分法插入排序类二分法插入排序类public:void Sort(Record Array,int n);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void BinaryInsertSorter:Sort(Record Array, int n) /Array为待排序数组，为待排序数组，n为数组长度为数组长度Record TempRecord; /临时变量临时变量 /记录已排好序序列的左、右、
18、中位置记录已排好序序列的左、右、中位置int left,right,middle;/依次插入第依次插入第i个记录个记录for (int i=1;in;i+)/保存当前待插入记录保存当前待插入记录TempRecord = Arrayi;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /记录已排好序序列的左右位置记录已排好序序列的左右位置left = 0; right = i-1;/开始查找待插入记录的正确位置开始查找待插入记录的正确位置while(left = left; j -)Arrayj+1 = Arrayj;/将待插入记录回填到正确位置将待插
19、入记录回填到正确位置Arrayleft = TempRecord; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n稳定稳定n空间代价：空间代价：(1)n时间代价：时间代价：n插入每个记录需要插入每个记录需要(log i)次比较次比较n最多移动最多移动i+1次次 ，最少，最少2次（移动临时记录）次（移动临时记录）n因此最佳情况下总时间代价为因此最佳情况下总时间代价为 (nlog n) ，最差和平均情况下仍为最差和平均情况下仍为(n2) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7
20、.2.2 冒泡排序冒泡排序 n算法思想：算法思想：n不停地比较相邻的记录，如果不不停地比较相邻的记录，如果不满足排序要求，就交换相邻记录，满足排序要求，就交换相邻记录，直到所有的记录都已经排好序。直到所有的记录都已经排好序。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 冒泡排序类冒泡排序类template class BubbleSorter:public Sorter /冒泡排序类冒泡排序类public:void Sort(Record Array,
21、int n); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 冒泡排序算法冒泡排序算法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); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析
22、算法分析n稳定稳定n空间代价：空间代价：(1) n时间代价时间代价 ：n比较次数比较次数 ：n交换次数最多为交换次数最多为(n2)，最少为最少为0，平均为，平均为(n2)。n最大，最小，平均时间代价均为最大，最小，平均时间代价均为(n2)。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 优化的冒泡排序优化的冒泡排序 n改进：检查每次冒泡过程中是否改进：检查每次冒泡过程中是否发生过交换，如果没有，则表明发生过交换，如果没有，则表明整个数组已经排好序了，排序结整个数组已经排好序了，排序结束。束。n避免不必要的比较避免不必要的比较北京大学信息学院北京大学
23、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 优化的冒泡排序优化的冒泡排序 template class ImprovedBubbleSorter:public Sorter /优化的冒泡排序类优化的冒泡排序类public:void Sort(Record Array,int n);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void ImprovedBubbleSorter:Sort(Record Array, int n) /Array为待排序数组，为待排序数组，n为数组长度为数组长度bool No
24、Swap;/ 是否发生交换的标志是否发生交换的标志for (int i=1; i=i; j-)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page if (Compare:lt(Arrayj, Arrayj-1) /如果发生了交换，如果发生了交换， /标志变为假标志变为假swap(Array, j, j-1);NoSwap = false;/ 如果没发生过交换，如果没发生过交换， / 表示已排好序，结束算法表示已排好序，结束算法if (NoSwap) return; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Pa
25、ge 算法分析算法分析n稳定稳定n空间代价为空间代价为(1) n时间代价：时间代价：n最小时间代价为最小时间代价为(n)：最佳情况最佳情况下只运行第一轮循环下只运行第一轮循环n其他情况下时间代价仍为其他情况下时间代价仍为(n2)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.2.3 直接选择排序直接选择排序 n算法思想算法思想:n找出剩下的未排序记录中的最小找出剩下的未排序记录中的最小记录，然后直接与数组中第记录，然后直接与数组中第i个记个记录交换录交换 ，比冒泡排序减少了移动，比冒泡排序减少了移动次数次数北京大学信息学院北京大学信息学院 版版
26、权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 直接选择排序直接选择排序 template class StraightSelectSorter:public Sorter /直接选择排序类直接选择排序类public:void Sort(Record Array,int n); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void StraightSelectSorter:Sort(Record Array, int n) /
27、Array为待排序数组，为待排序数组，n为数组长度为数组长度/ 依次选出第依次选出第i小的记录，小的记录， / 即剩余记录中最小的那个即剩余记录中最小的那个for (int i=0; in-1; i+)/ 首先假设记录首先假设记录i就是最小的就是最小的int Smallest = i;/ 开始向后扫描所有剩余记录开始向后扫描所有剩余记录for (int j=i+1;jn; j+)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page / 如果发现更小的记录，记录它的位置如果发现更小的记录，记录它的位置 if (Compare:lt(Arrayj, Arra
28、ySmallest) Smallest = j;/将第将第i小的记录放在数组中第小的记录放在数组中第i个位置个位置 swap(Array, i, Smallest); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n不稳定不稳定 n空间代价：空间代价：(1) n时间代价时间代价 ：n比较次数：比较次数：(n2)，与冒泡排序一样与冒泡排序一样n交换次数：交换次数：n-1 n总时间代价：总时间代价：(n2) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.2.4 简单排序算法的时间代简
29、单排序算法的时间代价对比价对比 比较次数比较次数 直接插直接插入排序入排序改改进的插的插入排入排序序二分法插二分法插入排序入排序冒泡排冒泡排序序改改进的的冒泡排冒泡排序序选择排序排序最佳情况最佳情况 (n)(n)(nlog n)(n2)(n)(n2)平均情况平均情况 (n2)(n2)(nlog n)(n2)(n2)(n2)最差情况最差情况 (n2)(n2)(nlog n)(n2)(n2)(n2)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 移动次数移动次数 直接直接插入插入排序排序改改进的的插入排插入排序序二分二分法插法插入排入排序序冒泡冒泡排序
30、排序改改进的冒的冒泡排泡排序序选择排序排序最佳情况最佳情况 0(n)(n)00(n)平均情况平均情况 (n2)(n2)(n2)(n2) (n2)(n)最差情况最差情况 (n2)(n2)(n2)(n2) (n2)(n)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 总代价总代价直接直接插入插入排序排序改改进的的插入排插入排序序二分法二分法插入排插入排序序冒泡冒泡排序排序改改进的的冒泡排冒泡排序序选择排序排序最佳情况最佳情况 (n)(n)(nlog n)(n2)(n)(n2)平均情况平均情况 (n2) (n2)(n2)(n2)(n2)(n2)最差情况最
31、差情况 (n2) (n2)(n2)(n2)(n2)(n2)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.3 Shell7.3 Shell排序排序n直接插入排序的两个性质：直接插入排序的两个性质：n在最好情况（序列本身已是有序在最好情况（序列本身已是有序的）下时间代价为的）下时间代价为(n)n对于短序列，直接插入排序比较对于短序列，直接插入排序比较有效有效nShell排序有效地利用了直接插排序有效地利用了直接插入排序的这两个性质入排序的这两个性质 。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page S
32、hellShell排序排序n算法思想：算法思想：n先将序列转化为若干小序列，在这些先将序列转化为若干小序列，在这些小序列内进行插入排序；小序列内进行插入排序；n逐渐扩大小序列的规模，而减少小序逐渐扩大小序列的规模，而减少小序列个数，使得待排序序列逐渐处于更列个数，使得待排序序列逐渐处于更有序的状态，有序的状态，n最后对整个序列进行扫尾直接插入排最后对整个序列进行扫尾直接插入排序，从而完成排序。序，从而完成排序。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Pag
33、e “增量每次除以增量每次除以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 templ
34、ate Void ShellSorter:Sort(Record Array, 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); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 针对变化的增量而
35、修改的插入针对变化的增量而修改的插入排序算法排序算法template void ShellSorter:ModifiedInsertSort(Record Array,int n, int delta) / 参数参数delta表示当前的增量表示当前的增量/ 对子序列中第对子序列中第i个记录排序个记录排序for (int i=delta; i=delta; j-=delta)if (Compare:lt(Arrayj, Arrayj-delta)swap(Array, j, j-delta);else break;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究
36、 Page 算法分析算法分析n不稳定不稳定n空间代价：空间代价：(1)n时间代价：时间代价：(n2) n选择适当的增量序列，可以使得选择适当的增量序列，可以使得时间代价接近时间代价接近(n) 。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 增量序列的选择增量序列的选择n增量每次除以增量每次除以2递减，时间代价为递减，时间代价为(n2) n增量序列为增量序列为2k-1，2k -1 -1，7，3，1 时，时间代价为时，时间代价为(n3/2) n选取其他增量序列还可以更进一步选取其他增量序列还可以更进一步减少时间代价减少时间代价北京大学信息学院北京大学
37、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.4 基于分治法的排序基于分治法的排序 n将原始数组分为若干个子部分然将原始数组分为若干个子部分然后分别进行排序后分别进行排序 n两种算法两种算法n快速排序快速排序n归并排序归并排序 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.4.1 快速排序快速排序n算法思想：算法思想：n选择轴值（选择轴值（pivot）n将序列划分为两个子序列将序列划分为两个子序列L和和R，使得使得L中所有记录都小于或等于轴中所有记录都小于或等于轴值，值，R中记录都大于轴值中记录都大于轴值n对子序列
38、对子序列L和和R递归进行快速排序递归进行快速排序 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 轴值选择轴值选择n尽可能使尽可能使L，R长度相等长度相等n选择策略：选择策略：n选择最左边记录选择最左边记录n随机选择随机选择n选择平均值选择平均值北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 分割过程（分割过程（Partition）n整个快速排序的关键整个快速排序的关键n分割后使得分割后使得L中所有记录位于轴中
39、所有记录位于轴值左边，值左边，R中记录位于轴值右边，中记录位于轴值右边，即轴值以位于正确位置即轴值以位于正确位置 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 快速排序算法快速排序算法template class QuickSorter:public Sorter /快速排序类快速排序类private:/选择轴值，返回轴值下标选择轴值，返回轴值下标int Sel
40、ectPivot(int left, int right); /分割分割,返回轴值位置返回轴值位置int Partition(Record Array, int left, int right); public:void Sort(Record Array,int left,int right); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void QuickSorter:Sort(Record Array, int left,int right) /Array为待排序数组，为待排序数组，i,j分别为数组两端分别为数组两端/
41、 如果子序列中只有如果子序列中只有0或或1个记录，就不需排序个记录，就不需排序if (right = left)return;/选择轴值选择轴值int pivot = SelectPivot(left, right); /分割前先将轴值放到数组末端分割前先将轴值放到数组末端swap(Array, pivot, right); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page / 对剩余的记录进行分割对剩余的记录进行分割pivot = Partition(Array, left, right); /对轴值左边的子序列进行递归快速排序对轴值左边的子序列进
42、行递归快速排序Sort(Array, left, pivot-1);/对轴值右边的子序列进行递归快速排序对轴值右边的子序列进行递归快速排序 Sort(Array, pivot +1, right); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 轴值选择函数轴值选择函数template int QuickSorter:SelectPivot(int left,int right) /参数参数left,right分别表示序列的左右端下标分别表示序列的左右端下标/选择中间纪录作为轴值选择中间纪录作为轴值return (left+right)/2; 北
43、京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 分割函数分割函数template int QuickSorter:Partition(Record Array, int left,int right) /分割函数，分割后轴值已到达正确位置分割函数，分割后轴值已到达正确位置Record TempRecord; /存放轴值的临时变量存放轴值的临时变量int i = left;/ i为左指针，为左指针，j为右指针为右指针int j = right; /将轴值存放在临时变量中将轴值存放在临时变量中TempRecord = Arrayj; /开始分割，开始分割
44、，i,j不断向中间移动，直到相遇不断向中间移动，直到相遇北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page while (i != j) /i指针右移，直到找到一个大于等于轴值的记录指针右移，直到找到一个大于等于轴值的记录while (Compare:lt(Arrayi, TempRecord) & (ji)i+; / 如果如果i,j未相遇就将逆序元素换到右边空闲位置未相遇就将逆序元素换到右边空闲位置if (i i) j-;/如果如果i,j未相遇就将逆序元素换到左边空闲位置未相遇就将逆序元素换到左边空闲位置if (ij)Arrayi = Arrayj;
45、i+;/i指针向右移动一步指针向右移动一步/把轴值回填到分界位置把轴值回填到分界位置i上上Arrayi = TempRecord;return i;/返回分界位置返回分界位置i 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n最差情况：最差情况：n时间代价：时间代价： (n2) n空间代价：空间代价： (n) n最佳情况：最佳情况：n时间代价：时间代价：(nlog n) n空间代价：空间代价：(log n) n平均情况：平均情况：n时间代价：时间代价：(nlog n) n空间代价：空间代价：(log n) 北京大学信息学院北京大学
46、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析（续）算法分析（续）n不稳定不稳定n优化：当快速排序的子数组小于某优化：当快速排序的子数组小于某个长度时，不继续递归，直接进行个长度时，不继续递归，直接进行插入排序。插入排序。n经验表明，最好的组合方式是当经验表明，最好的组合方式是当n（子数组的长度）小于等于子数组的长度）小于等于16时就时就使用插入排序使用插入排序 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 优化的快速排序优化的快速排序 #define THRESHOLD 16template class Impr
47、ovedQuickSorter:public Sorter /优化的快速排序类优化的快速排序类private:/选择轴值，返回轴值下标选择轴值，返回轴值下标int SelectPivot(int left, int right);/分割分割,返回轴值位置返回轴值位置int Partition(Record Array, int left, int right);void DoSort(Record Array,int left,int right); public:void Sort(Record Array,int left,int right); 北京大学信息学院北京大学信息学院 版版权所
48、有，转载或翻印必究权所有，转载或翻印必究 Page template void ImprovedQuickSorter:Sort(Record Array, int left,int right) /优化的快速排序，优化的快速排序，Array为待排序数组，为待排序数组，i,j分别分别/为数组两端为数组两端/先对序列进行递归排序先对序列进行递归排序DoSort(Array,left,right);/最后对整个序列进行一次直接插入排序最后对整个序列进行一次直接插入排序ImprovedInsertSorter insert_sorter;insert_sorter.Sort(Array,right-
49、left+1);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void ImprovedQuickSorter:DoSort(Record Array, int left,int right) /优化的快速排序，优化的快速排序，Array为待排序数组，为待排序数组，i,j分别为数组分别为数组/两端两端/ 如果序列中只有如果序列中只有0或或1个记录，就不用排序个记录，就不用排序 if (right THRESHOLD)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /选择轴值选择轴值i
50、nt pivot = SelectPivot(left, right);/ 将轴值放在数组末端将轴值放在数组末端swap(Array, pivot, right); / 对剩余的记录进行分割对剩余的记录进行分割pivot = Partition(Array, left, right);/对分割出的子序列进行递归快速排序对分割出的子序列进行递归快速排序/对轴值左右分别进行排序对轴值左右分别进行排序DoSort(Array, left, pivot-1); DoSort(Array, pivot+1, right); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必
51、究 Page 7.4.2 归并排序归并排序 n算法思想算法思想n简单地将原始序列划分为两个子简单地将原始序列划分为两个子序列序列n分别对每个子序列递归排序分别对每个子序列递归排序n最后将排好序的子序列合并为一最后将排好序的子序列合并为一个有序序列，即归并过程个有序序列，即归并过程 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 两路归并排序两路归并排序 template class TwoWayMergeSorter:public Sorter /两路归并
52、排序类两路归并排序类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 template void TwoWayMergeSorter:Sort(Record Array, Record TempArray,int left, int r
53、ight) /Array为待排序数组，为待排序数组，left，right分别为数组两端分别为数组两端/ 如果序列中只有如果序列中只有0或或1个记录，就不用排序个记录，就不用排序if (left right) /从中间划分为两个子序列从中间划分为两个子序列int middle=(left+right)/2;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /对左边一半进行递归对左边一半进行递归Sort(Array, TempArray,left,middle); /对右边一半进行递归对右边一半进行递归Sort(Array, TempArray,midd
54、le+1,right); / 进行归并进行归并Merge(Array, TempArray,left,right,middle); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 归并函数归并函数template void TwoWayMergeSorter:Merge(Record Array, Record TempArray,int left,int right,int middle) /归并过程归并过程 / 将数组暂存入临时数组将数组暂存入临时数组for (int j=left; j=right; j+) TempArrayj = Arra
55、yj;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page int index1=left;/左边子序列的起始位置左边子序列的起始位置int index2=middle+1;/右子序列起始位置右子序列起始位置int i=left;/从左开始归并从左开始归并while (index1 = middle)&(index2 = right)/取较小者插入合并数组中取较小者插入合并数组中if (Compare:le(TempArrayindex1, TempArrayindex2)Arrayi+ = TempArrayindex1+;北京大学信息学院北京大学信息
56、学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page else Arrayi+ = TempArrayindex2+;/处理剩余记录处理剩余记录while (index1 = middle)Arrayi+ = TempArrayindex1+;while (index2 = right)Arrayi+ = TempArrayindex2+; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n空间代价：空间代价：(n) n总时间代价：总时间代价：(nlog n) n不依赖于原始数组的输入情况，不依赖于原始数组的输入情况，最
57、大、最小以及平均时间代价均最大、最小以及平均时间代价均为为(nlog n)。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析（续）算法分析（续）n不稳定不稳定n优化：优化：n同优化的快速排序一样，对基本同优化的快速排序一样，对基本已排序序列直接插入排序已排序序列直接插入排序nR.Sedgewick优化：归并时从两优化：归并时从两端开始处理，向中间推进端开始处理，向中间推进北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 优化的归并排序优化的归并排序#define THRESHOLD 16temp
58、late class ImprovedTwoWayMergeSorter: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 /优化的两路归并排序，优化的两路归并排序
59、，Array为待排序数组，为待排序数组，left，right分别为数组两端分别为数组两端template void ImprovedTwoWayMergeSorter:Sort(Record Array,Record TempArray, int left, int right) DoSort(Array,TempArray,left,right);/最后对整个序列进行一次直接插入排序最后对整个序列进行一次直接插入排序ImprovedInsertSorter insert_sorter;insert_sorter.Sort(&Arrayleft,right-left+1);北京大学信息学院北京
60、大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void ImprovedTwoWayMergeSorter:DoSort(Record Array,Record TempArray, int left, int right) /如果序列长度大于阈值如果序列长度大于阈值(16最佳最佳)，跳出递归，跳出递归if (right THRESHOLD) int middle=(left+right)/2;/从中间划分从中间划分Sort(Array, TempArray ,left,middle);Sort(Array, TempArray ,middle+1
61、,right);Merge(Array, TempArray ,left,right,middle); else ImprovedInsertSorter insert_sorter; insert_sorter.Sort(&Arrayleft,right-left+1); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void ImprovedTwoWayMergeSorter:Merge(Record Array,Record TempArray,int left,int right,int middle) /归并过程归并过
62、程int index1,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 / 开始归并开始归并for (index1=left,index2=right,k
63、=left; k=right; k+)if (Compare:lt(TempArrayindex1, TempArrayindex2)Arrayk = TempArrayindex1+;else Arrayk = TempArrayindex2-; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.5 堆排序堆排序 n直接选择排序：直接从剩余记录直接选择排序：直接从剩余记录中线性查找最大记录中线性查找最大记录n堆排序：基于最大值堆来实现，堆排序：基于最大值堆来实现，效率更高效率更高北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有
64、，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 堆排序算法堆排序算法template class HeapSorter:public Sorter /堆排序类堆排序类public:void Sort(Record Array,int n); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void HeapSorter:Sort(Record Array, int
65、n) /堆排序，堆排序，Array为待排数组，为待排数组，n为数组长度为数组长度Record record;MaxHeap max_heap = MaxHeap(Array,n,n); /建堆建堆/ 依次找出剩余记录中的最大记录，即堆顶依次找出剩余记录中的最大记录，即堆顶for (int i=0; in; i+)max_heap.Removemax(record); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n建堆：建堆：(n) n删除堆顶删除堆顶:(log n) n一次建堆一次建堆 ,n次删除堆顶次删除堆顶n总时间代价为总时
66、间代价为(nlog n) n空间代价为空间代价为(1) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.6 分配排序和基数排序分配排序和基数排序 n不需要进行比较不需要进行比较n需要事先知道记录序列的一些具需要事先知道记录序列的一些具体情况体情况 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.6.1 桶式排序桶式排序 n事先知道序列中的记录都位于某事先知道序列中的记录都位于某个小区间段个小区间段0，m)内内 n将具有相同值的记录都分配到同将具有相同值的记录都分配到同一个桶中，然后依次按照编号从
67、一个桶中，然后依次按照编号从桶中取出记录，组成一个有序序桶中取出记录，组成一个有序序列列 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 桶式排序算法桶式排序算法template class BucketSorter:public Sorter /桶式排序类桶式排序类public:void Sort(Record Array,int n,int max);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /桶式排序，桶式排序，Array为待排序数组，数组长度为为待排序数组，数组长度为n,所所/有记录都位于
68、区间有记录都位于区间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;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /统计每
69、个取值出现的次数统计每个取值出现的次数 for (i=0;in;i+)countArrayi+; /统计小于等于统计小于等于i的元素个数的元素个数 for (i=1;i=0;i-) Array-countTempArrayi = TempArrayi;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n时间代价：时间代价：n统计计数时：统计计数时：(n+m) n输出有序序列时循环输出有序序列时循环n次次n总的时间代价为总的时间代价为(m+n) n适用于适用于m相对于相对于n很小的情况很小的情况北京大学信息学院北京大学信息学院 版版权所
70、有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析（续）算法分析（续）n空间代价：空间代价：nm个计数器，长度为个计数器，长度为n的临时数组，的临时数组，(m+n) n稳定稳定北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.6.2 基数排序基数排序 n桶式排序只适合桶式排序只适合m很小的情况很小的情况n当当m很大时，可以将一个记录的很大时，可以将一个记录的值即排序码拆分为多个部分来进值即排序码拆分为多个部分来进行比较行比较基数排序基数排序北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基数
71、排序基数排序n假设长度为假设长度为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称为最低排序码。称为最低排序码。北京大学信息学院北京大学信息学院 版版权
72、所有，转载或翻印必究权所有，转载或翻印必究 Page 例子例子n例如：如果我们要对例如：如果我们要对0到到9999之间的整之间的整数进行排序数进行排序n将四位数看作是由四个排序码决定，即将四位数看作是由四个排序码决定，即千、百、十、个位，其中千位为最高排千、百、十、个位，其中千位为最高排序码，个位为最低排序码。基数序码，个位为最低排序码。基数r=10。n可以按千、百、十、个位数字依次进行可以按千、百、十、个位数字依次进行4次桶式排序次桶式排序n4趟分配排序后，整个序列就排好序了。趟分配排序后，整个序列就排好序了。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必
73、究 Page 基数排序分为两类基数排序分为两类n高位优先法（高位优先法（MSD，Most Significant Digit first） n 低位优先法（低位优先法（LSD，Least Significant Digit first） 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 高位优先法（高位优先法（MSD，Most Significant Digit first）n先对高位先对高位kd-1进行桶式进行桶式排序，将序列分成若干排序，将序列分成若干个桶中个桶中n然后对每个桶再按次高位然后对每个桶再按次高位kd-2进行桶式排序，进行桶式排序，分
74、成更小的桶；分成更小的桶；n依次重复，直到对依次重复，直到对k0排序后，分成最小的桶，排序后，分成最小的桶，每个桶内含有相同的排序码每个桶内含有相同的排序码(kd-1，kd-2，k1 ，k0)；n最后将所有的桶依次连接在一起，成为一个有最后将所有的桶依次连接在一起，成为一个有序序列。序序列。n这是一个分、分、这是一个分、分、分、收的过程。、分、收的过程。北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 低位优先法（低位优先法（LSD，Least Significant Digit first）n从最低位从最低位k0开始排序；开始排序；n对于排好的序列
75、再用次低位对于排好的序列再用次低位k1排序；排序；n依次重复，直至对最高位依次重复，直至对最高位kd-1排好序排好序后，整个序列成为有序的。后，整个序列成为有序的。n这是一个分、收；分、收；这是一个分、收；分、收；分、；分、收的过程。收的过程。 n比较简单，计算机常用比较简单，计算机常用北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基数排序的实现基数排序的实现n
76、基于顺序存储基于顺序存储n基于链式存储基于链式存储北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基于顺序存储的基数排序基于顺序存储的基数排序n只讨论只讨论LSDn原始输入数组原始输入数组R的长度为的长度为nn基数为基数为rn排序码个数为排序码个数为d 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基于数组的基数排序
77、基于数组的基数排序template class RadixSorter:public Sorter /基数排序类基数排序类public:void Sort(Record Array,int n,int min,int max); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page template void RadixSorter:Sort(Record Array, int n,int d, int r) /n为数组长度，为数组长度，d为排序码数，为排序码数，r为基数为基数/临时数组临时数组Record *TempArray =new Recordn
78、;int* count= new intr;/计数器计数器int i,j,k;int Radix=1;/取取Arrayj的第的第i位排序码位排序码for (i=1; i=d; i+) / 分别对第分别对第i个排序码分配个排序码分配北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page for (j=0; jr; j+)/ 初始计数器均为初始计数器均为0countj = 0; for (j=0; jn; j+)/ 统计每个桶中的记录数统计每个桶中的记录数 /取取Arrayj的第的第i位排序码位排序码k=(Arrayj /Radix)%r;countk+;/相
79、应计数器加相应计数器加1/ 将将TempArray中的位置依次分配给中的位置依次分配给r个桶个桶for (j=1; j=0; j-) /取取Arrayj的第的第i位排序码位排序码k=(Arrayj /Radix)%r;/从第从第k个桶取出一个记录，计数器减个桶取出一个记录，计数器减1countk-;TempArraycountk = Arrayj; / 将临时数组中的内容复制到将临时数组中的内容复制到Array中中for (j=0; jn; j+)Arrayj = TempArrayj; Radix*=r; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 P
80、age 算法分析算法分析n空间代价：空间代价：n临时数组临时数组,nnr个计数器个计数器n(n+r) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析（续）算法分析（续）n时间代价时间代价n桶式排序：桶式排序：(m+n) nd次桶式排序次桶式排序n(d (n+r)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基于静态链的基数排序基于静态链的基数排序n将分配出来的子序列存放在将分配出来的子序列存放在r个个(静态链组织的静态链组织的)队列中队列中n链式存储避免了空间浪费情况链式存储避免了空间浪费情
81、况 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 静态队列定义静态队列定义 /结点类结点类class Nodepublic:int key;/结点的关键码值结点的关键码值int next; /下一个结点在数组中的下标下一个结点在数组中的下标;/静态队列类静态队列类class StaticQueue public:int head;int tail;北京大学信息学
82、院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 基于静态链的基数排序基于静态链的基数排序 template class LinkRadixSorter /基于静态链的基数排序类基于静态链的基数排序类private:void Distribute(Record* Array,int first,int i,int r, StaticQueue* queue);/分配过程分配过程void Collect(Record* Array, int& first, int i, int r, StaticQueue* queue);/收集过程收集过程void PrintAr
83、ray(Record* A, int first);/输出序列输出序列public:void Sort(Record* Array,int n, int d, int r);北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 静态链实现的基数排序静态链实现的基数排序template void LinkRadixSorter:Sort(Record* Array, int n, int d, int r) /n为数组长度，为数组长度，d为排序码个数，为排序码个数，r为基数为基数int first=0;/ first指向静态链中第一个记录指向静态链中第一个
84、记录StaticQueue *queue;/存放存放r个桶的静态队列个桶的静态队列queue = new StaticQueuer; / 建链，初始为建链，初始为next域指向下一个记录域指向下一个记录for (int i=0; in; i+)Arrayi.next = i+1;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Arrayn-1.next = -1;/链尾链尾next为空为空cout排序前：排序前： endl;PrintArray(Array, 0); /输出原始序列输出原始序列/对第对第j个排序码进行分配和收集，一共个排序码进行分配
85、和收集，一共d趟趟for (int j=0; jd; j+)Distribute(Array, first, j, r, queue);Collect(Array, first, j, r, queue);cout排序后：排序后： endl;PrintArray(Array, first);/输出排序后的结果输出排序后的结果delete queue;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 分配过程分配过程template void LinkRadixSorter:Distribute(Record* Array,int first,int
86、i,int r, StaticQueue* queue) /A中存放待排序记录，中存放待排序记录，first为静态链中的第一个记为静态链中的第一个记/录录,i为第为第i个排序码，个排序码，r为基数为基数 /初始化初始化r个队列个队列for (int j=0; jr; j+)queuej.head=-1; /对整个静态链进行分配对整个静态链进行分配while (first != -1)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page /取第取第i位排序码数字位排序码数字int k=Arrayfirst.key;for (int a=0;ai;a+)k=
87、 k/r;k=k%r; / 把把Arrayfirst分配到第分配到第k个子序列中个子序列中, / 如果子序列为空，如果子序列为空， / Arrayfirst就是第一个记录就是第一个记录if (queuek.head = -1)queuek.head = first; else/ 否则加到子序列的尾部否则加到子序列的尾部北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page Arrayqueuek.tail.next = first; /first为子序列的尾部为子序列的尾部queuek.tail = first;/继续分配下一个记录继续分配下一个记录fir
88、st = Arrayfirst.next; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 收集过程收集过程template void LinkRadixSorter:Collect(Record* Array, int& first, int i, int r, StaticQueue* queue) /A中存放待排序记录，中存放待排序记录，first为静态链中的第一为静态链中的第一个记个记/录，录，i为第为第i个排序码，个排序码，r为基数为基数int last, k=0;/已收集到的最后一个记录已收集到的最后一个记录 / 找到第一个非空队列找到
89、第一个非空队列while (queuek.head = -1) k+;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page first = queuek.head;last = queuek.tail;while (kr-1)/继续收集下一个非空队列继续收集下一个非空队列k+; /找到下一个非空队列找到下一个非空队列while (kr-1 & queuek.head=-1) k+; /将这个非空序列与上一个非空序列连接将这个非空序列与上一个非空序列连接起来起来if (queuek.head!= -1) 北京大学信息学院北京大学信息学院 版版权所有，转载或
90、翻印必究权所有，转载或翻印必究 Page Arraylast.next = queuek.head;/此时最后一个记录为该序列的尾部记录此时最后一个记录为该序列的尾部记录last = queuek.tail;Arraylast.next = -1; /收集完毕收集完毕北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 输出序列中所有内容输出序列中所有内容template void LinkRadixSorter:PrintArray(Record* Array, int first) /first为静态链为静态链Array中第一个记录的下标中第一个记录
91、的下标int tmp;/用来扫描整个链的指针用来扫描整个链的指针tmp = first;while (tmp != -1) cout Arraytmp.key ;/输出记录输出记录tmp = Arraytmp.next;cout n;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 算法分析算法分析n空间代价空间代价nn个记录空间个记录空间nr个子序列的头尾指针个子序列的头尾指针n(n + r) n时间代价时间代价n不需要移动记录本身，只需要修改记不需要移动记录本身，只需要修改记录的录的next指针指针 n(d(n+r) 北京大学信息学院北京大学信息
92、学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.7 各种排序算法的理论和实各种排序算法的理论和实验时间代价验时间代价 算法算法最大最大时间平均平均时间最小最小时间辅助空助空间代价代价稳定定性性直接插入排直接插入排序序(n2)(n2)(n)(1)稳定定二分法插入二分法插入排序排序(n2)(n2)(nlog n)(1)稳定定冒泡排序冒泡排序(n2)(n2)(n2)(1)稳定定改改进的冒泡的冒泡排序排序(n2)(n2)(n)(1)稳定定选择排序排序(n2)(n2)(n2)(1)不不稳定定北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page
93、 算法算法最大最大时间平均平均时间最小最小时间辅助空助空间代价代价稳定定性性Shell排序排序(3)(n3/2)(n3/2)(n3/2)(1)不不稳定定快速排序快速排序(n2)(nlog n)(nlog n)(log n)不不稳定定归并排序并排序(nlog n)(nlog n)(nlog n)(n)稳定定堆排序堆排序(nlog n)(nlog n)(nlog n)(1)不不稳定定桶式排序桶式排序(n+m)(n+m)(n+m)(n+m)稳定定基数排序基数排序(d(n+r)(d(n+r)(d(n+r)(n+r)稳定定北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究
94、 Page 小结小结nn n很小或基本有序时插入排序比很小或基本有序时插入排序比较有效较有效n综合性能快速排序最佳综合性能快速排序最佳北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 测试环境测试环境n硬件环境：硬件环境：nCPU：Intel P4 2.4G n内存：内存：512M DDRn软件环境：软件环境：nwindows xpnVisual C+ 6.0北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 随机生成待排序数组随机生成待排序数组/设置随机种子设置随机种子inline void Randomi
95、ze() srand(1); / 返回一个返回一个0到到n之间的随机整数值之间的随机整数值inline int Random(int n) return rand() % (n); /产生随机数组产生随机数组ELEM *sortarray =new ELEM1000000;for(int i=0;i1000000;i+)sortarrayi=Random(32003); 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 时间测试时间测试#include /* Clock ticks macro - ANSI version */#define CLO
96、CKS_PER_SEC 1000clock_t tstart = 0; / Time at beginning / Initialize the program timer void Settime() tstart = clock(); / The elapsed time since last Settime() double Gettime() return (double)(double)clock() - (double)tstart)/ (double)CLOCKS_PER_SEC; 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序
97、的时间测试排序的时间测试 Settime(); for (i=0; iARRAYSIZE; i+=listsize) sort(&arrayi, listsize); print(&arrayi, listsize); cout Sort with list size listsize , array size ARRAYSIZE , and threshold THRESHOLD : Gettime() secondsn;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数数组规模模10010K1M10K正序正序10K逆序逆序直接插入排序直接插入排
98、序0.000175 1.7266_0.000313.44187优化插入排序化插入排序0.000092 0.8847_0.000311.76157二分插入排序二分插入排序0.000036 0.1434_0.004530.28297冒泡排序冒泡排序0.000271 2.7844_1.746413.47484优化冒泡排序化冒泡排序0.000269 2.7848_0.000323.44063选择排序排序0.000180 1.7199_1.725161.72812Shell排序排序(2)0.000072 0.01664.5780.004840.00781Shell排序排序(3)0.000055 0.01
99、534.1250.001210.00687北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 数数组规模模10010K1M10K正序正序10K逆序逆序快速排序快速排序0.0000420.00681.0010.005470.00547优化快速排序化快速排序 0.0000310.00570.8560.004080.00409归并排序并排序0.0000450.00701.1050.006250.00546优化化归并排序并排序 0.0000330.00570.9340.005310.00531堆排序堆排序0.0000420.00751.5620.006720.
100、00688基数排序基数排序/20.0002940.02943.0310.029370.02922基数排序基数排序/40.0001450.01471.5150.014690.01469基数排序基数排序/80.0000950.00920.9530.009220.00921北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7.8 排序问题的下限排序问题的下限 n排序问题的时间代价在排序问题的时间代价在 (n)(起码起码I/O 时间时间) 到到O(n log n) (平均平均, 最差最差情况情况)之间之间n基于比较的排序算法的下限也为基于比较的排序算法的下限
101、也为(n log n) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 用判定树模拟基于比较的排序用判定树模拟基于比较的排序 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 判定树判定树( Dicision Tree )n判定树中叶结点的最大深度就是判定树中叶结点的最大深度就是排序算法在最差情况下需要的最排序算法在最差情况下需要的最大比较次数；大比较次数；n叶结点的最小深度就是最佳情况叶结点的最小深度就是最佳情况下的最小比较次数下的最小比较次数 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必
102、究权所有，转载或翻印必究 Page 基于比较的排序的下限基于比较的排序的下限n对对n个记录，共有个记录，共有n!个叶结点个叶结点 n判定树的深度为判定树的深度为log(n!) n在最差情况下需要在最差情况下需要log(n!)次比较，次比较，即即(n logn) n在最差情况下任何基于比较的排序在最差情况下任何基于比较的排序算法都需要算法都需要(nlog n)次比较次比较 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 排序问题的时间代价排序问题的时间代价n在最差情况下任何基于比较的排序算法在最差情况下任何基于比较的排序算法都需要都需要(nlog n)次比较，因此最差情况次比较，因此最差情况时间代价就是时间代价就是(n log n) 。n那么排序问题本身需要的运行时间也就那么排序问题本身需要的运行时间也就是是(n log n)。 n所有排序算法都需要所有排序算法都需要(n log n)的运行的运行时间，因此可以推导出排序问题的时间时间，因此可以推导出排序问题的时间代价为代价为 (n log n)。 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page END!
