第10章排序(上课用)讲述

1、单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级1数 据 结 构主讲人：主讲人： 张立震张立震e-mail: 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级2打扑克例例 子子单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级3世界杯比赛排名阿根廷阿根廷法国法国阿根廷阿根廷意大利意大

2、利法国法国意大利意大利法国法国英国英国中国中国巴西巴西巴西巴西阿根廷阿根廷西班牙西班牙葡萄牙葡萄牙阿根廷阿根廷例例 子子单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级4数据结构期末成绩排名学号姓名成绩1110810113刘德华981110810221陈鑫961110820109刘亦菲911110820104黄渤871110820116顼晓宇83例例 子子单击此处编辑母版标题样式单击此处编辑母版标题样式单击此处编辑母版文本样式单击此处编辑母版文本样式第二级第二级第三级第三级第四级第四级第五

3、级第五级510.1 概述概述10.2 插入排序插入排序 (直接插入、折半插入、希尔排序直接插入、折半插入、希尔排序)10.3 交换排序交换排序 (冒泡排序、快速排序冒泡排序、快速排序)10.4 选择排序选择排序 (简单选择、树形选择、堆排序简单选择、树形选择、堆排序)10.5 归并排序归并排序 10.6 基数排序基数排序10.7 各种排序小结各种排序小结单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级6：整理文件中的记录，使之按：整理文件中的记录，使之按关键字关键字递增递增 (或递减或递减

4、) 次序排列起来。次序排列起来。：以数据对象的多个属性域中的一个为：以数据对象的多个属性域中的一个为 排序依据，该属性域即为关键字。排序依据，该属性域即为关键字。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级7内部排序内部排序 外部排序外部排序 将欲处理的数据整个存放到内部存将欲处理的数据整个存放到内部存储器中排序，数据可被随机存取储器中排序，数据可被随机存取 交换式排序交换式排序 选择式排序选择式排序 插入式排序插入式排序 由于排序期间数据太多，需要借助外部由于排序期间数据太多，需要借

5、助外部的辅助存储器，不断在内、外存只见移的辅助存储器，不断在内、外存只见移动的排序，数据不可随机存取动的排序，数据不可随机存取 排序的分类排序的分类归并排序归并排序 基数排序基数排序 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级8排序算法衡量标准排序算法衡量标准稳定性稳定性 不稳定性不稳定性 排序过后能使值相同的数据保持排序过后能使值相同的数据保持原顺序中的相对位置原顺序中的相对位置 排序过后不能使值相同的数据排序过后不能使值相同的数据保持原顺序中的相对位置保持原顺序中的相对位置 49

6、325649272732494956u时间复杂度时间复杂度（最好情况和最坏情况）（最好情况和最坏情况）u空间复杂度空间复杂度u稳定性稳定性排序的时间开销可用算法执行中的数排序的时间开销可用算法执行中的数据据比较次数比较次数与数据与数据移动次数移动次数来衡量。来衡量。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级9 本教材定义的待排数据表类型本教材定义的待排数据表类型 typedef struct KeyType key; /关键字项关键字项 InfoType otherinfo; /其他

7、数据项其他数据项 RedType; typedef struct RedType rMAXSIZE+1; /r0闲置或作哨兵闲置或作哨兵 int length; SqList;单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级10 直接插入排序直接插入排序 (Insert Sort) 折半插入排序折半插入排序 (Binary Insert Sort) 2-路插入排序（略）路插入排序（略） 表插入排序（略）表插入排序（略） 希尔排序希尔排序 (Shell Sort)基本思想基本思想 每步将一个

8、待排序的对象，按其排序码大小，每步将一个待排序的对象，按其排序码大小， 插入插入到前面到前面已经排好序已经排好序的一组对象的适当位置上，的一组对象的适当位置上，直到对象全部插入为止。直到对象全部插入为止。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级11基本思想基本思想：顺序地把待排序的数据元素按其值的大小插顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。入到已排序数据元素子集合的适当位置。有序序列有序序列无序序列无序序列1. 直接插入排序直接插入排序(Inse

9、rt Sort)12578630941256783094单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级12基本思想基本思想：顺序地把待排序的数据元素按其值的大小插顺序地把待排序的数据元素按其值的大小插入到已排序数据元素子集合的适当位置。入到已排序数据元素子集合的适当位置。1. 直接插入排序直接插入排序(Insert Sort)p 当插入第当插入第i (i 1) 个对象时，前面的个对象时，前面的r1, , ri-1已经已经排好序。这时，用排好序。这时，用ri的排序码与的排序码与ri-1,

