直接插入排序算法-课件·PPT

}
r[i]=x;
qksort(r,t,j-1);
2021/2/10
qksort(r,j+1,w);
21
}
– 算法评价 • 时间复杂度 – 最好情况（每次总是选到中间值作枢轴） T(n)=O(nlog2n) – 最坏情况（每次总是选到最小或最大元素 作枢轴）T(n)=O(n² )
T(n)=O(n²)
• 根据“寻找”插入位置的方法不同，插入法可分为：直 插排序、二分插入排序、希尔排序。
• (1) 直接插入排序
– 若将一个未排序的元素L[i]插入到已排序的具有i-1个 元素的序列的适当位置，步骤如下：
• a. 从右向左顺序搜索已排序的序列，若已排序序 列中的元素比L[i]大，则后移一个位置，直至找到 一个元素L[j-1](0≤j-1≤i-1)的关键字值比L[i]的关键 字值小；
• 希尔排序可提高排序速度，因为 – 分组后n值减小，n² 更小，而T(n)=O(n² )，所 以T(n)从总体上看是减小了 – 关键字较小的记录跳跃式前移，在进行最后一 趟增量为1的插入排序时，序列已基本有序
• 增量序列取法 – 无除1以外的公因子 – 最后一个增量值必须为1
2021/2/10
14
关键字小，则可分别对这两部分记录进行排序，以达到 整个序列有序。 关键字通常取第一个记录的值为基准值。
– 排序过程：对r[s……t]中记录进行一趟快速排序，附设两 个指针i和j，设基准值记录rp=r[s]，x=rp.key
• 初始时令i=s,j=t
• 首先从j所指位置向前搜索第一个关键字小于x的记录， 并和rp交换
9.3 交换排序
• (0) 基本思想：
– 两两比较待排序的数据元素的关键字，如果发生逆序， 则交换之，直到全部对象都排好序为止。

清华大学出版社
概述
数据结构（C++版）
排序算法的存储结构
从操作角度看，排序是线性结构的一种操作，待排序 记录可以用顺序存储结构或链接存储结构存储。
假定1：采用顺序存储结构，关键码为整型，且记录 只有关键码一个数据项。
int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用
假定2：将待排序的记录序列排序为升序序列。
i = 6 18 10 15 21 25 25* 18
10 15 18 21 25 25*
r[0]的作用? 暂存单元 43;+版）
关键问题(1)如何构造初始的有序序列？
解决方法：
将第1个记录看成是初始有序表，然后从第2个记录起 依次插入到这个有序表中，直到将第n个记录插入。 算法描述：
学号 0001 0002 0003 …
姓名 王军 李明 汤晓影
…
高数 85 64 85 …
英语 68 72 78 …
思想品德 88 92 86 …
清华大学出版社
概述
数据结构（C++版）
排序的基本概念
单键排序：根据一个关键码进行的排序； 多键排序：根据多个关键码进行的排序。
学号 0001 0002 0003 …
算法描述：
r[0]=r[i]; j=i-1; while (r[0]<r[j]) {
r[j+1]=r[j]; j--; }
r[0]有两个作用：
1. 进入循环之前暂存了r[i] 的值，使得不致于因记录 的后移而丢失r[i]的内容；
2. 在查找插入位置的循环 中充当哨兵。
清华大学出版社
插入排序
姓名 王军 李明 汤晓影

哨兵的作用
哨兵的作用
算法中引进的附加记录R称监视哨或哨兵(Sentinel)。 哨兵有两个作用： ①进入查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容； ②它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R.可以和自己比较， 循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定 条件"j>=1")。 注意： ①实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 ②引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当 可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵 视为雕虫小技，而应该深刻理解并掌握这种技巧。
算法描述
算法描述
Python代码实现 C/C+ve-C实现 JAVA实现 C#实现
谢谢观看
直接插入排序
一种最简单的排序方法
01 简介
03 过程实例
目录
02 哨兵的作用 04 算法描述
基本信息
直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已 排好的有序表中，从而得到一个新的、记录数量增1的有序表。
简介
引言 基本思想
基本思想
每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排 序记录全部插入为止。
待排序记录 R1，R2，…，Rn–1, Rn 第一步：R1 第二步：(R1 ), R2 第三步：(R1, R2), R3 …… 第 j步：(R1，R2，…，Rj–1), Rj …… 第 n步: (R1，R2，…，Rn–1), Rn． 例：j=5

