当前位置：文档之家 › 第七章_排序

第七章_排序

  • 格式：ppt
  • 大小：1.25 MB
  • 文档页数：103

下载文档原格式

  / 103

合集下载

2017唐班数据结构-17排序

2017唐班数据结构-17排序

比较次数 记录移动次数
最好 平均 最坏
n1 (n1)(n4)/4 (n1)(n2)/2
2n2 (n1)(n8)/4 (n1)(n4)/2
优点：算法简单. 缺点：期望和最坏复杂度为 O(n2) . 稳定性：稳定 辅助空间： O(1)
希尔排序(shell)
将记录按下标的一定增量分组，对每组使用直 接插入排序算法排序；
最 坏时间复杂度 排序前记录已按关键词逆序排列，即dj j-1. 总的
比较次数为n1 n(n-1)/2，总的移动次数为 2(n1) n(n-1)/2.
期望时间复杂度
考察分析 j 2 n dj 的期望值。
对于序列 K1，K2，…，Kn ，如果 1 i j n，且 Ki Kj，则称（Ki , Kj）为上述序列的一个反序对.
实际上， j 2 n dj 正好是序列 K1，K2，…，Kn
的反序对个数。反序对的平均个数为 0+ (0+1)/2+ (0+1+2)/3+ (0123)/4(01234)/5 (012345)/6 … (012…n1)/n 01/22/2 3/24/25/2…( n1)/2 n(n1)/4
直接插入排序小结
7.6 .
79
90
90
90
90 四
趟
56
79
79
88
88 完 交
90
56
88
79
79
成替 排上
4
88
56
56
56 序 浮
下
32
4
32
35
35
沉
27
32
27
32
32
排 序

excel 2007 第7章 数据的排序、筛选

excel 2007 第7章 数据的排序、筛选

先对“销售员” 列进行排序，然后打开“分类汇总” 对话框，在其中进行第一次分类汇总设置，确定后再次打 开“分类汇总”对话框，再次设置分类汇总项，取消“替 找当前分类汇总”复选框的选中，最后确定即可。
7.5.3 嵌套分类汇总
嵌套分类汇总是指在一个已经建立了分类汇总的工 作表中再进行另外一种分类汇总，两次分类汇总的字段 总是不相同的。 在建立嵌套分类汇总前也要首先对工作表中需要进行 分类汇总的字段进行排序，排序的主要关键字应该是第1级 汇总关键字，排序的次要关键字应该是第2级汇总关键字， 其他的依次类推。 有几套分类汇总就需要进行几次分类汇总操作，第2 次汇总是在第1次汇总的结果上进行操作的，第3次汇总操 作是在第2次汇总的结果上进行的，依次类推。
7.3.1 自动筛选
自动筛选一般用于简单的条件筛选，筛选时将不满 足条件的数据暂时隐藏起来，只显示符合条件的数据。 使用自动筛选可以创建3种筛选类型：按列表值、按 格式或按条件。不过，这三种筛选类型是互斥的，用户 只能选择其中的一种。 单击要进行筛选操作工作表中的任意单元格，然后 单击“数据”选项卡上“排序和筛选”组中的“筛选” 按钮 ，此时工作表标题行中的每个单元格右侧会显示 一个三角形的筛选按钮，接下来就可以进行筛选操作了。
下面对“商品进货单”中的“商品名称”进行升序排序，对“数量” 进行降序排序，方法是：单击要进行排序操作工作表中的任意单元格， 然后打开“排序”对话框，在其中设置主要关键字条件，然后单击“添 加条件”按钮，添加一个次要条件并设置次要关键字条件，最后确定即 可。
若要对工作表中的数据按行进行排序，可选择单元格 区域中的一行数据，或者确保活动单元格在表行中，然后 打开“排序”对话框，单击“选项”按钮，打开“排序选 项”对话框，选中“按行排序”单选钮，如下图所示，然 后单击“确定”按钮返回“排序”对话框，再按上述有关 步骤进行设置，最后单击“确定”按钮。

冒泡排序教学设计

