一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
如图演示了对4个元素进行直接插入排序的过程，共需要(a),(b),(c)三次插入。
直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。[1]
例如,已知待排序的一组纪录是：
60,71,49,11,24,3,66
假设在排序过程中，前3个纪录已按关键码值递增的次序重新排列，构成一个有序序列：
49,60,71
将待排序纪录中的第4个纪录（即11）插入上述有序序列，以得到一个新的含4个纪录的有序序列。首先，应找到11的插入位置，再进行插入。可以讲11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的纪录依照同样的方法逐个插入到该有序序列中。若纪录数n,续进行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。
java代码实现
package com.wepayweb.weixin.util.paixu;
/****
*
* @author www.vxzsk.com V型知识库
*
*/
public class Insort {
final int MAX=20;
int num[]=new int[MAX];
{
System.out.print("生成的随机数组是：");
for(int i=0;i<20;i++){
num[i]=(int)(Math.random()*100);
System.out.print(num[i]+" ");
}
System.out.println();
}
/*-------------------------插入排序法--------------------------------
像是玩朴克一样，我们将牌分作两堆，每次从后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的适当位置
-----------------------------------------------------------------*/
/***
*
* @param number 无序数组
* MAX为为无序数据个数
*/
public void insort(int number[]){
int i, j, k, temp;
long start,end;
start=System.nanoTime();
for(j = 1; j < MAX; j++) {
temp = number[j];
i = j - 1;
while(temp < number[i]) {
number[i+1] = number[i];
i--;
if(i == -1){
break;
}
}
number[i+1] = temp;
}
end=System.nanoTime();
System.out.println("-----------------插入排序法------------------");
System.out.print("排序后是:");
for(i=0;i<=MAX-1;i++){
System.out.print(number[i]+" ");
}
System.out.println();
System.out.println("排序使用时间："+(end-start)+" ns");
}
/**
* @param V型知识库 www.vxzsk.com
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Insort s = new Insort();
s.insort(s.num.clone()); //插入排序法
}
}感觉本站内容不错，读后有收获？小额赞助,鼓励网站分享出更好的教程