算法描述
算法评价
时间复杂度
记录移动次数
最好情况：0
最坏情况：3(n-1)
比较次数： n1 (n i) 1 (n2 n)
i 1
2
T(n)=O(n²)
空间复杂度：S(n)=O(1)
Ch8_6.c
堆排序
堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当 满足下列关系时，称之为堆
增量序列取法 无除1以外的公因子 最后一个增量值必须为1
8.2 交换排序
冒泡排序
排序过程
将第一个记录的关键字与第二个记录的关键字进行比较，若 为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第 三个记录；依次类推，直至第n-1个记录和第n个记录比较为 止——第一趟冒泡排序，结果关键字最大的记录被安置在最 后一个记录上
二趟排序：13 4 48 38 27 49 55 65 97 76
Ch8_3.c
希尔排序特点
子序列的构成不是简单的“逐段分割”，而是将相隔某个增 量的记录组成一个子序列
希尔排序可提高排序速度，因为 分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体 上看是减小了
关键字较小的记录跳跃式前移，在进行最后一趟增量为1 的插入排序时，序列已基本有序
9776
7163
6257 13
4390 27
3308
38
9173 76
7267 13
6350 27
49 30
49
927 13
7360 27
65 30
65
9370 76
2977 30 76
3初0 9第7 第 第 第 第 第 始一二三四五六 关趟趟趟趟趟趟 键 字

24种插入法24种插入法是一种优化排序算法，它的基本思想是将一个列表分为已排序区间和未排序区间，每次从未排序区间取出一个元素，插入到已排序区间的正确位置，使已排序区间保持有序。

在这个过程中，相邻元素的比较和交换次数都很少，所以可以提高排序的效率。

此外，24种插入法还有一些变体，可以根据不同情况选用相应的插入法，达到更好的排序效果。

以下是24种插入法的详细介绍：1. 直接插入排序直接插入排序是最简单的插入法，它将未排序元素插入到已排序区间合适的位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

2. 折半插入排序折半插入排序是对直接插入排序的优化，它采用二分查找的方式找到插入位置。

时间复杂度为O(n²)，空间复杂度为O(1)。

3. 希尔排序希尔排序是一种针对直接插入排序的改进，它将列表按照一定步长分组，每个子列表采用直接插入排序，随着步长逐渐缩小，最终变为一组，完成排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

4. 二路插入排序二路插入排序是对直接插入排序的改进，它采用两个指针，在有序区间之前和之后分别插入未排序元素。

时间复杂度为O(n²)，空间复杂度为O(1)。

5. 多关键词插入排序多关键词插入排序是针对多关键词排序的优化，它将排序条件拆分为多个关键词，分别进行插入排序。

时间复杂度为O(nlogn)，空间复杂度为O(1)。

6. 基数插入排序基数插入排序是对基数排序的优化，它使用插入法对每个桶内的元素进行排序，并合并桶内已排序的元素。

时间复杂度为O(dn)，空间复杂度为O(max)。

7. 大小插入排序大小插入排序是对多关键词排序的优化，它根据元素的大小关系建立排序树，对树进行遍历并插入已排序区间。

时间复杂度为O(nlogn)，空间复杂度为O(nlogn)。

8. 块插入排序块插入排序是对桶排序的优化，它将待排序元素分为若干块，分别进行插入排序，再将已排序块合并。