冒泡排序教学设计
print(is_sorted(sorted_array)) # 应输出 True
print(is_sorted(unsorted_array)) # 应输出 False
```
答案：True, False
例题5：给定一个整数数组，编写一个冒泡排序的变种，使得数组中的所有偶数都排在所有奇数之前，但不需要对偶数或奇数内部进行排序。
```
for i from 0 to n-1
for j from 0 to n-i-1
if array[j] > array[j+1]
swap(array[j], array[j+1])
```
- Python代码示例：
```python
def bubble_sort(arr):
n = len(arr)
```
解答：这个冒泡排序代码的时间复杂度是O(n^2)。外层循环运行n次，内层循环平均运行n/2次，所以总的运行次数约为n*(n/2)，即O(n^2)。
例题3：给定一个整数数组[5, 1, 4, 2, 8]，请使用冒泡排序算法对其进行排序，并输出每轮排序的结果。
解答：
```python
def bubble_sort(arr):
- 遍历序列：从第一个元素开始，比较相邻的两个元素。
- 交换元素：如果相邻的两个元素顺序错误，即前者大于后者，则交换它们的位置。
- 标记有序：如果一轮比较中没有发生任何交换，说明序列已经有序，将布尔变量设为true。
- 结束条件：当布尔变量为true时，排序结束。
3. 冒泡排序的代码实现
- 伪代码：
- 提出问题：引导学生思考日常生活中排序的例子，如排队、整理物品等，并提问：“计算机是如何进行排序的？”

座位排序礼仪

座位排序礼仪
客人先进先出,先坐先起 3.电梯:
平移电梯:单行右站 升降电梯(1)无人驾驶:陪同人员先入后出
(2)有人驾驶:陪同人员后入后出
客方监督领导和其他人员
654321 客人签字人
客方监督领导和其他人员
123456 主方签字人
签
字
桌
签字仪式排座之一
客人签字人 主方签字人
签
字
桌
参加签字仪式人员
签字仪式排座之二
第六，轿车上面之座次
请问这个双排座轿车上面上座应该是哪个位置？ 第一号位置让客人坐你认为坐在哪里比较好？
• 重要客人坐在哪里，哪里就是上座 • 一般轿车上的上座有三个可能
第七章 座位及排序礼仪
第一，职场排座三原则
• 宾主有别 • 中外不同 • 国际惯例
第二，主席台上之座次
• 前高于后
• 中高于侧
• 中外左右相反
中国传统，政务礼仪强调：以左为上 国际管理是以右为大，以右为上
譬如你是办公室主任，一个区政府的
办公室主任，现在区政府开一个部 委办局局长的会，区政府开个办公 会，主管副区长现在做报告，副区 长面对着大家在台上就座，正在讲 着讲着，区委书记来了，现在办公 室必须在台上给区委书记加个位置， 让他也面对着各位就座，你在台上 摆区委书记这个位置，你认为怎么 摆是最好的？
其实就是前后左右，你怎么跟客人排的问题
ቤተ መጻሕፍቲ ባይዱ 左右的问题:
把墙让给客人 !(实际上就是让客人走在内侧， 而你陪同人员走在外侧。)
前后的问题 :
1.客人不认识路,要在前面带路. 陪同引导的标准位置是什么？ 左前方1米到1.5米处 2.客人认识路,把选择前进方向的权利让给对方
国际会议排序的规则

小班《按规律排序》数学教案

小班《按规律排序》数学教案

小班《按规律排序》数学教案第一章：认识排序1.1 教学目标：了解排序的概念，知道排序是一种将物品按照某种特定的规律进行排列的方法。

能够观察并发现物品之间的规律，进行简单的排序活动。

1.2 教学内容：讲解排序的概念，通过实物展示和图片引导幼儿观察并发现物品之间的规律。

进行简单的排序活动，如按照大小、颜色、形状等规律进行排列。

1.3 教学方法：采用实物展示、图片引导和小组合作的方式进行教学，让幼儿通过观察和操作来理解和掌握排序的概念。

1.4 教学评估：通过观察幼儿在排序活动中的表现，评估他们对排序概念的理解和应用能力。

第二章：数字排序2.1 教学目标：能够理解数字的大小顺序，能够将数字按照从小到大的顺序进行排列。

2.2 教学内容：讲解数字的大小顺序，通过数字卡片和实物展示引导幼儿观察并发现数字之间的规律。

进行数字排序活动，如按照从小到大的顺序排列数字卡片。

2.3 教学方法：采用数字卡片、实物展示和小组合作的方式进行教学，让幼儿通过观察和操作来理解和掌握数字排序的方法。

