第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的先后次序保持不变，则称这种排序算法是稳定的