当前课程知识点：数据结构 > 第8章 排序 > 8.2 插入排序 > 讲解（上）
这一节，我们来学习插入排序
插入排序所基于的思想，就是每次从无序区中，选取一个元素，插入到有序区
这里有一个概念，叫无序区、有序区
使得有序区长度不断变大
直到包含全部待排元素
所有的元素都在有序区里面
我们就排好了
插入排序，我们这里介绍两种，第一种
叫直接插入排序
我们先来看它的算法思想
首先，n个元素构成待排的序列
有序区
初始情况下，只包含第1个元素
因为，1个元素
无论它的值是多少
都是有序的
无序区
就是后n-1个元素
第1次，i等于2
也就是，第1次要插入的元素是R2
我们重复以下步骤
n-1次
每一次这样的操作
我们称为第i趟直接插入
第i趟直接插入
要干什么事情呢
我们就是将
Ri这个元素，也就是无序区当中的第一个元素
插入到有序区
R1到R(i-1)的合适位置
注意，现在的有序区
我们一般化
就是R1到R(i-1)
我们将无序区的第一个元素Ri
插入到有序区的合适位置
现在，有序区的元素个数，就多了一个了
由原来的i-1个，变成了i个
相反，无序区的元素少了一个
由原来的n-i+1，变成了n-i
具体来说
无序区就是R(i+1)到Rn
现在，我们来看直接插入具体的过程
我们第一次要插入的元素是6
也就是第2个元素
因为，有序区在初始状态，就包含一个元素了
这里以绿色背景来标志，我们插入6的时候
根据常识，应该放到3的后面
有序区多了一个元素
无序区少了一个元素
无序区是白色背景
我们第二次要插入的元素
是这个4，根据常识，4应该放到6的前面，有序区变成3、4、6
最后一次插入的元素是1，有序区变成1、3、4、6
有序区包含了全部的n个元素
排序完毕，那每一趟过程当中，具体又发生了什么呢
比如，我们最后一个插入的元素1
你怎么知道1要放在这个位置呢
现在，我们来看第i趟插入的具体过程
我们从有序区最后一个元素开始
别忘了，有序区是R1到R(i-1)，最后一个元素是R(i-1)
我们拿j来指向有序区的每一个元素
也就是Rj
然后
拿Rj与Ri进行比较
如果Ri小于Rj，则Rj后移，j在初始情况下
它的初值是i-1，有序区的最后一个元素
我们要插入的元素
假设，现在i等于3
也就是，要插入4这个元素
现在，4是小于6的
说明，4一定会插在6的左边
也就是说
6无论如何，都要后移一个位置
我们让6后移，取代原来4的位置
我们再把j向左减
现在，3是小于4的
也就是这里的“否则”
也就是，Ri大于等于Rj
这时候，就不需要再将Rj后移了
这时候，就相当于找到了Ri的存放位置
具体来说，存放在哪呢
应该存放在j+1的位置
j已经被减到了3的位置
这时候
j+1在这儿，这地方，就是Ri应该存放的位置
所以，我们将4放到j+1的位置，就可以了
这就是一趟插入具体的过程
其实，直接插入，我们可以用打扑克的例子来描述，它就是打扑克
我们待排的元素
就是在抓牌之前
桌子上所有属于你的牌
有序区，就是你左手上，已经排好序的牌
而无需区，就是桌子上准备抓起来的那些牌
我们每次都是从无序区(桌子上)起一张牌
然后，插入到左手(有序区)的合适位置
这就是直接插入排序
现在，我们来看具体的算法实现
insertSort
插入排序
我们对顺序表存储的待排序列L，进行直接插入排序
两个循环变量，外层循环
i从2开始，一直到最后一个元素
也就是R2到Rn
如果Ri是小于有序区的最后一个元素的
我们首先加个if语句
待插入的元素
如果小于有序区的最后一个元素
这时候，我们才有必要进行比较和插入
如果大于等于
根本就没有必要了
因为我们排成正序，要插入的Ri，都比有序区最大的那个元素R(i-1)还要大
或者相等
这时候，就没有必要再比较有序区的每一个元素了
现在，我们将Ri
暂存到R0里面
因为，0下标没用
而且，后面移动的过程当中
我们可能会把Ri覆盖掉
所以，我们要暂存一下
而且，(R0)可以作为监视哨来用
我们前面在讲顺序查找的时候，已经讲过了，现在开始循环，内层循环
j从i-1开始，也就是有序区的最后一个元素的下标
然后，比较R0和Rj的大小关系
R0，别忘了，就是Ri(待插入的元素)
只要Ri比Rj要小一些
我们就将Rj后移
原来j下标的位置，放到j+1的位置，就相当于后移了
然后，j--
所以，我们是从有序区右边开始，向左
去与Ri进行比较的
这个内层循环结束了之后
我们说过，Ri就应该放到j+1的位置
所以，R0赋值给j+1的位置
这个算法就结束了
我们可以分析一下这个算法
它的时间复杂度，在最好的情况下
也就是说，这个if语句
永远不成立
这时候，元素是正序
比如，在排序之前，给出的序列已经是正序了
我们插入第一个
也就是2
这个元素的时候
它是大于有序区的最后一个元素的
所以，没必要去比较有序区的元素了
第二个插入的是3，它大于有序区的最后一个元素，也没必要再比较，同样，最后一个元素
它大于有序区的最后一个元素，也没有必要再比较了
这时候，实际上我们只经历了n-1次比较
它就是O(n)，最坏的情况下
元素是逆序的
也就是，排序之前，它就是逆序了
这时候，我们可以算出它的比较次数
实际上是一个等差数列
那我们把系数
都忽略掉
低阶项都忽略掉
那就是平方
它的空间复杂度呢
我们只用到了一个临时的存储空间
所以是O(1)
这个算法是否稳定呢
通过我们刚才的分析
因为这里是小于
这里也是小于
没有出现等于
也就是说，相等的时候
并不会去移动元素
所以，那些后面的元素，它不会跳到前面相同的元素前面去
从这个角度分析
它是稳定的
其实，稳定的算法很容易改成不稳定的
比如，我们将这个小于改成小于等于，这地方的小于改成小于等于，这个算法就变成了不稳定的了
相等的时候
我们也让它移动，移动到前面去
所以，我们可以总结出，所有稳定的排序算法，都能改成不稳定的
但是反过来
如果一个排序算法已经是不稳定的了
你不可能把它改成稳定的
这就是直接插入排序
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