2.4 教学评估：通过观察幼儿在数字排序活动中的表现，评估他们对数字排序的理解和应用能力。

第三章：形状排序3.1 教学目标：能够识别不同的形状，能够将形状按照某种特定的规律进行排列。

3.2 教学内容：讲解形状的分类和排序方法，通过形状卡片和实物展示引导幼儿观察并发现形状之间的规律。

进行形状排序活动，如按照形状的大小、颜色等规律进行排列。

3.3 教学方法：采用形状卡片、实物展示和小组合作的方式进行教学，让幼儿通过观察和操作来理解和掌握形状排序的方法。

3.4 教学评估：通过观察幼儿在形状排序活动中的表现，评估他们对形状排序的理解和应用能力。

第四章：颜色排序4.1 教学目标：能够识别不同的颜色，能够将颜色按照某种特定的规律进行排列。

4.2 教学内容：讲解颜色的分类和排序方法，通过颜色卡片和实物展示引导幼儿观察并发现颜色之间的规律。

进行颜色排序活动，如按照颜色的顺序进行排列。

第7章生产作业计划与作业排序

第7章生产作业计划与作业排序

例7.3 表7.12是在某工作中心 等待加工的6项作业的加工时间 （包含换产时间）与预定日期 ，假设工作的到达顺序与表中 顺序相符，根据以下规则来决 定其作业顺序，并对它们分别 进行评价：①先到先服务；② 最短作业时间；③交货期最早 ；④最小松弛时间。
FCFS规则排序的结果是A-B-C-D-E-F
【例7.4】 某冲模工厂有5 件特殊的工作需通过两 个工作中心（钻机和车 床）的操作，各项工作 的操作时间如表7.15所 示，为这组工作进行排 序，使总完成时间最短。
根据约贝规则，可得加工顺序：E—D—C—A—B
作业周期示意图
N/3流水型排序——约贝规则的扩展方法
在制品定额法（连锁计算法） 1、 某车间出产量计算公式：
某车间出产量=后车间的投入量+本车间 半成品计划外销量+（中间库半成品定额 -中间库半成品期初预计存量） 2、 某车间投入量计算公式： 某车间投入量=本车间的出产量+本车间 计划允许废品数量+（本车间在制品定额 -本车间在制品期初预计存量）
厂级生产作业计划编制——
m
= ti (n 1)tL i 1
= 34 + (4－1) × 12 = 70（分）
零件加工的生产周期
（3）平行顺序移动方式的计算：
m
m 1
Tpo n ti (n 1) tsj
i 1
j 1
= 4×（10 + 5 + 12 + 7）−（4−1）×（5 + 5 + 7） = 85（分）
（三）生产提前期
表7.5 零件A的有关期量标准
四、单件小批生产作业计划
➢ 生产周期法 ➢ 编制综合日历进度计划 ➢ 三日滚动计划法

第7章-逼近于理想解的排序技术TOPSIS


bij
1(aij
aj*) / (aj
''aj*),
0,
0 aj ' aij aj0 aj0 aij aj*, aj* aij aj '' 其他
设研究生院的生师比最佳区间为[5,6]， a2' 2 ， a2" 12。则例 1 中的属性“生师比”的数据处理结果 如表 b。
表 b 生师比的数据处理
1、构造（同趋势化/同向化）初始矩阵 2、归范化/标准化：用向量规划化的方法求得规范决策矩阵
原始数据同趋化：目的是使各个指标的方向一致。通常采用低优指标 向高优指标转化的方法，绝对数一般采用倒数法（即1/x） ，相对数一 般采用差数法（即1-x）。
3、构造加权规范阵 4、确定正理想解和负理想解； 5、计算各个方案到理想解、负理想解的距离。
属 性
2 方案B
S
B
S
* B
S
* A
正理想解
S
A
方案A
负理想解
O
属性1
最理想解：由考虑的n个方案在 m个属性上的最佳属性值的集合 所构成的综合表现最佳的方案。
S
* j
为方案j与理想解的距离
离S 理j- 为想方解案越j近与(负S j*理越想小解)而的离距负离理想
解越远( S
j
越大)的方案越佳。
负理想解：由考虑的n个方案在 m个属性上的最差属性值的集合 所构成的综合表现最佳的方案。
7）反余切函数转换：y=atan(x)*2/PI
8）模糊量化模式：新数据=1/2+1/2sin[π/（极大值-极小值）*
（X-（极大值-极小值）/2）] X为原数据
9）区间型属性的变换

