第九章排序
第九章 排序
本章主要内容排序的概念插入排序顺序插入排序1折半插入排序希尔排序快速排序选择排序归并排序分配排序内部排序算法分析
本章主要内容 ◼ 排序的概念 ◼ 插入排序 顺序插入排序 折半插入排序 希尔排序 ◼ 快速排序 ◼ 选择排序 ◼ 归并排序 ◼ 分配排序 ◼ 内部排序算法分析 2
排序的概念■定义口将一组杂乱无章的数据按一定规律顺次排列数据表(dataList)待排序数据元素的有限集合排序码(key)通常数据元素有多个属性，作为排序依据的属性称为排序码学生成绩表，按学号小到大排序，按成绩高到低排序4
排序的概念 ◼ 定义 将一组杂乱无章的数据按一定规律顺次排列 ◼ 数据表(dataList) 待排序数据元素的有限集合 ◼ 排序码(key) 通常数据元素有多个属性，作为排序依据的属性称 为排序码 ➢ 学生成绩表，按学号小到大排序，按成绩高到低排序 3
排序的概念排序的稳定性两数据元素排序码相同，排序前后两元素先后顺序初始2(c)2(b)1(a)3(d)若相同，则是稳定的福若不同，则不稳定排序11(a)3(d)稳定的2(b)2(c)■内排序和外排序排序21(a)2(c)2(b)3(d)不稳定口内排序所有元素都在存在内存的排序口外排序数据太多，内存放不下，而存放在外部存储器，排序时需要经常在内、外存之间读写数据1
排序的概念 ◼ 排序的稳定性 两数据元素排序码相同，排序前后两元素先后顺序 ➢ 若相同，则是稳定的 ➢ 若不同，则不稳定 ◼ 内排序和外排序 内排序 ➢ 所有元素都在存在内存的排序 外排序 ➢ 数据太多，内存放不下，而存放在外部存储器，排序 时需要经常在内、外存之间读写数据 4 1(a) 2(b) 2(c) 3(d) 1(a) 2(c) 2(b) 3(d) 初始 2(b) 1(a) 3(d) 2(c) 排序1 排序2 稳定的 不稳定
排序的概念排序的时间开销内排序一般用数据比较次数和数据移动次数衡量口外排序一般用外存的读写次数衡量（外存慢）排序的空间开销口执行排序算法需要的存储空间5
排序的概念 ◼ 排序的时间开销 内排序一般用数据比较次数和数据移动次数衡量 外排序一般用外存的读写次数衡量(外存慢) ◼ 排序的空间开销 执行排序算法需要的存储空间 5