直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增 1 的有序表。
在日常生活中，经常碰到这样一类排序问题：把新的数据插入到已经排好的数据列中。例如：一组从小到大排好顺序的数据列 {1,2,3,4,5,6,7,9,10}，通常称之为有序列，我们用序号 1,2,3，… 表示数据的位置，欲把一个新的数据 8 插入到上述序列中。
完成这个工作的步骤：
①确定数据 “8” 在原有序列中应该占有的位置序号。数据 “8” 所处的位置应满足小于或等于该位置右边所有的数据，大于其左边位置上所有的数据。
②将这个位置空出来，将数据 “8” 插进去。
直接插入排序 (straight insertion sort) 的做法是：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了 (n-1) 趟扫描以后就完成了整个排序过程。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
基本思想
每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。 [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)
java代码如下：
package 数据结构;
public class zhijiecharupaixu {
public static void sort(long arr[]){
long tep;
for(int i=1;i<arr.length;i++){//注意是从1开始
tep=arr[i];//把每一轮循环arr[i]的值赋给tep，用来进行比较
int k=i;
while(k>0 && arr[k-1]>tep){//当选择的arr[i]的前面有比它大的数的时候，把那个位置的数向后移一位，然后一次循环之后将这个小的插到空出的位置
arr[k]=arr[k-1];
k=k-1;
}
arr[k]=tep;
}
}
}
测试：
package 数据结构;
public class Testzhijiecharupaixu {
public static void main(String args[]){
long arr[]=new long[6];
arr[0]=2;
arr[1]=1;
arr[2]=5;
arr[3]=3;
arr[4]=8;
arr[5]=0;
zhijiecharupaixu.sort(arr);
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
}
输出结果如下：
好啦,这次就到这里啦，有问题可以和我留言哦！
其他博客的链接：
欢迎各位访问哦，这次就到这里啦！
网友评论