10、ri-2, 的排序的排序码顺序进行比较，找到插入位置即将码顺序进行比较，找到插入位置即将Vi插入，原来位插入，原来位置上的对象向后顺移。置上的对象向后顺移。p 子集合的数据元素个数从只有一个数据元素开始逐次子集合的数据元素个数从只有一个数据元素开始逐次增大。增大。p 当子集合大小最终和集合大小相同时排序完毕。当子集合大小最终和集合大小相同时排序完毕。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级1364 7896468989646464直接插入排序直接插入排序 6478962458962

11、457624572456567246489578924初始序列初始序列:第第1趟排序趟排序:第第2趟排序趟排序:第第3趟排序趟排序:第第4趟排序趟排序:第第5趟排序趟排序:jjjj6Temp 6单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级14 直接插入排序的算法直接插入排序的算法 (p265算法算法10.1) void InsertSort(SqList &L) int i, j; for ( i=2; i=L.length; +i ) if ( LT(L.ri.key, L.

12、ri-1.key) ) / 时，需将时，需将L.ri插入有序子表插入有序子表 L.r0 = L.ri; / L.r0为监视哨为监视哨 for ( j=i-1; LT(L.r0.key,L.rj.key); -j ) L.rj+1 = L.rj; / 记录后移记录后移 L.rj+1 = L.r0; / 插入到正确位置插入到正确位置 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级15最坏最坏情况下情况下 最好最好情况下情况下比较次数：比较次数：n-1移动次数：移动次数：0算法分析算法分析比较

