直接插入排序(Straight Insertion Sort)是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

• 中文名称 直接插入排序
• 外文名称 Straight Insertion Sort
• 类型 插入排序
• 时间复杂度 O(n^2)
• 空间复杂度 O(1)

简介

引言

　　在日常生活中，经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中。例如:一组从小到大排好顺序的数据列{1,2,3,4,5,6,7,9,10}，通常称之为有序列，我们用序号1,2,3，…表示数据的位置，欲把一个新的数据8插入到上述序列中。

　　完成这个工作的步骤:

　　①确定数据"8"在原有序列中应该占有的位置序号。数据"8"所处的位置应满足小于或等于该位置右边所有的数据，大于其左边位置上所有的数据。

　　②将这个位置空出来，将数据"8"插进去。

　　直接插入排序(straight insertion sort)的做法是:

　　每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

　　第一趟比较前两个数，然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中;依次进行下去，进行了(n-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

　　原有序表中关键词比Rj大的记录数:dj

　　比较次数:dj+1 移动次数: dj+2

算法思想

　　算法 InsertSort (R,n)

　　FOR j=2 TO n DO

　　( //每次将Rj插入到有序表R1，…，Rj–1中

　　K←Kj. R←Rj. i←j-1.

　　WHILE (i>0) AND (Ki>K) DO

　　(Ri+1←Ri.

　　i←i-1.)

　　Ri+1←R.

　　)

　　算法InsertSortA( R, s, e )

　　//引入虚拟记录,Ks-1≤min{Ki| s≤i≤e}

　　ISA1 [逐一排序]

　　FOR j=s+1 TO e DO

　　( i←j-1.K←Kj. R←Rj .

　　WHILE K<Ki DO

　　( Ri+1←Ri .

　　i←i-1 .)

　　Ri+1←R .

　　)

　　ISA1 [逐一排序]

　　FOR j=s+1 TO e DO

　　( i←j-1.K←Kj . R←Rj .

　　WHILE K<Ki DO

　　( Ri+1←Ri .i←i-l ) .

　　Ri+1←R )

　　直接插入排序的时间复杂度为 O(n2)。

排序方法

　　1.简单方法

　　首先在当前有序区R[1..i-1]中查找R[i]的正确插入位置k(1≤k≤i-1);然后将R[k..i-1]中的记录均后移一个位置，腾出k位置上的空间插入R[i]。

　　注意:若R[i]的关键字大于等于R[1..i-1]中所有记录的关键字，则R[i]就是插入原位置。

　　2.改进的方法

　　一种查找比较操作和记录移动操作交替地进行的方法。具体做法:

　　将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i-1，i-2，…，1)的关键字进行比较:

　　① 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置;

　　②若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。

　　关键字比R[i]的关键字大的记录均已后移，所以j+1的位置已经腾空，只要将R[i]直接插入此位置即可完成一趟直接插入排序。

哨兵的作用

　　算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。

　　哨兵有两个作用:

　　① 进入查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容;

　　② 它的主要作用是:在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

　　注意:

　　① 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。

　　【例】单链表中的头结点实际上是一个哨兵

　　② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。

过程实例

　　例:

　　原有序表:(9 15 23 28 37) 20

　　找插入位置 : (9 15 ^ 23 28 37) 20

　　新有序表: (9 15 20 23 28 37)

　　设待排序的文件有8个记录，其关键字分别为:49，38，65，97，76，13，27，49。为了区别两个相同的关键字49，后一个49的下方加了一下划线以示区别。其排序过程见

算法描述

　　Python 代码实现

　　C/C++代码实现直接插入排序

　　Objective-C实现

　　JAVA实现

　　C#实现