第七章 作业排序(生产运作与管理,陈荣秋)


星期一 星期二 星期三 星期四 星期五
4 工人1 4 3 3 4 4 2 2 3 3
星期六 星期日
1 1 2 * 2 * 2 * 1 1 * 0 * * *
工人2
工人3 工人4
3 2
1 0
2 1
0 0 *
3 2 1
1
1 0
* 0 0
2 2 1
0
*
1 1 1
0
工人5
作业 1、有7个作业必须全部进行A和B两种作业，顺序是先A后B。 用约翰逊规则决定各作业的顺序。 工件 1 2 3 4 5 6 7 （小时）
单班次问题： 1、保证工人每周有两个休息日； 2、保证工人每周有两个休息日为连休。
启发式算法：
第一步：从每周的人员需求量中，找出全部具有最少人员需求量 的两个连续日，再从中找出两日需求量总和最小者； 第二步：指定一名人员在上述两日休息，从其余准备安排该人员 工作的各日的人员需求量中减去1人的需求量； 第三步：重复第一、二步
Hale Waihona Puke 三、优先调度规则事例 在理论方面，排序问题的难度随着机床数量的增加而增大，而 不是随需加工的作业数量的增加而增大。 （一）n个作业单台机床的排序 零件 所需标准加工时间（h） 顾客预计取货时间（h） A 8 10 B 6 12
C D E
15 3 12
20 18 22
用SPT规则得出的作业排序 加工 开始 加工 结束 流程 预计取 实际取 提前小 拖延 顺序 工作 时间 工作 时间 货时间 货时间 时数 时间 D B A 0 3 9 3 6 8 3 9 17 3 9 17 18 12 10 18 12 17 15 3 7
生产作业排序对最终使用者或消费者无直接影响 （二）排序内容 服务要定义服务交易的时间和地点 制造业仅仅定义产品生产的操作步骤

2016年考研核心题型【数据结构部分】【第7章 排序】


温馨提示：快速排序主要考查两点：1、快速排序算法的特点；2、快速排序算法实现； 3、快速排序的过程或者一趟排序的结果。本考点历年考查很多，是复习的重点，请同学们 务必掌握。
接插入排序每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍
然有序。
折半插入排序是对直接插入排序算法的一种改进。由于前半部分为已排好序的数列，
这样我们可以不用按顺序依次寻找插入点，而是采用折半查找的方法来加快寻找插入点的
速度。折半查找的方法来寻找插入位置，可以减少比较次数。但不影响排序的趟数（仍然
本题只剩下希尔排序了，事实上，本题是利用增量为 d=5、3、1 来对关键字｛50 , 26 , 38 , 80 , 70 , 90 , 8 , 30 , 40 , 20 ｝进行希尔排序。其排序过程如图 7.2 所示。
我方慎重声明，各盈利机构若采用我方资料，必追究法律责任
102
2016 年考研核心考点命题思路解密 数据结构 梦享团队主编
1. 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是
（
）。
A. 排序的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比较次数
【2012 年统考——第 11 题】
【考查内容】直接插入排序和折半插入排序的区别。
【解析】所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。直
一趟冒泡排序结束。
整个排序过程如下图所示。
其过程如图 7.1 所示。
50 40 95 20 15 70 60 45 80
50>40，50和40交换
40 50 95 20 15 70 60 45 80

数据结构第七章 排序


