《数据结构》课程教学资源（PPT课件）第八章 排序

第8章排序8.1排序的基本概念8.2插入排序8.3选择排序8.4交换排序

第8章 排序 8.1 排序的基本概念 8.2 插入排序 8.3 选择排序 8.4 交换排序

本章主要知识点：·排序的基本概念和衡量排序算法优劣的标准其中衡量标准有算法的时间复杂度、空间复杂度和稳定性，直接插入排序，希尔排序直接选择排序，堆排序冒泡排序，快速排序

本章主要知识点： ● 排序的基本概念和衡量排序算法优劣的标准， 其中衡量标准有算法的时间复杂度、空间复杂 度和稳定性 ● 直接插入排序，希尔排序 ● 直接选择排序，堆排序 ● 冒泡排序，快速排序

8.1排序的基本概念1.排序是对数据元素序列建立某种有序排列的过程2.排序的目的：便于查找。3.关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。关键字分主关键字和次关键字两种。对要排序的数据元素集合来说，如果关键字满足数据元素值不同时该关键字的值也一定不同，这样的关键字称为主关键字。不满足主关键字定义的关键字称为次关键字

8.1排序的基本概念 1.排序是对数据元素序列建立某种有序排列的过程。 2.排序的目的：便于查找。 3.关键字是要排序的数据元素集合中的一个域，排序是以 关键字为基准进行的。 关键字分主关键字和次关键字两种。对要排序的数据元素 集合来说，如果关键字满足数据元素值不同时该关键字的值也 一定不同，这样的关键字称为主关键字。不满足主关键字定义 的关键字称为次关键字

学生成绩表序号学号姓名数学英语语文物理0100470.084. 078. 077. 0Wang Yun1100275. 088.092. 085. 0Zhang Pen2101290. 084. 066. 080.0Li Cheng3100895. 077. 080.084. 3Chen Hong.::.................1022n-190. 095. 088. 0100.0Chu San

学生成绩表 序号 学号 姓名 数学 语文 物理 英语 0 1004 Wang Yun 84.0 70.0 78.0 77.0 1 1002 Zhang Pen 75.0 88.0 92.0 85.0 2 1012 Li Cheng 90.0 84.0 66.0 80.0 3 1008 Chen Hong 80.0 95.0 77.0 84.3 n-1 1022 Chu San 90.0 95.0 88.0 100.0 . . . . . .

4.排序的种类：分为内部排序和外部排序两大类若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则称为外部排序注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。5.排序算法好坏的衡量标准(1)时间复杂度它主要是分析记录关键字的比较次数和记录的移动次数。算法中使用的内存辅助空间的多少。(2）空间复杂度(3）稳定性若两个记录A和B的关键字值相等，但排序后AB的先后次序保持不变，则称这种排序算法是稳定的

4.排序的种类：分为内部排序和外部排序两大类。 若待排序记录都在内存中，称为内部排序；若待排序记 录一部分在内存，一部分在外存，则称为外部排序。 注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外 存，显然外部排序要复杂得多。 5.排序算法好坏的衡量标准： (1)时间复杂度—— 它主要是分析记录关键字的比较次数和记录 的移动次数。 (2)空间复杂度——算法中使用的内存辅助空间的多少。 (3)稳定性——若两个记录A和B的关键字值相等，但排序后A、 B的先后次序保持不变，则称这种排序算法是稳定的

8.2插入排序插入排序的基本思想是：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止简言之，边插入边排序，保证子序列中随时都是排好序的。常用的插入排序有：：直接插入排序和希尔排序两种8.2.1直接插入排序最简单的排序法！1、其基本思想是顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置

8.2 插入排序 插入排序的基本思想是：每步将一个待排序的对象，按 其关键字大小，插入到前面已经排好序的一组对象的适当位 置上，直到对象全部插入为止。 简言之，边插入边排序，保证子序列中随时都是排好序的。 常用的插入排序有：直接插入排序和希尔排序两种。 8.2.1 直接插入排序 1、其基本思想是： 顺序地把待排序的数据元素按其关键字值的大小插入到已排 序数据元素子集合的适当位置。 最简单的排序法！

例1：关键字序列T=（13，6，3，31，9，27，5，11），请写出直接插入排序的中间过程序列。初始关键字序列：【13】,6, 3,31,9,27,5, 11第一次排序：[6, 13],3,31, 9, 27, 5, 11第二次排序：[3, 6, 13],31, 9, 27, 5, 11第三次排序：[3,6,13,31],9,27,5, 11第四次排序：3, 6, 9, 13, 31] ,27,5, 11第五次排序：[3,6,9,13, 27,31],5,11第六次排序：[3,5,6.9,13,27,31】,11第七次排序：[3,5, 6,9, 11,13, 27.31】注：方括号「1中为已排序记录的关键字，下划横线的关键字表示它对应的记录后移一个位置

初始关键字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11 第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11 第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11 第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11 第六次排序： 【3, 5, 6, 9, 13，27, 31】, 11 第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。 注：方括号[ ]中为已排序记录的关键字，下划横线的关键字 表示它对应的记录后移一个位置

2.直接插入排序算法public static void insertSort(intla)int i, j, temp;int n = a.Length;for(i= 0;i-1 && temp< a[jl)al[j + 1] = a[i];j --;1a[j +1] = temp;初始关键字序列：【13】,6, 3, 31, 9, 27, 5, 11人第一次排序：[6, 13】,3, 31, 9, 27,5, 11第二次排序：【3, 6, 13】,31, 9, 27,5, 11

public static void insertSort(int[] a){ int i, j, temp; int n = a.Length; for(i = 0; i -1 && temp < a[j]){ a[j + 1] = a[j]; j -; } a[j + 1] = temp; } } 2.直接插入排序算法 初始关键字序列：【13】, 6, 3, 31, 9, 27, 5, 11 第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11 第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11

3、直接插入排序算法分析(1)时间效率：当数据有序时，执行效率最好，此时的时间复杂度为O(n）；当数据基本反序时，执行效率最差，此时的时间复杂度为O(n2)。所以当数据越接近有序，直接插入排序算法的性能越好。(2)空间效率：仅占用1个缓冲单元0(1)(3）算法的稳定性：稳定

(1)时间效率：当数据有序时，执行效率最好，此时的时 间复杂度为O(n)；当数据基本反序时，执行效 率最差，此时的时间复杂度为O(n2)。所以当数 据越接近有序，直接插入排序算法的性能越好。 (2)空间效率：仅占用1个缓冲单元——O（1） (3)算法的稳定性：稳定 3、直接插入排序算法分析

8.2.2希尔（she11）排序（又称缩小增量排序）1、基本思想：把整个待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法排序；小组的个数逐次缩小，当完成了所有数据元素都在一个组内的排序后排序过程结束。2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某个增量d的记录组成一个小组，让增量d逐趟缩短（例如依次取5,3,1），直到d=1为止。3、优点：让关键学值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多

8.2.2 希尔（shell）排序（又称缩小增量排序） 1、基本思想：把整个待排序的数据元素分成若干个小组，对同 一小组内的数据元素用直接插入法排序；小组的个数逐次缩小， 当完成了所有数据元素都在一个组内的排序后排序过程结束。 2、技巧：小组的构成不是简单地“逐段分割”，而是将相隔某 个增量d的记录组成一个小组,让增量d逐趟缩短（例如依次取 5,3,1），直到d＝1为止。 3、优点：让关键字值小的元素能很快前移，且序列若基本有序 时，再用直接插入排序处理，时间效率会高很多