插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。比较和交换的时间复杂度为O(n^2)，算法自适应，对于数据已基本有序的情况，时间复杂度为O(n)，算法稳定，开销很低。算法适合于数据已基本有序或者数据量小的情况。

插入算法把要排序的数组分成两部分：***部分包含了这个数组的所有元素，但将***一个元素除外，而第二部分就只包含这一个元素。在***部分排序后，再把这个***元素插入到此刻已是有序的***部分里的位置。

算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 　　

1. 从***个元素开始，该元素可以认为已经被排序 　　

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描 　　

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置 　　

4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 　　

5. 将新元素插入到下一位置中 　　

6. 重复步骤2 　　

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。

代码实现

public void insertionSort() {// 插入排序  
int out, in;  
int count1 = 0, count2 = 0;// 复制次数，比较次数  
for (out = 1; out < nElems; out++) {  
long temp = a[out];  
in = out;  
boolean flag=in>0&&a[in-1]>=temp;  
while(flag){  
if(a[in-1]>=temp){  
if(in>0){  
a[in]=a[in-1];  
count1++;  
--in;   
}  
}  
count2++;  
flag=in>0&&a[in-1]>=temp;  
}   
a[in] = temp;  
}  
System.out.println("复制次数为：" + count1 + " 比较次数为：" + count2);  
} 

插入排序法在数据已有一定顺序的情况下，效率较好。但如果数据无规则，则需要移动大量的数据，其效率就与冒泡排序法和选择排序法一样差了。

【编辑推荐】

1. 18.1.4 插入排序法
2. 介绍C#直接插入排序
3. 经典四讲贯通C++排序之一 插入排序