name 张涛 赵亮
冯博远 王强 李燕
7.2
基本原理
插入排序
每次将一个待排序的对象，按其关键字大小， 插入到前面已经排序好的一组对象的适当位臵上， 直到对象全部插入为止。
直接插入排序(Insert Sort)
希尔排序(Shell Sort)
7.2.1
直接插入排序
R[1]---R[i-1]
08 08
16 16
第三次
08
16
21
25* 25
49
希尔排序中d（间隔量）的取法 Shell最初的方案是 d= n/2, d=d/2， 直到d=1； Knuth的方案是d= d/3+1；
其它方案有：都取奇数为好；d互质为好 等等。
希尔排序的稳定性
如序列： 21 25 排序后为：08 16
R[0]有两个作用:
其一: 进入查找循环之前，保存 R[i] 的副本，使之不至 于因记录的后移而丢失R[i]中的内容； 其二: 在 while 循环时，“监视”下标变量 j 是否越界， 一旦越界（j<0）,R[0]自动控制while循环的结束, 从而 避免了在while 循环内的每一次都要检测 j 是否越界( 即 省略了循环条件j>=0）。 因此，把 R[0] 称为“监视哨”。
第七章 排 序
本章内容
排序的概念和有关知识
常用的几种排序方法的基本思想、排序过 程和算法实现 各种排序算法的时间复杂度分析
学生成绩表
学号 姓名 高数 英语 总分
005 010 002
018 004
Chen Lin Gao Hong Wang Na
ZhangYang Zhao Pen
84 69 90
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第七章 排序
本章纲要
1.排序基本概念 1.排序基本概念 2.三种 三种Ｏ 2.三种Ｏ(n2)的简单排序 3.希尔 shell） 希尔（ 3.希尔（shell）排序 4.堆排序 4.堆排序 5.基于分治法的排序 5.基于分治法的排序 6.大型结构排序 6.大型结构排序 7.桶式排序 7.桶式排序 8.外部排序 8.外部排序
2
1.排序基本概念 1.排序基本概念
定义： 定义：
设有记录序列： 设有记录序列：{ R1,R2, ….. ,Rn } 其相应 .. 的关键字序列为： 的关键字序列为：{ K1,K2, ….. ,Kn }; .. 若存在一种确定的关系： 若存在一种确定的关系： Kx <= Ky <= … <= Kz，则将记录序列 { R1,R2, ….. ,Rn } 排 则将记录序列 .. 成按该关键字有序的序列： 成按该关键字有序的序列：{ Rx,Ry, ….. .. Rz } 的操作，称之为排序。 的操作，称之为排序。 排序关系是任意的，如通常经常使用的小于、 排序关系是任意的，如通常经常使用的小于、 大于等关系或任意的关系。 大于等关系或任意的关系。
直接插入排序 二分法插入排序
冒泡排序(Bubble 冒泡排序(Bubble Sort) 选择排序 (Selection Sort)
5
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序 算法思想： 算法思想：
逐个处理待排序的记录， 逐个处理待排序的记录，每个新记录都要与 前面那些已排好序的记录进行比较， 前面那些已排好序的记录进行比较，然后插 入到适当的位置。 入到适当的位置。
32
3.希尔（shell） 3.希尔（shell）排序 希尔
继承插入排序优点
n小，高效 当待排序列有序时， 当待排序列有序时，效率高
Shell排序算法思想： Shell排序算法思想： 排序算法思想
划分成若干子序列， n大，划分成若干子序列，分别直接插入排序 待整个记录“基本有序” 待整个记录“基本有序”时，对整体直接重 排
9 11 12
16
18
23
25
30
31
36
47
34
3.希尔（shell） 3.希尔（shell）排序 希尔
0 1 2 3 4 5 6 7 8 9 10 11 ， 23 ， ， 9 ， 18，16 ， 25， ， 30 47， [初始关键字]： 16， 25，12，30，47，11，23，36，9，18，31 初始关键字] 初始关键字 ， 增量＝ 增量＝5 一趟排 序结果 增量＝ 增量＝3 二趟排 序结果 增量＝ 增量＝1 三趟排 序结果 9
6
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
36、24、10、6、12存放在 r 数组的下标为 1 至 5 的元素之中，用直 、 、 、 、 存放在 的元素之中， 接插入法将其排序。结果仍保存在下标为 1 至 5 的元素之中。 接插入法将其排序。 的元素之中。 0 1 36 2 24 3 10 4 6 5 12
7
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 j
3 10 6
4
5 12
24
36
8
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 j 36
3 10 6
4
5 12
24
9
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
3
1.排序基本概念 1.排序基本概念
内部排序(Internal Sorting)： 内部排序 ：
整个排序过程中所有的记录都可以直接存放在内存中
外部排序(External Sorting)： 外部排序 ：
内存无法容纳所有记录， 内存无法容纳所有记录，排序过程中还需要访问外存
稳定与不稳定： 稳定与不稳定：
2 24 j 36
3 10 6
4
5 12
24
24
10
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 36
3 10 j 6
4
5 12
10
24
11
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24
3 10 j 36 6
4
5 12
10
24
12
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
2
交换次数最多为Θ(n 最少为0 平均为Θ(n 交换次数最多为Θ(n2)，最少为0，平均为Θ(n2)。 最大，最小，平均时间代价均为Θ(n 最大，最小，平均时间代价均为Θ(n2)。
29
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
选择排序 算法思想: 算法思想:
找出剩下的未排序记录中的最小记录， 找出剩下的未排序记录中的最小记录，然后 直接与数组中第i 直接与数组中第i个记录交换 ，比冒泡排序 减少了移动次数
30
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
选择排序
49 i=1 初始： [ 13 38 j i=2 一趟： 13 65 j 97 j 97 j 97 [97 49 49 49 76 j 76 j 76 76 [76 65 65 13 49 j 27 ] j
[38 65 27 j
49 38 ] 27 j 49 49 97 [97 76 j 38 ] 65 ] 65 ] 76 ] [97 ]
31
二趟： 13 三趟： 13 四趟： 13 五趟： 13 六趟： 13
27 27 27 27 27
[65 38 38 38 38
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
选择排序 时间代价 ：
比较次数： 比较次数：Θ(n2)，与冒泡排序一样 交换次数： 交换次数：n-1 总时间代价：Θ(n2) 总时间代价：
直接插入排序
0
1 36
2 24 10
3 10 24 6
4 j
5 12
6
36
18
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 10
3 10 24 6
4 j
5 12
6
6
36
19
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 10
3 10 24 6
a[0] 用作哨兵。共执行 5 遍操作。 用作哨兵。 遍操作。 每遍操作：先将元素复制内容放入a[0]，再将本元素同已排序的序列， 每遍操作：先将元素复制内容放入 ，再将本元素同已排序的序列， 从尾开始进行比较。在已排序的序列中寻找自己的位置，进行插入。 从尾开始进行比较。在已排序的序列中寻找自己的位置，进行插入。 或者寻找不到，则一直进行到哨兵为止。意味着本元素最小， 或者寻找不到，则一直进行到哨兵为止。意味着本元素最小，应该放 在 a[1] 。 每一遍，排序的序列将增加一个元素。 个元素， 每一遍，排序的序列将增加一个元素。如果序列中有 n 个元素，那么 最多进行n 遍即可。 最多进行 遍即可。
high
12
6
10
24
36
low=m+1=3, high=4, m=3, A[m]=24>12
high low
12
6
10
24
36
12
high=m-1=2, low=3, high<low, low即为插入点 即为插入点
减少了比较次数，未降低时间复杂性。 减少了比较次数，未降低时间复杂性。
26
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0
1 36
2 24 10
3 10 12 6
4
5 12 j 36
12
6
24
23
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
直接插入排序
0 1 10 2 20 3 30 4 40 5 50
正序
50 40 30 20 10 逆序 移动、 移动、比较次数可作为衡量时间复杂性的标准
正序
n
逆序
n
28
38 13 49 49 13 27 27 30 49 30 49 65
38 13
13
13 27 30
13 27
38 27 13 27 30 38 27 30 38 30 49 38
第 七
第
n=8
2.三种Ｏ 2.三种Ｏ(n2)的简单排序 三种
冒泡排序 时间代价 ：
比较次数 ：
n−1 i=1
∑(n −i) = n(n −1)/ 2 =Θ(n )
特点： 特点：
关键字较大的记录“跳跃式”地往后移动， 关键字较大的记录“跳跃式”地往后移动，从而使得 在进行最后一趟插入排序之前序列中记录的关键字已 基本有序，只需作少量关键字比较和移动记录， 基本有序，只需作少量关键字比较和移动记录，由此 减少了整个排序过程中所需进行的“比较” 移动” 减少了整个排序过程中所需进行的“比较”和“移动” 的次数。 的次数。
33
3.希尔（shell） 3.希尔（shell）排序 希尔
0 1 2 3 4 5 6 7 8 9 10 [初始关键字]： 16， 25，12，30，47，11，23，36，9，18，31 初始关键字] 初始关键字 ， ， ， ， ， ， ， ， ， ， 增量＝ 增量＝5 一趟排 序结果 增量＝ 增量＝3 二趟排 序结果 增量＝ 增量＝1 三趟排 序结果 9 18 12 11 23 16 25 31 30 47 36 11 23 12 9 18 16 25 36 30 47 31