PPT《东南大学计算机学院 方效林》

东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件

第九章 排序 本章主要内容 排序的概念插入排序顺序插入排序折半插入排序希尔排序快速排序选择排序归并排序分配排序内部排序算法分析 * 排序的概念 定义将一组杂乱无章的数据按一定规律顺次排列数据表(dataList)待排序数据元素的有限集合排序码(key)通常数据元素有多个属性,作为排序依据的属性称为排序码学生成绩表,按学号小到大排序,按成绩高到低排序 * 排序的概念 排序的稳定性两数据元素排序码相同,排序前后两元素先后顺序若相同,则是稳定的若不同,则不稳定内排序和外排序内排序所有元素都在存在内存的排序外排序数据太多,内存放不下,而存放在外部存储器,排序时需要经常在内、外存之间读写数据 * 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 稳定的 不稳定 排序的概念 排序的时间开销内排序一般用数据比较次数和数据移动次数衡量外排序一般用外存的读写次数衡量(外存慢)排序的空间开销执行排序算法需要的存储空间 * 顺序插入排序 顺序插入排序算法将待排序元素,从后向前寻找适当的插入位置,直到所有元素都插入为止 *

21 25

49 25*

16 08 初始

21 25

49 25*

16 08 第1步21

25 49 25*

16 08 第2步21

25 49 25*

16 08 第3步21

25 25*

49 16

08 第4步16

21 25 25*

49 08 第5步 插入25,25 ≥ 21,无需移动 插入49,49 ≥ 25,无需移动 插入25*,25* <

49,

21 25 25*

49 16

08 插入16,16 <

49,25*,25,21,

16 21

25 25*

49 08

08 16

21 25 25*

49 插入08,08 <

49,25*,25,21,16, 49后移,25*填入 49,25*,25,21后移,16填入 49,25*,25,21,16后移,08填入 顺序插入排序 算法分析最好情况(n个元素)原数据是按小到大顺序排好的每步只需与前一个数据比较一次,而不用移动数据总比较次数n-1,总移动次数0最坏情况(n个元素,i=0,1,…,n-1)原数据按大到小顺序排好的元素i需要比较i次,每比较1次移动1次,元素i移动2次总比较次数和总移动次数 temp = a[i]a[0] = temp 比较和移动最坏最好平均值约为n2/4时间复杂度O(n2) 顺序插入排序 算法分析是稳定的算法,key相同元素原来的顺序不会打乱需要额外一个存储空间 *

21 25

49 25*

16 08 初始

08 16

21 25 25*

49 排序后 temp = a[i]a[0] = temp 折半插入排序 折半插入排序算法将待排序元素,按折半搜索法寻找适当的插入位置,直到所有元素都插入为止 *

16 21

23 25 25*

49 low>

high,49,25*,25后移,23填入

16 21

25 25*

49 23

0 1

2 3

4 5 low mid high

16 21

25 25*

49 23

0 1

2 3

4 5 low mid high

16 21

25 25*

49 23

0 1

2 3

4 5 low mid high mid>

23,high=mid-1,mid=(low+high)/2 mid≤23,low=mid+1,mid=(low+high)/2

16 21

25 25*

49 23

0 1

2 3

4 5 low mid high mid≤23,low=mid+1,mid=(low+high)/2 折半插入排序 算法分析平均情况下,折半搜索比顺序搜索快搜索元素i需比较?log2i? +1次总比较次数移动的时间复杂度O(n2)是稳定的排序算法,需额外一个存储空间 * 比较的时间复杂度O(n*log2n) 希尔排序 基本思想设定不同gap值,距离gap的元素放一起插入排序 *

21 25

49 25*

16 08 初始

21 25

49 25*

16 08 第1步21

25 49 25*