《数据结构》 第十章上)
《数据结构》 第十章(上)
第十章内部排序 数据结构 10.1概述 10.2插入排序 10.2.1直接插入排序 10.2.2其它插入排序 10.2.3希尔排序 10.3快速排序 10.4选择排序 10.4.1简单选择排序 10.4.3堆排序 10.5归并排序 10.6基数排序 10.6.1多关键字的排序 10.6.2链式基数排序 10.7各种内部排序方法的比较讨论
数据结构 tjm 第十章 内部排序 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 其它插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论
数据结构 101概述 排序:将一个数据元素(或记录)的任意序列,重新 排列成一个按关键字有序的序列。 有序表与无序表:一组记录按关键字的递增或递减次 序排列得到的结果被称之为有序表,相应地,把排序 前的状态称为无序表。 正序表与逆序表:若有序表是按关键字升序排列的, 则称为升序表或正序表,否则称为降序表或逆序表。 不失普遍性,一般只讨论正序表。 内部排序和外部排序: 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序
数据结构 tjm 10.1 概述 排序：将一个数据元素（或记录）的任意序列，重新 排列成一个按关键字有序的序列。 有序表与无序表：一组记录按关键字的递增或递减次 序排列得到的结果被称之为有序表，相应地，把排序 前的状态称为无序表。 内部排序和外部排序： 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 正序表与逆序表：若有序表是按关键字升序排列的， 则称为升序表或正序表，否则称为降序表或逆序表。 不失普遍性，一般只讨论正序表
数据结构 内部排序得方法: 插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 归并排序:2-路归并排序 其它排序:多关键字排序、基数排序 排序基本操作: 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定:具有相同关键字的数据元素的相对位置关系 在排序前后保持不变。 不稳定:具有相同关键字的数据元素的相对位置关 系在排序前后发生了改变
数据结构 tjm 内部排序得方法： 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 其它排序: 多关键字排序、基数排序 排序基本操作： 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定：具有相同关键字的数据元素的相对位置关系 在排序前后保持不变。 不稳定：具有相同关键字的数据元素的相对位置关 系在排序前后发生了改变
102插入排序 数据结构 1021直接插入排序 排序过程:整个排序过程为n-1趟插入,即先将序 列中第1个记录看成是一个有序子序列,然后从第2 个记录开始,逐个进行插入,直至整个序列有序 算法参见P265 例:i=1(49)386597761327 i=238(3849)6597761327 i365(384965)97761327 97638496597)761327 i=576(3849657697)1327 i=613(133849657697)27 i=727(3273849657697 排序结果:3p78955697)
数据结构 tjm 例: 49 38 65 97 76 13 27 i=2 38 (38 49) 65 97 76 13 27 i=3 65 (38 49 65) 97 76 13 27 i=4 97 (38 49 65 97) 76 13 27 i=5 76 (38 49 65 76 97) 13 27 i=6 13 (13 38 49 65 76 97) 27 i=1 ( ) i=7 (13 38 49 65 76 97) 27 27 j j j j j j 27 38 49 65 76 97 排序结果：(13 27 38 49 65 76 97) 10.2 插入排序 10.2.1 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序 列中第1个记录看成是一个有序子序列，然后从第2 个记录开始，逐个进行插入，直至整个序列有序。 算法参见P265
数据结构 算法评价 若待排序记录按关键字从小到大排列(正序),则 关键字比较次数: 1=n 记录移动次数: 2=2(n-1) 若待排序记录按关键字从大到小排列(逆序),则 关键字比较次数:∑=(+2X(n-1) 记录移动次数:∑(+1) (n+4)(n-1) 若待排序记录是随机的,取平均值,则 关键字比较次数约: 4 记录移动次数约: 时间复杂度:T(m)=Om2 空间复杂度:S(n)=O(1) 直接插入排序是一种稳定的排序方法
数据结构 tjm 若待排序记录按关键字从小到大排列(正序)，则 关键字比较次数： 1 1 2 = − = n n i 记录移动次数： 2 2( 1) 2 = − = n n i 若待排序记录按关键字从大到小排列(逆序)，则 关键字比较次数： 2 ( 2)( 1) 2 + − = = n n i n i 记录移动次数： 2 ( 4)( 1) ( 1) 2 + − + = = n n i n i 若待排序记录是随机的，取平均值，则 关键字比较次数约： 4 2 n 记录移动次数约： 4 2 n 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1) 直接插入排序是一种稳定的排序方法。 算法评价
数据结构 1022其它插入排序 折半插入排序:用折半查找方法确定插入位置。 算法参见P267 例:i=1 (30)1370853942620 213(1330)70853942620 i=76(6133039427085)20 820(133034270)20 i=820 33039427085)20 i=820(613 39427085)20 S m i=820(6 39427085)20 i=820(613203039427085) 时间复杂度:T(n)=O(m2)空间复杂度:S(n)=0(1)m
数据结构 tjm 折半插入排序：用折半查找方法确定插入位置。 例： i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 … i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s mj i=8 20 (6 13 30 39 42 70 85 ) 20 j s i=8 20 (6 13 20 30 39 42 70 85 ) 10.2.2 其它插入排序 算法参见P267 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1)
数据结构 1023希尔排序 希尔排序( Shell sort)又称为“缩小增量排 序”。排序过程:先取一个正整数d1<n,把所有 相隔d1的记录放一组,组内进行直接插入排序; 然后取d2<d1,重复上述分组和排序操作;直至 d=1,即所有记录放进一个组中排序为止
数据结构 tjm 10.2.3 希尔排序 希尔排序（Shell Sort）又称为“缩小增量排 序” 。排序过程：先取一个正整数d1<n，把所有 相隔d1的记录放一组，组内进行直接插入排序； 然后取d2<d1，重复上述分组和排序操作；直至 di=1，即所有记录放进一个组中排序为止
数据结构 例:初始:4938659776132748554 取d1=5 趟分组:4938659776132748554 趟排序:1327485544938659776 取d2=3 二趟分组:1327485544938659776 二趟排序:1344838274955659776 取d3=1 趟分组:1327485544938659776 三趟排序:4132738484955657697
数据结构 tjm 取d3=1 三趟分组：13 27 48 55 4 49 38 65 97 76 三趟排序：4 13 27 38 48 49 55 65 76 97 例：初始：49 38 65 97 76 13 27 48 55 4 一趟排序：13 27 48 55 4 49 38 65 97 76 二趟排序：13 4 48 38 27 49 55 65 97 76 取d1=5 一趟分组：49 38 65 97 76 13 27 48 55 4 取d2=3 二趟分组：13 27 48 55 4 49 38 65 97 76
数据结构 其中第一趟排序过程如下 1327485544938659776 第二趟:1344838274955659776 算法参见P272
数据结构 tjm 其中第一趟排序过程如下: 49 38 65 97 76 13 27 48 55 4 j i 13 27 49 38 第二趟： 13 27 48 55 4 49 38 65 97 76 j j i i 4 27 j j i i 55 j i 38 j j j i i i j j i i 48 65 j i 55 97 j i 4 76 算法参见P272