数据结构-第10章-内部排序
- 格式：ppt
- 大小：524.50 KB
- 文档页数：88
下载文档原格式
合集下载
数据结构-内排序
Shell排序的性能分析
Shell排序的时间复杂度在O(nlog2n)和O(n2)间， Knuth的 统计结论是，平均比较次数和记录平均移动次数在n1.25与 1.6n1.25之间
Shell排序是一种不稳定的排序方法
最后谈一下delta的取法。 Shell最初的方案是delta=n/2， delta=delta/2，直到delta=1。Knuth的方案是delta=delta/3 +1。其它方案有：都取奇数为好；或delta互质为好等等。 而使用象1, 2, 4, 8, …或1, 3, 6, 9, …这样的增量序列就不太 合适，因为这样会使几个元素多次被分到一组中，从而造 成重复排序，产生大量无用的比较操作
另外，在无序子表中向前移动的过程中，如果没 有交换元素，则说明无序子表已有序，无须再做 排序
24
冒泡排序算法实现
1 void bubble_sort(RecType R[ ], int n) { 2 //待排序元素用一个数组R表示，数组有n个记录
3 int i, j; 4 bool swap=TRUE; //判断无序子表是否已有序的变量
内排序和外排序 按照排序过程中使用内、外存的不 同将排序方法分为内排序和外排序。若待排序记录全 部在内存中，称为内排序；若待排序记录的数量很大， 以致内存一次不能容纳全部记录，在排序过程中需要 进行内、外存交换，称为外排序。本章仅讨论内排序
内排序可分为五大类：插入排序、交换排序、选择排 序、归并排序和基数排序
直接插入排序(straight insert sort) 折半插入排序(binary insert sort) Shell排序(Shell sort)
10
10.2.1 直接插入排序举例
数据结构-第十章-内部排序
0
1
2
3
4
5
6
7
8
i=5
MAXINT 49 2 3
MAXINT 49 6 3 MAXINT 49 6 3 MAXINT 49 6 8
38 1
38 1 38 1 38 1
65 97 5 0
65 5 65 5 65 5 97 0 97 0 97 0
76 4
76 4 76 4 76 4
13
27
49
i=6
最坏情况下,待排记录按关键字非递增有序 排列（逆序）时，第 i 趟时第 i＋1 个对象 必须与前面 i 个对象都做排序码比较, 并且 每做1次比较就要做1次数据移动。总比较 次 数 为 (n+2)(n-1)/2 次 ， 总 移 动 次 数 为 (n+4)(n-1)/2。 在平均情况下的排序码比较次数和对象移 动次数约为 n2/4。因此，直接插入排序的 时间复杂度为 O(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)
基本思想 既然每个要插入记录之前的纪录 已经按关键字有序排列，在查找插入位 臵时就没有必要逐个关键字比较，可以 使用折半查找来实现。由此进行的插入 排序称之为折半插入排序。
折半插入排序的算法
void BInsertSort (SqList &L){ for (i=2;i<=L.length;++i){ L.r[0]=L.r[i]; low=1;high=i-1; //查找范围由1到i-1 while(low<=high){ m=(low+high)/2; if LT(L.r[0].key,L.r[m].key) high=m-1; else low=m+1; }//while 折半查找 for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; //折半查找结束后high+1位臵即为插入位臵 L.r[high+1]=L.r[0]; }//for }//BInsertSort
源代码--数据结构与算法(Python版)chap10 排序
20
交换类
（2）快速排序 快速排序采用分而治之(Divide and Conquer)
的策略将问题分解成若干个较小的子问题，采用 相同的方法一一解决后，再将子问题的结果整合 成最终答案。快速排序的每一轮处理其实就是将 这一的基准数定位，直到所有的数都排序完成 为止。
21
快速排序的基本步骤：
1. 选定一个基准值（通常可选第一个元素）； 2. 将比基准值小的数值移到基准值左边，形
14
• 交换类
交换类排序的基本思想是：通过交换无序序列 中的记录得到其中关键字最小或最大的记录，并将 其加入到有序子序列中，最终形成有序序列。交换 类排序可分为冒泡排序和快速排序等。
15
交换类
（1）冒泡排序 两两比较待排序记录的关键字，发现两
个记录的次序相反时即进行交换，直到没有 反序的记录为止。因为元素会经由交换慢慢 浮到序列顶端，故称之为冒泡排序。
3. 最后对这个组进行插入排序。步长的选法 一般为 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
11
【例】给定序列（11，9，84，32，92，26，58，91，35， 27，46，28，75，29，37，12 ），步长设为d1 =5、d2 =3、 d3 =1，希尔排序过程如下：
for i in range(1,len(alist)):
#外循环n-1
for j in range(i,0,-1):
#内循环
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j] #交换
li=[59,12,77,64,72,69,46,89,31,9] print('before: ',li) insert_sort(li) print('after: ',li)
交换类
（2）快速排序 快速排序采用分而治之(Divide and Conquer)
的策略将问题分解成若干个较小的子问题，采用 相同的方法一一解决后，再将子问题的结果整合 成最终答案。快速排序的每一轮处理其实就是将 这一的基准数定位，直到所有的数都排序完成 为止。
21
快速排序的基本步骤：
1. 选定一个基准值（通常可选第一个元素）； 2. 将比基准值小的数值移到基准值左边，形
14
• 交换类
交换类排序的基本思想是：通过交换无序序列 中的记录得到其中关键字最小或最大的记录，并将 其加入到有序子序列中，最终形成有序序列。交换 类排序可分为冒泡排序和快速排序等。
15
交换类
（1）冒泡排序 两两比较待排序记录的关键字，发现两
个记录的次序相反时即进行交换，直到没有 反序的记录为止。因为元素会经由交换慢慢 浮到序列顶端，故称之为冒泡排序。
3. 最后对这个组进行插入排序。步长的选法 一般为 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。
11
【例】给定序列（11，9，84，32，92，26，58，91，35， 27，46，28，75，29，37，12 ），步长设为d1 =5、d2 =3、 d3 =1，希尔排序过程如下：
for i in range(1,len(alist)):
#外循环n-1
for j in range(i,0,-1):
#内循环
if alist[j]<alist[j-1]:
alist[j],alist[j-1]=alist[j-1],alist[j] #交换
li=[59,12,77,64,72,69,46,89,31,9] print('before: ',li) insert_sort(li) print('after: ',li)
数据结构答案 第10章 排序学习与指导
第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。
（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。
（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。
（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。
2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。
3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。
4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。
然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。
5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。
每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。
6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。
第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。
第十章_排序方法(数据结构ppt-严蔚敏)
第二个问题解决方法——筛选
方法：输出堆顶元素之后，以堆中最后一个元素替代之；然 后将根结点值与左、右子树的根结点值进行比较，并与其中 小者进行交换；重复上述操作，直至叶子结点，将得到新的 堆，称这个从堆顶至叶子的调整过程为“筛选”
例 38 50 97 76
13 27 65 49 13 38
97 27 38 50 76
2 (n 4)(n 1) 记录移动次数： (i 1) 2 i 2
i 2 n
若待排序记录是随机的，取平均值 n2 关键字比较次数： T(n)=O(n² ) 4 记录移动次数：
空间复杂度：S(n)=O(1)
n2 4
折半插入排序
排序过程：用折半查找方法确定插入位置的排序叫~
初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp 交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录， 和rp交换 重复上述两步，直至i==j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有 一个记录为止
x 例 初始关键字： 27 49 i 完成一趟排序： ( 27 38 13 49 65 i 13) 49 97 76 j 97 49 13 j 97 65 49 27 50 j 50)
13 38
76 65 27 49
堆排序：将无序序列建成一个堆，得到关键字最小 （或最大）的记录；输出堆顶的最小（大）值后，使 剩余的n-1个元素重又建成一个堆，则可得到n个元素 的次小值；重复执行，得到一个有序序列，这个过程 叫~ 堆排序需解决的两个问题：
如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新 的堆？
按排序所需工作量
《数据结构》陈慧南 第10章
n−1
n( n − 1 ) ∑i = 2 i =1
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
9.2.3 冒泡排序
（48，36，68，72，12，48，02） 48，36，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，12，72，48，02） （36，48，68，12，72，48，02） （36，48，68，12，48，72，02） 36，48，68，12，48，72，02） 36，48，68，12，48，02，72） （36，48，68，12，48，02，72）
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
序列中两个元素R 序列中两个元素 i和Rj (i<j)，且Ki=Kj，若 ， 排序后仍保持p(i)<p(j)，即Ri 仍然排在 j之 仍然排在R 排序后仍保持 ， 则称所用的排序算法是稳定的。 反之， 前 ， 则称所用的排序算法是稳定的 。 反之 ， 称该排序算法是不稳定的。 称该排序算法是不稳定的。 如果待排序元素总数相对于内存而言较小， 如果待排序元素总数相对于内存而言较小 ， 整个排序过程可以在内存中进行， 整个排序过程可以在内存中进行 ， 则称之 为内部排序； 反之， 为内部排序 ； 反之 ， 如果待排序元素总数 较多， 不能全部放入内存， 较多 ， 不能全部放入内存 ， 排序过程中需 访问外存， 则称之为外部排序。 访问外存 ， 则称之为外部排序 。 本章讨论 内部排序。 内部排序。
n( n − 1 ) ∑i = 2 i =1
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
9.2.3 冒泡排序
（48，36，68，72，12，48，02） 48，36，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，72，12，48，02） （36，48，68，72，12，48，02） 36，48，68，12，72，48，02） （36，48，68，12，72，48，02） （36，48，68，12，48，72，02） 36，48，68，12，48，72，02） 36，48，68，12，48，02，72） （36，48，68，12，48，02，72）
南京邮电大学计算机学院 陈慧南 2006年9月 2006年
序列中两个元素R 序列中两个元素 i和Rj (i<j)，且Ki=Kj，若 ， 排序后仍保持p(i)<p(j)，即Ri 仍然排在 j之 仍然排在R 排序后仍保持 ， 则称所用的排序算法是稳定的。 反之， 前 ， 则称所用的排序算法是稳定的 。 反之 ， 称该排序算法是不稳定的。 称该排序算法是不稳定的。 如果待排序元素总数相对于内存而言较小， 如果待排序元素总数相对于内存而言较小 ， 整个排序过程可以在内存中进行， 整个排序过程可以在内存中进行 ， 则称之 为内部排序； 反之， 为内部排序 ； 反之 ， 如果待排序元素总数 较多， 不能全部放入内存， 较多 ， 不能全部放入内存 ， 排序过程中需 访问外存， 则称之为外部排序。 访问外存 ， 则称之为外部排序 。 本章讨论 内部排序。 内部排序。
第十章排序(可编辑修改word版)
主要辅助手段：多媒体
作业布置
10-4(2),(4),(5),10-6,
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
重点难点
希尔的思想，实现，算法分析
要求掌握知识点和
分析方法
1.概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2。插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段，板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
难点：堆的调整辅助手段：多媒体
作业布置
10-7,10-8
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.5归并排序10.6基数排序
讲授主要内容
归并排序 ，基数排序
重点难点
归并排序 ，基数排序的基本思想与算法实现
本章思考题和习题
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.1概念10.2插入排序
讲授主要内容
1．概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2.
插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段， 板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
教学思路：
作业布置
10-4(2),(4),(5),10-6,
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
重点难点
希尔的思想，实现，算法分析
要求掌握知识点和
分析方法
1.概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2。插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段，板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
难点：堆的调整辅助手段：多媒体
作业布置
10-7,10-8
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.5归并排序10.6基数排序
讲授主要内容
归并排序 ，基数排序
重点难点
归并排序 ，基数排序的基本思想与算法实现
本章思考题和习题
主 要 参考资料
1．《数据结构》，严蔚敏 吴伟民，清华大学出版社；2.数据结构题集（C语言版），
严蔚敏 吴伟民，清华大学出版社；
备注
章节
10.1概念10.2插入排序
讲授主要内容
1．概念：排序，主（次）关键字，内部（外部）排序，比较排序算法的技术指标2.
插入排序的基本思想；3。直接直接插入排序和希尔的思想，实现，算法分析。
教授思路，采 用 的 教学方法和辅助手段， 板书设计，重 点 如 何突出，难点如何解决，师 生 互 动等
教学思路：
数据结构复习题-第10章答案2014-6-16
第10章内部排序一、选择题（每小题1分，共10分）1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ A ）排序法。
A.插入排序B.选择排序C.希尔排序D.二路归并排序2.下列排序算法中( C )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择B.冒泡C.归并D.堆3.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
A. 38, 40, 46, 56, 79, 84B. 40, 38, 46, 79, 56, 84C. 40, 38，46, 56, 79, 84D. 40, 38, 46, 84, 56, 794.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。
A.希尔排序B.冒泡排序C.插入排序D.选择排序5.为实现快速排序算法，待排序序列宜采用的存储方式是（ A ）。
A. 顺序存储B. 散列存储C. 链式存储D. 索引存储6.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ B ）。
A. 79, 46, 56, 38, 40, 84B. 84, 79, 56, 38, 40, 46C. 84, 79, 56, 46, 40, 38D. 84, 56, 79, 40, 46, 387．排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。
A．希尔排序B．冒泡排序C．插入排序D．选择排序8．在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ D ）。
A．希尔排序B．冒泡排序C．直接插入排序D．直接选择排序9．堆是一种有用的数据结构。
《数据结构》期末考试复习题-第10章-排序
第10章排序一、选择题1．某内排序方法的稳定性是指( )。
【南京理工大学 1997 一、10（2分）】A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。
【北京航空航天大学 1999 一、10 （2分）】A. 插入B. 冒泡C. 二路归并D. 堆积3．下列排序算法中，其中（）是稳定的。
【福州大学 1998 一、3 (2分)】A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序4．稳定的排序方法是（）【北方交通大学 2000 二、3（2分）】A．直接插入排序和快速排序 B．折半插入排序和起泡排序C．简单选择排序和四路归并排序 D．树形选择排序和shell排序5．下列排序方法中，哪一个是稳定的排序方法？（）【北方交通大学 2001 一、8（2分）】A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。
【北京邮电大学 2001 一、5（2分）】7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。
（）就是不稳定的排序方法。
【清华大学 1998 一、3 (2分）】A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】10．下面的排序算法中，不稳定的是（）【北京工业大学 1999 一、2 (2分)】A.起泡排序B.折半插入排序C.简单选择排序D.希尔排序E.基数排序F.堆排序。
数据结构第10章习题
三、填空题
1. 设用希尔排序对数组{98，36，-9，0，47，23， 1，8，10，7}进行排序，给出的步长（也称增量 序列）依次是4，2，1则排序需__________趟， 写出第一趟结束后，数组中数据的排列次序 __________。 【南京理工大学 1997 三、5 （2分）】 2．若不考虑基数排序，则在排序过程中，主要进行 的两种基本操作是关键字的______和记录的 _____。 【北京邮电大学 2001 二、7 （4分）】 3．分别采用堆排序，快速排序，冒泡排序和归并排 序，对初态为有序的表，则最省时间的是_____ 算法，最费时间的是______算法。【福州大学 1998 二、10 (2分)】
பைடு நூலகம்
12．就排序算法所用的辅助空间而言，堆排序，快 速排序，归并排序的关系是（ a ） A．堆排序〈 快速排序〈归并排序 B．堆排序 〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排 序 > 快速排序 > 归并排序 E．以上答案都不 对 【西安交通大学 1996 三、1 (3分)】 13．将两个各有N个元素的有序表归并成一个有序表, 其最少的比较次数是( a ) A．N B．2N-1 C．2N D．N-1
2．比较次数与排序的初始状态无关的排序方法是 ( d )。【北方交通大学 2000 二、2（2分）】
A．直接插入排序 D．简单选择排序 B．起泡排序 C．快速排序
3．数据序列（8，9，10，4，5，6，20，1，2）只能是 下列排序算法中的( c )的两趟排序后的结果。 【合肥工业大学 1999 一、3 （2分）】 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 4．数据序列（2，1，4，9，8，10，6，20）只能是下 列排序算法中的( a )的两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 5．对序列{15，9，7，8，20，-1，4}进行排序，进行 一趟后数据的排列变为{4，9，-1，8，20，7，15}； 则采用的是（ c ）排序。【南京理工大学 1998 一、8（2分）】 A. 选择 B. 快速 C. 希尔 D. 冒泡
数据结构chapter_10
typedef struct { //定义每个记录 数据元素) 定义每个记录( //定义每个记录(数据元素)的结构 KeyType key ; //关键字 //关键字 InfoType otherinfo; //其它数据项 //其它数据项 }RedType; //记录类型 //记录类型 typedef struct { //定义顺序表 定义顺序表L //定义顺序表L的结构 RecordType r [ MAXSIZE +1 ]; //存储顺序表的向量 //存储顺序表的向量 //r[0] r[0]一般作哨兵或缓冲区 //r[0]一般作哨兵或缓冲区 int length ; //顺序表的长度 //顺序表的长度 }SqList; //顺序表类型 //顺序表类型
void BInsertSort (SqList &L) {
// 对顺序表 作折半插入排序 对顺序表L作折半插入排序 for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将L.r[i]暂存到 暂存到L.r[0] 暂存到 low = 1; high = i-1; while (low<=high) { // 在r[low..high]中折半查找有序插入的位置 中折半查找有序插入的位置 m = (low+high)/2; // 折半 if (L.r[0].key < L.r[m].key) high = m-1; // 插入点在低半区 else low = m+1; // 插入点在高半区 } // while for ( j=i-1; j>=low; --j ) L.r[j+1] = L.r[j]; // 记录后移 // 插入 L.r[high+1] = L.r[0]; } } // BInsertSort
数据结构Ch10习题答案
第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。
A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。
A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。
A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。
A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。
A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。
数据结构1800试题-第10章 排序 - 答案
第10章排序（参考答案）部分答案解释如下：18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。
20. 本题为步长为3的一趟希尔排序。
24.枢轴是73。
49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。
64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。
二、判断题5. 错误。
例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。
12. 错误。
堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
22. 错误。
待排序序列为正序时，简单插入排序比归并排序快。
三、填空题1. 比较,移动2.生成有序归并段（顺串）,归并3.希尔排序、简单选择排序、快速排序、堆排序等4. 冒泡,快速5. (1)简单选择排序 (2)直接插入排序（最小的元素在最后时）6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。
7. n(n-1)/28.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。
(1)!=null (2)p->next (3)r!=null (4)r->data<q->data(5)r->next (6)p->next9. 题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。
(1)q->link!=NULL (2)r!=p (3)p->link (4)p->link=s (5)p=p->link10.(1)i<n-i+1 (2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i(6)r[max]<-->r[n-i+1]11.(1)N (2)0 (3)N-1 (4)1 (5)R[P].KEY<R[I].KEY (6)R[P].LINK(7)(N+2)(N-1)/2(8)N-1 (9)0 (10)O(1)(每个记录增加一个字段) (11)稳定（请注意I的步长为-1）12. 3,(10,7,-9,0,47,23,1,8,98,36) 13.快速14.(4,1,3,2,6,5,7)15.最好每次划分能得到两个长度相等的子文件。
数据结构第十、十一章：排序
14
9.2 交换排序
冒泡排序
排序过程
将第一个记录的关键字与第二个记录的关键字进行比较， 将第一个记录的关键字与第二个记录的关键字进行比较，若 为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与 为逆序 ，则交换； 第三个记录；依次类推，直至第n-1个记录和第 个记录比较 个记录和第n个记录比较 第三个记录；依次类推，直至第 个记录和第 为止——第一趟冒泡排序，结果关键字最大的记录被安置在 第一趟冒泡排序， 为止 第一趟冒泡排序 最后一个记录上 对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的 个记录进行第二趟冒泡排序， 对前 个记录进行第二趟冒泡排序 记录被安置在第n-1个记录位置 记录被安置在第 个记录位置 重复上述过程，直到“ 重复上述过程，直到“在一趟排序过程中没有进行过交换记 录的操作” 录的操作”为止
按待排序记录所在位置
内部排序： 内部排序：待排序记录存放在内存 外部排序： 外部排序：排序过程中需对外存进行访问的排序
稳定排序和不稳定排序 假设Ki=Kj（1≤i≤n，1≤j≤n，i≠j），且在排序前的序列中Ri领先 假设 （ ， ， ），且在排序前的序列中 领先 ），且在排序前的序列中 于Rj（即i<j）。若在排序后的排序中Ri仍领先于 ，即那些具 （ ）。若在排序后的排序中 仍领先于Rj， ）。若在排序后的排序中 仍领先于 有相同关键字的记录，经过排序后它们的相对次序仍然保持不变， 有相同关键字的记录，经过排序后它们的相对次序仍然保持不变， 则称这种排序方法是稳定的；反之，若Rj领先于 ，则称所用的 则称这种排序方法是稳定的；反之， 领先于Ri， 领先于 方法是不稳定的。 方法是不稳定的。 按排序依据原则
4
例
《数据结构与算法》第十章-排序习题
《数据结构与算法》第二部分习题精选一、填空题1. 大多数排序算法都有两个基本的操作：和。
2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。
(可约定为从后向前比较)3. 在插入和选择排序中，若初始数据基本正序，则选用；若初始数据基本反序，则选用。
4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。
5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。
若对其进行快速排序，在最坏的情况下所需要的时间是。
6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。
7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍），共计移动次记录。
二、单项选择题（）1．将5个不同的数据进行排序，至多需要比较次。
Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25（）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（）3．排序方法中，从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序（）4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。
Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序（）5．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n(n-1)/2 （）6．快速排序在下列哪种情况下最易发挥其长处。
Ａ. 被排序的数据中含有多个相同排序码Ｂ. 被排序的数据已基本有序Ｃ. 被排序的数据完全无序Ｄ. 被排序的数据中的最大值和最小值相差悬殊（）7．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)（）8．若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为Ａ. 38, 40, 46, 56, 79, 84 Ｂ. 40,38, 46 , 79, 56, 84Ｃ. 40, 38，46, 56, 79, 84 Ｄ. 40, 38,46, 84, 56, 79（）9．在最好情况下，下列排序算法中排序算法所需比较关键字次数最少。
数据结构课程的内容
时间效率：虽然比较次数大大减少，可惜移动次数并 未减少，所以排序效率仍为O(n2) 。
空间效率： O（1） 稳定性：稳定
23
折半插入排序算法
void BiInsertSort(SqList *L)
{ int i,j, low,high,m;
for(i=2;i<=L->length;i++)
{ L->r[0]=L->r[i]; low=1; high=i-1;
（KCN）和对象移动次数（RMN）分别为：
比较次数：n i = (n +2)(n -1)
i=2
2
移动次数：n（i +1）= (n +4)(n -1)
i=2
2
时间复杂度为O(n2)。
54 32 1 44 5 3 2 1 33 4 5 2 1 22 3 4 5 1 11 2 3 4 5
比较i次（依次与前面的i-1个记录进行比较，并和哨兵比较1次），移动i+1次（前面的i-1个记录依次向后移动，另外开始 19
13
*表示后一个25
例2：关键字序列T= （21，25，49，25*，16，08），
请写出直接插入排序的具体实现过程。 解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或
暂存单元（Temp）。则程序执行过程为：
初态：
完成!
22410暂存59685*
021816
21516
2425951*
2459*
定义：
设有记录序列：{ R1、R2………Rn } 其相应的 关键字序列为： { K1、K2………Kn }; 若存在一种 确定的关系：Kx<=Ky<=…<= Kz则将记录序列 { R1、 R2……….Rn}排成按该关键字有序的序列： { Rx、 Ry……….Rz}的操作，称之为排序。
空间效率： O（1） 稳定性：稳定
23
折半插入排序算法
void BiInsertSort(SqList *L)
{ int i,j, low,high,m;
for(i=2;i<=L->length;i++)
{ L->r[0]=L->r[i]; low=1; high=i-1;
（KCN）和对象移动次数（RMN）分别为：
比较次数：n i = (n +2)(n -1)
i=2
2
移动次数：n（i +1）= (n +4)(n -1)
i=2
2
时间复杂度为O(n2)。
54 32 1 44 5 3 2 1 33 4 5 2 1 22 3 4 5 1 11 2 3 4 5
比较i次（依次与前面的i-1个记录进行比较，并和哨兵比较1次），移动i+1次（前面的i-1个记录依次向后移动，另外开始 19
13
*表示后一个25
例2：关键字序列T= （21，25，49，25*，16，08），
请写出直接插入排序的具体实现过程。 解：假设该序列已存入一维数组V[7]中，将V[0]作为缓冲或
暂存单元（Temp）。则程序执行过程为：
初态：
完成!
22410暂存59685*
021816
21516
2425951*
2459*
定义：
设有记录序列：{ R1、R2………Rn } 其相应的 关键字序列为： { K1、K2………Kn }; 若存在一种 确定的关系：Kx<=Ky<=…<= Kz则将记录序列 { R1、 R2……….Rn}排成按该关键字有序的序列： { Rx、 Ry……….Rz}的操作，称之为排序。
DS10_排序01_概述和插入排序
排序
先迚排序方法，其时间复杂度为O(nlogn)
基数排序，其时间复杂度为O(d·n)
内排序的分类
按排序过程中依据的原则分
揑入类（直揑排序、二分排序、希尔排序） 交换类（冒泡排序、快速排序） 排序
选择类（直选排序、树型排序、堆排序）
归并类（二路归并排序、多路归并排序） 分配类（多关键字排序、基数排序）
3)折半插入排序性能分析
折半揑入排序减少了关键字的比较次数，但记彔的移动次数丌变，其 时间复杂度不直接揑入排序相同。
折半揑入排序是“稳定的”
3. 2-路插入排序
1）基本思想 2-路揑入排序是在折半揑入排序的基础上改迚的，目的是减少排序过 程中移动记彔的次数，但为此需要n个记彔的辅助空间。
2）具体做法
2)折半插入排序算法
void BinsertSort(SqList &L){ int i,low,high,mid; for(i=2; i<= L.length; ++i) { L.r[0]=L.r[i]; low=1; high=i-1; While(low<=high) { mid=(low+high)/2; if (L.r[0].key< L.r[mid].key) high=mid-1; else low=mid+1; } for( j=i-1; j>=low; j ) L.r[j+1]=L.r[j]; L.r[low]=L.r[0]; } }
另设一个和 L.r 同类型的数组d，首先将 L.r[1] 赋值给 d[1] ，并将 d[1] 看成是在排好序的序列中处于中间位置的记彔，然后从 L.r 中第 2 个记彔起依次揑入到d[1] 之前或之后的有序序列中。先将待揑入记彔的 关键字和 d[1] 的关键字迚行比较。 若 L.r[i]<d[1].key，则将 L.r[i] 揑入到 d[1] 之前的有序表中。反之， 揑入到 d[1] 之后的有序表中。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
独立的两部分，其中一部分记录的关键字均小于L，而另 一部分记录的关键字均大于等于L。分别对这两部分记录 继续进行排序，以达到整个序列有序 。 • 支点的选择方法
Kp1 Kp2 … Kpn 即使序列(※）成为一个按关键字有序的序列
{ Rp1，Rp2，…，Rpn} 这种操作过程称为排序。
5
基本概念
• 排序方法是稳定的 设 Ki=Kj（ l i n，1 j n，i≠j），且在排序前
的序列中 Ri领先于 Rj（即 i＜j），在排序后的序列中 Ri仍 领先于 Rj。
{ mid = (low+high)/2;
if (LT(L.r[0].key,L.r[mid].key)) high=mid-1;
else low=mid+1; }
for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
L. r[j+l]=L. r[j];
L. r[j+l]=L. r[0] ;
}
}
14
直接插入排序
• 例子
初始关键字：( 42 ) 41 33 67 74 23 37 33 i=2：(41) ( 41 42 ) 33 67 74 23 37 33 i=3：(33) ( 33 41 42 ) 67 74 23 37 33 i=4：(33) ( 33 41 42 67 ) 74 23 37 33 i=5：(33) ( 33 41 42 67 74 ) 23 37 33 i=6：(23) ( 23 33 41 42 67 74 ) 37 33 i=7：(37) ( 23 33 37 41 42 67 74 ) 33 i=8：(33) ( 23 33 33 37 41 42 67 74 )
7
排序方法分类
• 按排序时使用的原理 插入排序、交换排序、选择排序、归并排序、基数
排序。 • 按照所需的工作量
简单的排序方法，其时间复杂度为O（n2）； 先进的排序方法，其时间复杂度为O（nlogn）； 基数排序，其时间复杂度为O（d ·n）。
8
3. 基本操作 • 比较两个关键字的大小； • 将记录从一个位置移动至另一个位置。
折半插入排序是一个稳定的排序方法。
22
3. 希尔排序 (Shell’s Sort)
• 概念
希尔排序又称“缩小增量排序”(Diminishing Increment Sort) 属于插入排序类的方法，其时间效率上优于前述几种方法。
• 基本思想 先将整个待排记录序列分割成为若干子序列分别进行
直接插入排序，待整个序列中的记录“基本有序”时，再对 全体记录进行一次直接插入排序。
•排序方法是不稳定的 设 Ki=Kj（ l i n，1 j n，i≠j），且在排序前
的序列中 Ri领先于 Rj（即 i＜j），在排序后的序列中 Rj 领先于 Ri。
6
2. 排序方法分类
• 按照文件所处的位置不同： 内部排序 待排序记录存放在计算机内存中进行的排序过程。 外部排序 排序过程中有内、外存间信息的传递及交换的排序过程。
• 2-路插入排序
• 表插入排序
18
折半插入排序的算法10.2
void BInsertSort(SqList &L)
{ int low,high,mid;
for (int i=2;i<=L.length;++i)
{ L.r[0]=L.r[i];
low = 1; high=i-1;
while (low <= high)
次数为 n-1，对象移动次数为 0。
最坏情况下，排序前对象已经按关键字大小从大 到小有序（逆序），需比较和移动次数为多少？
16
直接插入排序
•时间复杂性分析
若待排序对象序列中出现各种可能排列的概率 相同，则可取上述最好情况和最坏情况的平均 情况。在平均情况下的关键字比较次数和对象 移动次数约为 n2/4。因此，直接插入排序的时 间复杂度为 o(n2)。
20
n 1
log 2 i 1 1 2 2 3 3
i1
20
21
22
4 4 k k
23
2 k 1
(1 2 2 2 2 k 1 ) ( 2 2 2 2 k 1 )
( 2 2 2 k 1 ) 2 k 1
k
k
k
2 j1
2 i 1 (1 2 2 k i )
第四 趟排 序后
13 27 38 49 49 65 76 97
第五 趟排 序后
13 27 38 49 49 65 76 97
第六 趟排 序后
29
冒泡排序的算法
Void bubble-sort(int a[]，int n) for(I=n-1; change=TURE; I>1 && change; --I) { change=false; for (j=0;j<I;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE} }
28
冒泡排序
• 例子
49 38 38 49 65 65 97 76 76 13 13 27 27 49 49 97
初始 关键 字
第一 趟排 序后
38 49 65 13 27 49 76 97
第二 趟排 序后
38 49 13 27 49 65 76 97
第三 趟排 序后
38 13 27 49 49 65 76 97
10
5. 排序方法分析
排序的时间开销: 排序的时间开销是衡量算法好坏的 最重要的标志。排序的时间开销可用算法执行中的数 据比较次数与数据移动次数来衡量。
一般都按平均情况进行估算。对于那些受对象关键字 序列初始排列及对象个数影响较大的，需要按最好情 况和最坏情况进行估算。
衡量排序方法的标准
排序时所需要的平均比较次数
直接插入排序是一种稳定的排序方法。
17
2. 其它插入排序
• 折半插入排序（Binary Insertion Sort）
折半插入排序基本思想是：设在顺序表中有一 个对 象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已经排好序的对象。在插入 v[i] 时，利用折 半搜索法寻找 v[i] 的插入位置。
交换排序的基本思想是两两比较待排序对 象的关键字，如果发生逆序(即排列顺序与 排序后的次序正好相反)，则交换之，直到 所有对象都排好序为止。
26
1. 冒泡排序 (Bubble Sort)
• 基本思想 将第1个记录的关键字和第2个记录的关键字进行比较，
若为逆序（即r[1].key＞r[2].key），则将两个记录交换之， 然后比较第2个记录和第3个记录的关键字。依次类推，直 至第n-1个记录和第n个记录的关键字进行过比较为止。第一 趟冒泡排序后，关键字最大的记录被放到最后一个记录的 位置上。
23
希尔排序
• 例子
例，初始关键字序列为：
43 41 33 67 74 23 37 33 47 35
d=5
43 23
41 37
33 33 67 47 74 35
一趟排序的结果：23 37 33 47 35 43 41 33 67 74
24
希尔排序
23 37 33 47 35 43 41 33 67 74
大家好
第10章 内部排序
讨论各种内部排序方法：插入排序、交换排序、 选择排序、归并排序和基数排序的基本思想、算法 特点、排序过程以及时间复杂性的分析。比较各种 内部排序方法。
2
目录
10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论
15
直接插入排序
•时间复杂性分析
若设待排序的对象个数为L.length= n，则该算 法的主程序执行n-1趟。
关键字比较次数和对象移动次数与对象关键字的 初始排列有关。
最好情况下，排序前对象已经按关键字大小从小 到大有序，每趟只需与前面的有序对象序列的最 后一个对象的关键字比较 1 次，总的关键字比较
排序时所需要的平均移动
排序时所需要的平均辅助存储空间
11
10.2 插入排序
1. 直接插入排序 (Straight Insertion Sort)
• 概念 将一个记录插入到已排好序的有序表中，从而得到一
个新的、记录数增 1 的有序表。
例：已排序的一组记录排列如下： 12，33，45，57，76
现将关键字 40 记录插入上述序列中 12，33，40，45，57，76
• 算法10.1
void InsertSort（SqList &L）{
for(i=2;i<=L.Length;++i)
if LT (L. r[i].key, L. r[i-1].key {
L. r[0]=L. r[i]；
L. r[i]=L. r[i-1]；
for (j=i-2; LT (L. r[0].key, L. r[j].key);- -j）
9
4. 存储结构
（1）以一维数组作为存储结构 （2）以静态链表作为存储结构（链表排序） （3）采用辅助表排序（地址排序）
待排序记录存储在数组中，同时另 设一个指示各个记 录存储位置的地址向量。在排序过程中不移动记录本身，而 移动地址向量中这些记录的 “地址”，排序结束后再按照地 址向量中的值调整记录的存储位置。
12
Kp1 Kp2 … Kpn 即使序列(※）成为一个按关键字有序的序列
{ Rp1，Rp2，…，Rpn} 这种操作过程称为排序。
5
基本概念
• 排序方法是稳定的 设 Ki=Kj（ l i n，1 j n，i≠j），且在排序前
的序列中 Ri领先于 Rj（即 i＜j），在排序后的序列中 Ri仍 领先于 Rj。
{ mid = (low+high)/2;
if (LT(L.r[0].key,L.r[mid].key)) high=mid-1;
else low=mid+1; }
for (int j=i-1; j>=high+1;--j) L.r[j+1]=L.r[j];
L.r[high+1]=L.r[0];
}
}
L. r[j+l]=L. r[j];
L. r[j+l]=L. r[0] ;
}
}
14
直接插入排序
• 例子
初始关键字：( 42 ) 41 33 67 74 23 37 33 i=2：(41) ( 41 42 ) 33 67 74 23 37 33 i=3：(33) ( 33 41 42 ) 67 74 23 37 33 i=4：(33) ( 33 41 42 67 ) 74 23 37 33 i=5：(33) ( 33 41 42 67 74 ) 23 37 33 i=6：(23) ( 23 33 41 42 67 74 ) 37 33 i=7：(37) ( 23 33 37 41 42 67 74 ) 33 i=8：(33) ( 23 33 33 37 41 42 67 74 )
7
排序方法分类
• 按排序时使用的原理 插入排序、交换排序、选择排序、归并排序、基数
排序。 • 按照所需的工作量
简单的排序方法，其时间复杂度为O（n2）； 先进的排序方法，其时间复杂度为O（nlogn）； 基数排序，其时间复杂度为O（d ·n）。
8
3. 基本操作 • 比较两个关键字的大小； • 将记录从一个位置移动至另一个位置。
折半插入排序是一个稳定的排序方法。
22
3. 希尔排序 (Shell’s Sort)
• 概念
希尔排序又称“缩小增量排序”(Diminishing Increment Sort) 属于插入排序类的方法，其时间效率上优于前述几种方法。
• 基本思想 先将整个待排记录序列分割成为若干子序列分别进行
直接插入排序，待整个序列中的记录“基本有序”时，再对 全体记录进行一次直接插入排序。
•排序方法是不稳定的 设 Ki=Kj（ l i n，1 j n，i≠j），且在排序前
的序列中 Ri领先于 Rj（即 i＜j），在排序后的序列中 Rj 领先于 Ri。
6
2. 排序方法分类
• 按照文件所处的位置不同： 内部排序 待排序记录存放在计算机内存中进行的排序过程。 外部排序 排序过程中有内、外存间信息的传递及交换的排序过程。
• 2-路插入排序
• 表插入排序
18
折半插入排序的算法10.2
void BInsertSort(SqList &L)
{ int low,high,mid;
for (int i=2;i<=L.length;++i)
{ L.r[0]=L.r[i];
low = 1; high=i-1;
while (low <= high)
次数为 n-1，对象移动次数为 0。
最坏情况下，排序前对象已经按关键字大小从大 到小有序（逆序），需比较和移动次数为多少？
16
直接插入排序
•时间复杂性分析
若待排序对象序列中出现各种可能排列的概率 相同，则可取上述最好情况和最坏情况的平均 情况。在平均情况下的关键字比较次数和对象 移动次数约为 n2/4。因此，直接插入排序的时 间复杂度为 o(n2)。
20
n 1
log 2 i 1 1 2 2 3 3
i1
20
21
22
4 4 k k
23
2 k 1
(1 2 2 2 2 k 1 ) ( 2 2 2 2 k 1 )
( 2 2 2 k 1 ) 2 k 1
k
k
k
2 j1
2 i 1 (1 2 2 k i )
第四 趟排 序后
13 27 38 49 49 65 76 97
第五 趟排 序后
13 27 38 49 49 65 76 97
第六 趟排 序后
29
冒泡排序的算法
Void bubble-sort(int a[]，int n) for(I=n-1; change=TURE; I>1 && change; --I) { change=false; for (j=0;j<I;++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1]; change=TURE} }
28
冒泡排序
• 例子
49 38 38 49 65 65 97 76 76 13 13 27 27 49 49 97
初始 关键 字
第一 趟排 序后
38 49 65 13 27 49 76 97
第二 趟排 序后
38 49 13 27 49 65 76 97
第三 趟排 序后
38 13 27 49 49 65 76 97
10
5. 排序方法分析
排序的时间开销: 排序的时间开销是衡量算法好坏的 最重要的标志。排序的时间开销可用算法执行中的数 据比较次数与数据移动次数来衡量。
一般都按平均情况进行估算。对于那些受对象关键字 序列初始排列及对象个数影响较大的，需要按最好情 况和最坏情况进行估算。
衡量排序方法的标准
排序时所需要的平均比较次数
直接插入排序是一种稳定的排序方法。
17
2. 其它插入排序
• 折半插入排序（Binary Insertion Sort）
折半插入排序基本思想是：设在顺序表中有一 个对 象序列 V[0], V[1], …, v[n-1]。其中，v[0], V[1], …, v[i-1] 是已经排好序的对象。在插入 v[i] 时，利用折 半搜索法寻找 v[i] 的插入位置。
交换排序的基本思想是两两比较待排序对 象的关键字，如果发生逆序(即排列顺序与 排序后的次序正好相反)，则交换之，直到 所有对象都排好序为止。
26
1. 冒泡排序 (Bubble Sort)
• 基本思想 将第1个记录的关键字和第2个记录的关键字进行比较，
若为逆序（即r[1].key＞r[2].key），则将两个记录交换之， 然后比较第2个记录和第3个记录的关键字。依次类推，直 至第n-1个记录和第n个记录的关键字进行过比较为止。第一 趟冒泡排序后，关键字最大的记录被放到最后一个记录的 位置上。
23
希尔排序
• 例子
例，初始关键字序列为：
43 41 33 67 74 23 37 33 47 35
d=5
43 23
41 37
33 33 67 47 74 35
一趟排序的结果：23 37 33 47 35 43 41 33 67 74
24
希尔排序
23 37 33 47 35 43 41 33 67 74
大家好
第10章 内部排序
讨论各种内部排序方法：插入排序、交换排序、 选择排序、归并排序和基数排序的基本思想、算法 特点、排序过程以及时间复杂性的分析。比较各种 内部排序方法。
2
目录
10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论
15
直接插入排序
•时间复杂性分析
若设待排序的对象个数为L.length= n，则该算 法的主程序执行n-1趟。
关键字比较次数和对象移动次数与对象关键字的 初始排列有关。
最好情况下，排序前对象已经按关键字大小从小 到大有序，每趟只需与前面的有序对象序列的最 后一个对象的关键字比较 1 次，总的关键字比较
排序时所需要的平均移动
排序时所需要的平均辅助存储空间
11
10.2 插入排序
1. 直接插入排序 (Straight Insertion Sort)
• 概念 将一个记录插入到已排好序的有序表中，从而得到一
个新的、记录数增 1 的有序表。
例：已排序的一组记录排列如下： 12，33，45，57，76
现将关键字 40 记录插入上述序列中 12，33，40，45，57，76
• 算法10.1
void InsertSort（SqList &L）{
for(i=2;i<=L.Length;++i)
if LT (L. r[i].key, L. r[i-1].key {
L. r[0]=L. r[i]；
L. r[i]=L. r[i-1]；
for (j=i-2; LT (L. r[0].key, L. r[j].key);- -j）
9
4. 存储结构
（1）以一维数组作为存储结构 （2）以静态链表作为存储结构（链表排序） （3）采用辅助表排序（地址排序）
待排序记录存储在数组中，同时另 设一个指示各个记 录存储位置的地址向量。在排序过程中不移动记录本身，而 移动地址向量中这些记录的 “地址”，排序结束后再按照地 址向量中的值调整记录的存储位置。
12