将新结点x插入L所指的顺序表的 第i个结点的位置上
void InsertList(SeqList *L,DataType x,int i) { int j;
if (L->length==MaxSize { ①表p空rin间tf已("表满空，间不已能满插，入不元能素插，入退元出素，退出运行。");
exit(0); }
3 插入运算的算法分析
平均情况：
表长为n的线性表中，在第i个位置插入一个新元素，元素后移
语句的执行次数为n-i+1。假设i是一个随机值，即在多次插入运算
中取值分布是均匀的，则概率 pi为 1 ，需要移动的元素平均次数
为： n1
pi(n i 1) =
i 1
1 n 1
n 1
n1
3 插入运算的算法分析
该算法的问题规模是表的长度n，基本语句是for循环中执行元 素后移的语句。 最坏情况：
当i=1时，即新插入的元素为表头结点，需要移动表中所有的 元素，元素后移语句将执行n次，这是最坏的情况，时间复杂度为 O(n)； 最好情况：
当i=n+1时，即新插入的结点为表尾结点，元素不需要执行后 移，这是最好的情况，时间复杂度为O(1)。
(n i 1) =
i 1
n 2
也就是说，在顺序表上实现插入操作，等概率情况下，平均要 移动表中一半的数据元素，算法的平均时间复杂度为O(n)。
谢谢学习
主讲教师：邹岚
1 插入运算的算法设计
插队前：
1
2
3
4
5
6
7
空闲空间
插队后：
1
2
3
4
5
6
7

—— 若待排序记录一部分在内存，一部分在外存， 则称为外部排序。
注：外部排序时，要将数据分批调入内存来 排序，中间结果还要及时放入外存，显然外 部排序要复杂得多。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
5.待排序记录在内存中怎样存储和处理？
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
Void BInsertSort (SqList &L) // 折半插入排序
{ for ( i=2；i<=L.length；++i )
{ L.r[0] = L.r[ i ]； // 将L.r [i] 暂存到L.r[0]
处理方式： ① 顺序排序 —— 数据间的逻辑顺序关系通过其物理
存储位置的相邻来体现，排序时直接移动记录； 适合数据较少的情况！
② 链表排序 ——数据间的逻辑顺序关系通过结点中 的指针体现，排序时只修改指针，不移动数据；
③ 地址排序 —— 数据存储在一段连续地址的空间， 构造一个辅助表保持各数据的存放地址（指针），排 序时先修改辅助表中的地址，最后再移动记录。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
4. 什么叫内部排序？什么叫外部排序？ —— 若待排序记录都在内存中，称为内部排序；
内部排序基本操作有两种： ◆ 比较两个关键字的大小；(比不可少的操作) ◆ 存储位置的移动。
i=8
0
1
2
3
4

插入排序、冒泡排序和选择排序之间的比较。 除了直接插入排序，我们还可以学习其他很多排序算法。
感谢观看！
1 信息
更多信息和算法请访问 我们的网站。
2 学习
访问我们的课程和图书 来提升你的技能。
3 代码
查看我们的代码库，学 习更多关于算法和数据 件
欢迎来到这个课件！在这个课件里，我们将会学习关于直接插入排序的一些 基础知识。
什么是直接插入排序？
简介
直接插入排序是一种简单 的排序算法。
适用场景
通常用于对少量元素进行 排序。
核心思想
通过不断比较和移动元素， 将一个无序的数列变为有 序。
工作原理
1
已排序的元素
从第一个元素开始，该元素可以认为已经被排序。
2
寻找插入位置
取出下一个元素，在已经排序的元素序列中从后向前扫描。
3
后移元素
如果被扫描的元素（已排序）大于新元素，将该元素后移一位。
4
插入新元素
重复步骤 3 直到找到已排序的元素小于或者等于新元素的位置。将新元素插入到该位 置后。
示例代码
Java 代码
在 Java 中实现直接插入算法。 我们可以通过使用上述代码实现直接插入排序。
时间复杂度
1 最好情况
2 最坏情况
时间复杂度为 O(n)。
时间复杂度为 O(n²)。
直接插入排序的时间复杂度取决于排序数据的初始顺序。
总结
优点
简单而有效，适用于排序少量元素。
缺点
时间复杂度为平方级别，不适合排序大量元素。
思考
你认为还有哪些实际应用可以使用直接插入排序？
常见的排序算法
几种排序算法的比较

插入排序变例分析：下方程序运行时系统 报错，错在哪里？如何改进？
Const n = 10
Dim a(1 To n) As Integer ‘改成Dim a(0 To n) As Integer
Dim i As Integer, j As Integer, x As Integer
For i = 2 To n x = a(i): j = i - 1
插入排序算法思路和代码实现
对存放原始数据的数组，从第2个元素开始，扫描左侧的已排序 区间，依次将待排序元素插入到正确位置。每趟处理一个元素， 总共排序n-1趟。
Dim i As Integer, j As Integer, x As Integer For i = 2 To n
x = a(i)
内外两层循环分别 起什么作用？或者 说变量i和j的含义
Const size = 20 ‘数组分配空间 Dim a(1 To size) As Integer Dim i As Integer, n As Integer Dim x As Integer x = Val(Text3.Text) '插入数据 For i = n To 1 Step -1
If a(i) <= x Then Exit For a(i + 1) = a(i)
Next p For i = n To p Step -1
a(i + 1) = a(i)
第一个是顺序扫描，第二个是逆序扫 描，必须统一扫描方向。应该修改谁？
Next i
a(p) = x
n=n+1
例题1.已知数组长度为n，其元素值按升序排列，要求 插入新元素x以后，数组仍保持升序排列。下面的代码 能实现前述功能，请将缺失的代码补充完整。

n1
比较次数的最大值 (n i) n(n 1) / 2 O(n2 ) i 1
n1
移动次数的最大值 3(n i) 3n(n 1) / 2 O(n2 ) i 1
冒泡排序方法是稳定的。
9.3.2 快速排序
快速排序的基本思想
快速排序方法是一种所需比较次数较少、在 内部排序中速度比较快的排序方法。
其思想是在待排序的记录序列中任取某个记 录（作为基准）的值作为控制值，采用某种 方法把这个记录放到适当的位置，使得这个 位置的左边的所有记录的值都小于或等于这 个控制值，而这个位置的右边的所有记录的 值都大于或等于这个控制值。
例9.4 (a) 一趟快速排序示例（一次划分过程）
49 38 65 97 76 13 27 49’
排序 所谓排序（Sort），就是要整理文件中的 记录，使它们按关键字递增(或递减)次序重新排 列。排序的确切定义为： 假设文件中有n个记录R1,R2,…Rn，其相应的 关键字分别为K1,K2,…Kn。所谓排序，是需要将 这Ki1n≤个Ki记2≤录…重≤K新in(排或列Ki为1 ≥RKi1i2,R≥i…2,…≥RKiinn,)使。得
例9.1 直接插入排序举例
[初始关键字]
i=2 (38) i=3 (65) i=4 (97) i=5 (76) i=6 (13) i=7 (27) i=8 (49)
监视哨R[0]
[49] 38 65 97 76 13 27 49
[38 49] 65 97 76 13 27 49 [38 49 65] 97 76 13 27 49 [38 49 65 97] 76 13 27 49 [38 49 65 76 97] 13 27 49 [13 38 49 65 76 97] 27 49 [13 27 38 49 65 76 97] 49 [13 27 38 49 49 65 76 97]

其他应用场景
比赛评分排序
在比赛评比中，根据评分高低进行排 序，可以选出优胜者。
事件排队
在排队等待某些事件（如领取某物、 参加某项活动等）时，按照到达时间 的先后顺序进行排序。
06
大班排序的未来发展趋势
人工智能和机器学习在排序中的应用
人工智能和机器学习的发展将进一步改变和优化排序算法，提高排序的准确性和效 率。
优化算法也可以降低时间复杂度。例如，可以使用快速排序 和归并排序等具有线性对数时间复杂度的排序算法来替代冒 泡排序和插入排序等具有O(n²)时间复杂度的排序算法。
04
排序算法的优化和改进
使用更高效的排序算法
选择排序算法
根据数据量和特定需求选 择适合的排序算法，如快 速排序、归并排序、堆排 序等。
股票价格排序
根据股票价格排序
根据股票价格进行排序，可以让投资者更加方便地比较不同股票的 价格水平，从而做出更加明智的投资决策。
根据股票涨幅排序
根据股票的涨幅进行排序，可以让投资者更加清楚地了解哪些股票 的涨势更好，从而更加高效地利用有限的投资资金。
根据股票趋势排序
根据股票价格的Biblioteka 化趋势进行排序，可以让投资者更加清楚地了解哪 些股票有可能上涨或者下跌，从而更好地把握投资时机。
采用并行计算优化性能
并行计算
将排序算法拆分成多个子任务， 并在多个处理器或线程上同时执 行这些子任务，以加快排序速度
。
线程池
使用线程池来管理并控制线程的 数量和执行状态，提高系统的稳
定性和效率。
数据分配
合理分配数据到不同的处理器或 线程上，以充分发挥并行计算的
优势。
05
大班排序的应用场景

1.1.2 快速排序
算法实例：
始关键字
pivotkey 21 25 low
49 25* 16 08 high
一次交换
21
二次交换
三次交换
high-1 完成一趟排序
08 25 low
49 25* 16
high
08
49 25* 16 25
low
high
08 16 49 25*
25
low
08 16
low
常见排序算法
1.1 常见的排序算法
冒泡排序 快速排序 直接插入排序 希尔排序 选择排序 堆排序 归并排序
1.1.1 冒泡排序
算法描述
设待排序记录序列中的记录个数为n 一般地，第i趟起泡排序从1到n-i+1 依次比较相邻两个记录的关键字，如果发生逆序，则交换之 其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位 置上，最多作n-1趟。
08 16
21
high 25* 49 25
high 25* 49 25
low high
1.1.2 快速排序
算法实例：
完成一趟排序
08 16
21 25* 49 25
分别进行快速排序 有序序列
08 16
21 25* 25 49
08 16
21 25* 25 49
11
1.1.2 快速排序
算法分析：
快速排序是一个递归过程; 利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要 是关键字小于基准记录关键字的记录都移到序列左侧； 快速排序的趟数取决于递归树的高度。 如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长 度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情 况

if (L.r[j].key > L.r[j+1].key ) {
for(j = i - 2; L.r[0].key < L.r[j].key]; j--)
L.r[0] = L.r[j]; L.r[j] = L.r[j+1];
L.r[j+1] = L.r[j];
L.r[j+1] = L.r[0]; exchanged =TRUE;
有序序列R[1..i-1]
第i趟 简单选择排序
无序序列 R[i..n] 从中选出关键字最小的记录
有序序列R[1..i]
无序序列 R[i+1..n]
简单选择排序算法
❖ 以顺序表作为存储结构的简单选择排序算法
void SelectSort(SqList &L) {//对顺序表作简单选择排序
ffoorr((ii==11;;ii<<LL..elnenggthth; ;i+i+++) ){{
数据结构定义
#define MAXSIZE 100
typedef int Keytype;
// 定义关键字类型为整型
typedef char InfoType[100];
typedef struct { KeyType key; InfoType otherinfo;
}RedType;
// 关键字项 // 其他数据项 // 记录类型
typedef struct { RedType r[MAXSIZE+1]; int length;
}SqList;
// r[0]闲置或用作哨兵 // 顺序表长度 // 顺序表类型
直接插入排序
直接插入排序(Straight Insertion Sorting)的基本思想 是：n个待排序的元素由一个有序表和一个无序表组成， 开始时有序表中只包含一个元素。排序过程中，每次从 无序表中取出第一个元素，将其插入到有序表中的适当 位置，使有序表的长度不断加长，完成排序过程。

1
2
3
4
5
数组 38 39 51 57 66 2、创建新的序号，比较数的大小移动数据
旧序号 旧数组
1 38
2 39
3 51
4 57
5 66
新序号
1
2
3
4 57 52
5 66 57
6 66
流程图：
因为52<R[5] R[6]:=R[5]
因为52<R[4] R[5]:=R[4] 因为52>R[3] R[4]:=52
将52插Байду номын сангаас 4号位置
空5号位置
空4号位置
问题二：对一个有序列{ R[1],R[2],…,R[n] }，要将 新数据A插入到有序列中，形成新的有序列， 应该怎么做呢？
根据分析原理画出流程图
思考： 1、还有其它插入A的方法吗？画出流程图
2、如何以有序排列的算法为平台进行无序排序？
{ 49,38,65,97,76,13,27,49}
有序列插入排序
教学目标：了解有序列插入排列的原理 能写排序算法
教学难点：插入排序的原理和算法
预备知识
有序列的概念：
对于一组数据按照一定的规则顺序排列 时，通常称之为有序列.
有序列的插入排序 在已经按照某一规则排好的一系列数中，再 插进一个数，成为新的一序列数，且仍按照 原来的规则排列.
用直接插入法把23插入有序列5 8 11 24 33 38 45 48 50 60中，则23在该有序列中 的序位为（ 4 ）
用直接插入法把95插入有序列45 55 67 81 99 102 105 152中，则该有序列中的第1个 数和最后一个数的序号变为（ ） A.1 8 B. 2 9 C. 1 9 D.2 8

平均情况时间复杂度
O(nlogn)，归并排序的平均时间复杂度为O(nlogn)。其中，n为待排序序列的长度。
06
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
分配和收集
基数排序是一种稳定的排序算法，即相同的元素在排序后仍保持原有的顺序。
文件系统需要对文件和目录进行排序，以便用户可以更方便地浏览和管理文件。
数据挖掘和分析中需要对数据进行排序，以便发现数据中的模式和趋势。
计算机图形学中需要对图形数据进行排序，以便进行高效的渲染和操作。
数据库系统
文件系统
数据挖掘和分析
计算机图形学
02
插入排序
将待排序的元素按其排序码的大小，逐个插入到已经排好序的有序序列中，直到所有元素插入完毕。
简单选择排序
基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 时间复杂度：堆排序的时间复杂度为O(nlogn)，其中n为待排序元素的个数。 稳定性：堆排序是不稳定的排序算法。 优点：堆排序在最坏的情况下也能保证时间复杂度为O(nlogn)，并且其空间复杂度为O(1)，是一种效率较高的排序算法。
基数排序的实现过程
空间复杂度
基数排序的空间复杂度为O(n+k)，其中n为待排序数组的长度，k为计数数组的长度。
时间复杂度
基数排序的时间复杂度为O(d(n+k))，其中d为最大位数，n为待排序数组的长度，k为计数数组的长度。
适用场景
当待排序数组的元素位数较少且范围较小时，基数排序具有较高的效率。然而，当元素位数较多或范围较大时，基数排序可能不是最优选择。

详解排序算法（⼀）之3种插⼊排序（直接插⼊、折半插⼊、希尔）直接插⼊排序打过牌的⼈都知道，当我们拿到⼀张新牌时，因为之前的牌已经经过排序，因此，我们只需将当前这张牌插⼊到合适的位置即可。

⽽直接插⼊排序，正是秉承这⼀思想，将待插⼊元素与之前元素⼀⼀⽐较，从⽽找到合适的插⼊位置。

那么使⽤直接插⼊排序，具体是怎样操作的呢？我们取 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 来进⾏⽰范。

（1）第1轮排序，3之前⽆可⽐较值，因此我们从44开始操作，取44和3⽐较，⼤于3，顺序保持不变。

得数据3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（2）第2轮排序，取38和44⽐较，38 < 44，再将38与3⽐较，38 > 3，故将38放于第2位，得数据3, 38, 44, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（3）第3轮排序，取5与44⽐较，5 < 44，再将5与38⽐较，5 < 38，再将5与3⽐较，5 > 3, 置于第2位，得数据3, 5, 38, 44, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48（4）如此经过14轮排序后，得到最终结果2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50动态图javascript实现function directInsertSort (arr) {let compare, // 对⽐元素下标current // 待插⼊元素值for (let i = 1; i < arr.length; i++) {current = arr[i]compare = i - 1while (current < arr[compare] && compare >= 0) {arr[compare + 1] = arr[compare]compare--}arr[compare + 1] = current}return arr}折半插⼊排序细⼼的同学可能已经注意到，当我们要将⼀个元素插⼊合适的位置时，其之前的元素是有序的，因此，我们可以⽤折半查找的⽅式来⽐对并插⼊元素，也就是所谓的折半插⼊排序。

数
据
增量 d = 4
32 24 10 24* 16 20 08 28 12 30
结 构 （ 从
概
i
算法描述：
念 到 实 现 ）
清
华
for (i = d + 1; i <= n; i++)
大 学
出
{
版 社
将r[i]插入到所属子序列的合适位置；
}
在一趟希尔排序中，从哪个记录开始执行插入操作？
Page 23
}
Page 16
改进的着眼点
在待排序序列正序时，直接插入排序的时间性能是O(n)。
当待排序的记录个数较多时，大量的比较和移动操作使
数
据
直接插入排序算法的效率降低。
结 构 （
从
概
念
到
改进的着眼点：
实 现
）
（1）若待排序记录按关键码基本有序，直接插入排序的效率较高；
清 华 大
学
（2）若待排序记录数量 n 较小，直接插入排序的效率也很高。
第七章 v 排序技术
7-2-1 直接插入排序
讲什么？
直接插入排序的基本思想 直接插入排序的运行实例 直接插入排序的算法及性能分析 希尔排序的基本思想 希尔排序的运行实例 希尔排序的算法及性能分析
数 据 结 构 （ 从 概 念 到 实 现 ） 清 华 大 学 出 版 社
Page 2
基本思想
直接插入排序的基本思想：依次将待排序序列中的每一个记录插 入到已排好序的序列中，直到全部记录都排好序。
数
据
增量 d = 4
12 20 08 24* 16 24 10 28 32 30
结 构 （ 从