13、次数：比较次数：移动次数：移动次数：2) 1)(2(2- -+ += = = =nnini2) 1)(4(1- -+ += =+ + nnin2= =i）（正序）（正序） （逆序）（逆序） 直接插入排序的时间复杂度为直接插入排序的时间复杂度为O(n2)。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级16空间性能：空间性能：需要一个记录的辅助空间（监视哨）。需要一个记录的辅助空间（监视哨）。稳定性：稳定性：直接插入排序算法是一种直接插入排序算法是一种稳定稳定的排序算法。的排序算法。特点：特

14、点：简单、容易实现，适用于待排序记录简单、容易实现，适用于待排序记录基本有基本有 序序或待排序记录或待排序记录较小较小时。时。算法分析算法分析单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级17246457624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 62. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入位置时，使用折半查找算法。：在查找插入位置时，使用折半查找算法。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此

15、处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级18642. 折半插入折半插入(Binary Insert Sort) 基本思想基本思想：在查找插入位置时，使用折半查找算法。：在查找插入位置时，使用折半查找算法。57624576489896第第2趟排序趟排序:第第3趟排序趟排序:temp 689647low6mhigh单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级19void BInsertSort ( SqList &L ) i

16、nt i, j, high, low, m; for (i=2; i=L.length; +i) L.r0 = L.ri; / 将将L.ri暂存到暂存到L.r0 low = 1; high = i-1; while (low=high+1; -j) L.rj+1 = L.rj; / 记录后移记录后移 L.rhigh+1 = L.r0; / 插入插入 / BInsertSort折半插入排序算法折半插入排序算法单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级20时间性能分析：时间性能分析： 移

17、动次数与直接插入排序相同移动次数与直接插入排序相同 比较次数与初始顺序无关，只依赖于记录个数比较次数与初始顺序无关，只依赖于记录个数 插入每个记录需要插入每个记录需要log2 i次比较次比较 时间复杂度为时间复杂度为O(n2)。空间代价空间代价: 与直接插入排序相同与直接插入排序相同稳定性稳定性: 稳定稳定算法分析算法分析单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级21 基本思想基本思想：把待排序的数据元素把待排序的数据元素分成若干个小组分成若干个小组，对，对同一小组内的数据元素用直接

18、插入法排序；同一小组内的数据元素用直接插入法排序；小组的个数小组的个数逐次缩小逐次缩小；当完成了所有数据元素都在一个组内的排序；当完成了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称作缩小增量排序。后排序过程结束。希尔排序又称作缩小增量排序。3. 希尔排序希尔排序(Shell Sort) 开始时开始时 gap（间隔值）（间隔值） 的值较大，子序列中的对象较的值较大，子序列中的对象较少，排序速度较快；随着排序进展，少，排序速度较快；随着排序进展，gap 值逐渐变小，值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本

19、有序，所以排序速度仍然很快。大多数对象已基本有序，所以排序速度仍然很快。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级22希尔排序过程希尔排序过程6565 343425258787 121238385656 464614147777 929223235656656514142525777787873838232356563434141477771212232365654646252587879292383865657777121234345656121214146565343423237

20、77746462525878792923838121214142323252534343838464656566565777787879292结果序列结果序列gap=6gap=3gap=1单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级23void ShellInsert(SqList &L, int gap) / 对顺序表对顺序表L作一趟希尔插入排序。本算法对算法作一趟希尔插入排序。本算法对算法10.1作了以下修改：作了以下修改： / 1. 前后记录位置的增量是前后记录位置的增量

21、是gap，而不是，而不是1； / 2. r0只是暂存单元，不是哨兵。当只是暂存单元，不是哨兵。当j=0时，插入位置已找到。时，插入位置已找到。 int i, j; for (i=gap+1; i0 & LT(L.r0.key, L.rj.key); j-=gap) L.rj+gap = L.rj; / 记录后移，查找插入位置记录后移，查找插入位置 L.rj+gap = L.r0; / 插入插入 / ShellInsert希尔排序的算法希尔排序的算法 (算法算法10.4)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三

22、级第三级 第四级第四级 第五级第五级24void ShellSort ( SqList &L, int dlta, int t ) / 按增量序列按增量序列dlta0.t-1对顺序表对顺序表L作希尔排序。作希尔排序。 for (int k=0; k= 2; -i ) for ( j=1; j L. rj+1. key ) ElemType temp=L.rj; / 交换交换 L.rj=L.rj+1; L.rj+1=temp; 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级30问题

23、：刚才的改进算法是否已经最优问题：刚才的改进算法是否已经最优?冒泡排序的冒泡排序的改进改进算法算法1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 如何解决呢？如何解决呢？单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级31 冒泡排序的冒泡排序的改进改进算法算法void BubbleSort ( SqList &L ) for (i=n, Change =TRUE; i = 2 &

24、Change; -i ) Change = FALSE; for ( j=1; j L. rj+1. key ) ElemType temp=L.rj; L.rj=L.rj+1; L.rj+1=temp; Change=TRUE; 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级32最坏情况（逆序）：最坏情况（逆序）：最好情况（正序）：最好情况（正序）：比较次数：比较次数：n-1移动次数：移动次数：0 比较次数：比较次数：移动次数：移动次数：2) 1(1- -= = = =nn(n-i)n

25、-1i2) 1(1- -= = = =n3n3(n-i)n-1i算法分析算法分析 n 时间复杂度为时间复杂度为O(n2)n 稳定性：稳定性：稳定稳定单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级33基本思想基本思想：任取待排序对象序列中的某个对象（例如取任取待排序对象序列中的某个对象（例如取第一个对象）作为第一个对象）作为枢轴枢轴(pivot)，按照该对象的关键字大小，按照该对象的关键字大小，将整个对象序列划分为，将整个对象序列划分为左右两个子序列左右两个子序列：2. 快速排序快速排序(

26、Quick Sort)u左侧左侧子序列中所有对象的关键字都子序列中所有对象的关键字都小于小于枢轴对象的关枢轴对象的关键字。键字。u右侧右侧子序列中所有对象的关键字都子序列中所有对象的关键字都大于或等于大于或等于枢轴对枢轴对象的关键字。象的关键字。枢轴对象则排在这两个子序列中间枢轴对象则排在这两个子序列中间(这也是该对象最终应安这也是该对象最终应安放的位置放的位置)。然后分别对这两个子序列重复施行上述方法，。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。直到所有的对象都排在相应位置上为止。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击

27、此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级34一趟快速排序的具体过程一趟快速排序的具体过程49 38 65 97 76 13 27 49pivot=49lowhigh27low65high13low97highhigh49第一趟结果：第一趟结果： 27 38 13 49 76 97 65 49 小于小于49大于等于大于等于49单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级35快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqL

28、ist &L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并的记录，枢轴记录到位，并返回其所在返回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，此时在它之前（后）的记录均不大（小）于它 */ / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级36快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &L, int low

29、, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录的记录，枢轴记录到位，并返回其所在到位，并返回其所在 的位置，此时在它之前（后）的记的位置，此时在它之前（后）的记录均不大（小）于它录均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第

30、四级第四级 第五级第五级37快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并返的记录，枢轴记录到位，并返回其所在回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，此时在它之前（后）的记录均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 whil

31、e ( low high ) / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级38快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并返的记录，枢轴记录到位，并返回其所在回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，此时在它之前（后）的记录均不大（小）于它 */ L. r

32、0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 while ( low high ) L. rlow=L. r0; / 枢轴记录到位枢轴记录到位 return low; / 返回枢轴位置返回枢轴位置 / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级39快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &

33、amp;L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并返回其所在的记录，枢轴记录到位，并返回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，此时在它之前（后）的记录均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 while ( low high ) while ( low=pivotkey ) -high; L. rlow=L. r0;

34、 / 枢轴记录到位枢轴记录到位 return low; / 返回枢轴位置返回枢轴位置 / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级40快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并返回其所在的记录，枢轴记录到位，并返回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，

35、此时在它之前（后）的记录均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录 int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 while ( low high ) while ( low=pivotkey ) -high; L. rlow = L. rhigh; / 将比枢轴记录小的记录移到低端将比枢轴记录小的记录移到低端 L. rlow=L. r0; / 枢轴记录到位枢轴记录到位 return low; / 返回枢轴位置返回枢轴位置 / Partition 单击此处编辑母版标题样式单击此

36、处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级41快速排序每一趟的划分快速排序每一趟的划分 int Partition ( SqList &L, int low, int high ) /* 交换顺序表交换顺序表L中子表中子表r low high 的记录，枢轴记录到位，并返回其所在的记录，枢轴记录到位，并返回其所在 的位置，此时在它之前（后）的记录均不大（小）于它的位置，此时在它之前（后）的记录均不大（小）于它 */ L. r0=L. rlow; / 用子表的第一个记录作枢轴记录用子表的第一个记录作枢轴记录

37、int pivotkey = L. rlow. key; / 枢轴记录关键字枢轴记录关键字 while ( low high ) while ( low=pivotkey ) -high; L. rlow = L. rhigh; / 将比枢轴记录小的记录移到低端将比枢轴记录小的记录移到低端 while ( low high & L. rlow. key = pivotkey ) +low; L.rhigh = L.rlow; / 将比枢轴记录大的记录移到高端将比枢轴记录大的记录移到高端 L. rlow=L. r0; / 枢轴记录到位枢轴记录到位 return low; / 返回枢轴位置

38、返回枢轴位置 / Partition 单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级42快速排序算法快速排序算法void QSort ( SqList &L, int low, int high ) / 对顺序表对顺序表L中的子序列中的子序列L. rlowhigh作快速排序作快速排序 if ( low high ) / 长度大于长度大于1 pivotloc=Partition (L, low, high); / 将将L.rlow.high一分为二一分为二 QSort ( L, l

39、ow, pivotloc-1 ); / 对低子表递归排序对低子表递归排序 QSort(L,pivotloc+1,high); / 对高子表递归排序对高子表递归排序 / QSort单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级43算法分析算法分析n最理想的情况：每次划分对一个对象定位后，该对象最理想的情况：每次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度相同。的左侧子序列与右侧子序列的长度相同。n就就平均时间平均时间而言，快速排序是而言，快速排序是最好最好的一种内部排序方的一

40、种内部排序方法。平均计算时间是法。平均计算时间是O(nlog2n)n最坏情况：初始关键字有序或基本有序。此时快速排最坏情况：初始关键字有序或基本有序。此时快速排序蜕化为冒泡排序，序蜕化为冒泡排序，时间复杂度时间复杂度为为O(n2)。占用附加存。占用附加存储储(即栈即栈)将达到将达到O(n)。n快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。n对于对于 n 较大的平均情况而言，快速排序是较大的平均情况而言，快速排序是“快速快速”的，的，但是当但是当 n 很小时，这种排序方法往往比其它简单排序很小时，这种排序方法往往比其它简单排序方法还要慢。方法还要慢。单击此处编辑母版标题样式单击

41、此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级44 简单选择排序简单选择排序 (Simple Selection Sort) 树形选择排序树形选择排序 (Tree Selection Sort) 堆排序堆排序 (Heap Sort)基本思想基本思想 每一趟每一趟 (例如第例如第 i 趟趟, i = 1, , n-1) 在后面在后面 n-i +1个待个待排序记录中选出排序码最小的记录排序记录中选出排序码最小的记录, 作为有序序列中的作为有序序列中的第第 i 个记录。待到第个记录。待到第n-1 趟作完趟作完, 待排序记

42、录只剩下待排序记录只剩下1个个,就不用再选了。就不用再选了。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级45基本思想基本思想：i 从从 1 开始，直到开始，直到 n-1，进行，进行 n-1 趟排序。第趟排序。第 i 趟的排序过程为：趟的排序过程为： 在一组对象在一组对象 rirn ( i = 1, 2, , n-1) 中选择具有最小关键字的对象，并和第中选择具有最小关键字的对象，并和第 i 个对象进行交个对象进行交换。换。1. 简单选择排序简单选择排序(Simple Selection

43、 Sort)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级46一趟简单选择排序的过程一趟简单选择排序的过程149238365497576613727849ki=1jkjjjjkjjk1349单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级47149238365497576613727849i=kjjjjjj1349k k2一趟简单选择排序的过程一趟简单选择排序的过程单击此处编辑母版标

44、题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级48void SelectSort ( SqList & L) for ( int i = 1; i L.length; i+ ) k= SelectMinKey( L, i ); if (i!=k) ElemType temp=L.ri; L.ri=L.rk; L.rk=temp; int SelectMinKey (SqList & L, int i ) int m = i; for (j = i+1; j =L.length; j+) i

45、f (L.rj. key L.rm. key) m = j; /当前具最小关键码的对象当前具最小关键码的对象 return m;简单选择排序的算法简单选择排序的算法单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级49最坏情况：最坏情况：算法分析算法分析移动次数：移动次数：最好情况：最好情况：比较次数：比较次数：)() 1(21211nOnninni= =- -= =- - - -= =）（l 时间复杂度为时间复杂度为O(n2)。l 稳定性：稳定性：不稳定不稳定 为什么？为什么？0次次3(n

46、-1)次次单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级50世界杯比赛排名巴西巴西法国法国巴西巴西意大利意大利法国法国意大利意大利法国法国英国英国中国中国巴西巴西巴西巴西阿根廷阿根廷西班牙西班牙葡萄牙葡萄牙阿根廷阿根廷8个国家参加世界杯，个国家参加世界杯，需要多少次比赛得出冠军？需要多少次比赛得出冠军？单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级51树形选择排序又称为锦标赛排序。

47、树形选择排序又称为锦标赛排序。基本思想基本思想：与体育比赛时的淘汰赛类似。首先取得与体育比赛时的淘汰赛类似。首先取得 n 个个对象的关键码，进行对象的关键码，进行两两比较两两比较，得到，得到 n/2 个比较的个比较的优胜优胜者者(关键码小者关键码小者)，作为第一步比较的结果保留下来。然后，作为第一步比较的结果保留下来。然后对这对这 n/2 个对象再进行关键码的两两比较，个对象再进行关键码的两两比较，如此重，如此重复，直到选出一个关键码最小的对象。复，直到选出一个关键码最小的对象。2. 树形选择排序树形选择排序(TreeSelection Sort)单击此处编辑母版标题样式单击此处编辑母版标题样

48、式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级52133813973865493876131327652749单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级5313974938761365274938133865132727382738657627单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级54279749387613

49、6527493827386576271338384938657649单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级55p锦标赛排序构成的树是锦标赛排序构成的树是满的完全二叉树满的完全二叉树，其深度为，其深度为 log2(2n-1)取上整，其中取上整，其中 n 为待排序元素个数。为待排序元素个数。p除第一次选择具有最小关键字的对象需要进行除第一次选择具有最小关键字的对象需要进行 n-1 次次关键字比较外，重构胜者树选择具有次小、再次小关关键字比较外，重构胜者树选择具有次小、再次小关键字对象

50、所需的关键字比较次数均为键字对象所需的关键字比较次数均为 O(log2n)。总关总关键字比较次数为键字比较次数为O(nlog2n)。p对象的移动次数不超过关键字的比较次数，所以锦标对象的移动次数不超过关键字的比较次数，所以锦标赛排序赛排序总的时间复杂度总的时间复杂度为为O(nlog2n)。p这种排序方法虽然减少了许多排序时间，但是这种排序方法虽然减少了许多排序时间，但是使用了使用了较多的附加存储较多的附加存储。p锦标赛排序是一个锦标赛排序是一个稳定稳定的排序方法。的排序方法。算法分析算法分析单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二

51、级第二级 第三级第三级 第四级第四级 第五级第五级563. 堆排序堆排序(Heap Sort)堆定义：堆定义：n 个元素的序列个元素的序列 k1, k2, , kn 当且仅当当且仅当满足下列关系时，称之为满足下列关系时，称之为堆堆。 kik2i kik2i ki k2i+1 ki k2i+1其中，其中，i = 1, 2, , n/2.前者称为前者称为最小堆最小堆，后者称为，后者称为最大堆最大堆。或或单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级57最小堆与最大堆举例最小堆与最大堆举例96

52、83273811091236248547913053最大堆最大堆最小堆最小堆单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级58基本思想基本思想：在输出堆顶的最小值之后，使得剩余在输出堆顶的最小值之后，使得剩余n-1个元个元素的序列重又建成一个堆，则得到素的序列重又建成一个堆，则得到n个元素中的次小值。个元素中的次小值。反复执行，反复执行，直到直到得到一个有序序列。得到一个有序序列。堆排序分为两个步骤：堆排序分为两个步骤：u 根据初始输入数据形成初始堆；根据初始输入数据形成初始堆；u 通过

53、一系列的对象交换和重新调整堆进行排序。通过一系列的对象交换和重新调整堆进行排序。3. 堆排序堆排序(Heap Sort)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级59关键问题：关键问题：如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆? (1) 如何调整余下的元素成为一个新堆如何调整余下的元素成为一个新堆? 3. 堆排序堆排序(Heap Sort)单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第

54、四级第四级 第五级第五级60堆调整过程堆调整过程1338277697654949rc=13单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级61123456136542堆调整堆调整单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级62123456136542堆调整堆调整单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第

55、三级 第四级第四级 第五级第五级63123456136542堆调整堆调整单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级64123456136542堆调整堆调整单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级65123456136542堆调整堆调整单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级

56、 第五级第五级66123456136542建立初始的最大堆建立初始的最大堆单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级67123456136542建立初始的最大堆建立初始的最大堆单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级68u最大堆的第一个对象最大堆的第一个对象r1具有最大的关键字，将具有最大的关键字，将r1与与rn对调，把具有最大关键字的对象交换到最后，对调，把具有最大关键

57、字的对象交换到最后，再对前面的再对前面的n-1个对象，使用堆的调整算法个对象，使用堆的调整算法HeapAdjust(1, n-1)，重新建立最大堆。结果具有次，重新建立最大堆。结果具有次最大关键字的对象又上浮到堆顶，即最大关键字的对象又上浮到堆顶，即r1位置。位置。u再对调再对调r1和和rn-1，调用，调用HeapAdjust (1, n-2)，对前，对前n-2个对象重新调整。个对象重新调整。u如此反复执行，最后得到全部排序好的对象序列。如此反复执行，最后得到全部排序好的对象序列。这个算法即堆排序算法。这个算法即堆排序算法。utypedef SqList HeapType; /顺序存储方式顺序

58、存储方式基于初始堆进行堆排序基于初始堆进行堆排序单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级69void HeapAdjust(HeapType &H, int s, int m) /调整调整H.rs的关键字，使的关键字，使H.rsm成为一个大顶堆成为一个大顶堆 ElemType rc=H.rs; for (int j=2*s; j=m; j*=2) /沿较大的孩子结点向下筛选沿较大的孩子结点向下筛选 if (j0; -i) / 把把H.r1.H.length建成大顶堆建成大顶

59、堆 HeapAdjust ( H, i, H.length ); for (i=H.length; i1; -i) temp=H.ri; H.ri=H.r1; H.r1=temp; /* 将堆顶记录和当前未经排序子序列将堆顶记录和当前未经排序子序列Hr1.i中中 最后一个记录相互交换最后一个记录相互交换 */ HeapAdjust (H, 1, i-1); / 将将H.r1.i-1 重新调整为大顶堆重新调整为大顶堆 / HeapSort堆排序算法堆排序算法单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级

60、 第五级第五级71算法分析算法分析p适宜记录较多的文件适宜记录较多的文件p在最坏的情况下，时间复杂度为在最坏的情况下，时间复杂度为O(nlog2n)p堆排序是一个堆排序是一个不稳定不稳定的排序方法。的排序方法。单击此处编辑母版标题样式单击此处编辑母版标题样式 单击此处编辑母版文本样式单击此处编辑母版文本样式 第二级第二级 第三级第三级 第四级第四级 第五级第五级72基本思想基本思想 将一个具有将一个具有n个待排序记录的序列看成是个待排序记录的序列看成是 n 个长度个长度为为 1 的有序序列，然后进行的有序序列，然后进行两两归并两两归并，得到，得到 n/2 个长度个长度为为 2 的有序序列，再进行两两归并，得到的有序序列，再进行两两归并，得到 n/4 个长度为个长度为 4 的有序序列，的有序序列，直至得到一个长度为，直至得到一个长度为 n 的有序序的有序序列