导语
接上一篇文章(冒泡排序也要写得优雅出众) http://www.jianshu.com/p/8abad5e9432b 直接插入排序的思想是：将数组的无序区元素一个个插入到前面的有序区的合适位置，使有序区仍然有序，开始时有序区只有第一个元素a[0]。
直接插入排序算法步骤：
1.假设待排序数组为a[0...n]，a[0]自成一个有序区，无序区为a[1...n];
2.遍历a[1..n]，在有序区里找到a[i]的合适位置
3.在有序区内，大于a[i]的元素后移，将a[i]插入使得有序区仍然有序。
下面给出严格按照定义书写的代码：
void insertSort(int a[], int length) {
//a[0]为有序区，从第二个元素a[1]开始遍历
for (int i = 1; i < length; i++) {
//为a[i]在前面的有序区里找到适合的位置
int j;
for (j = i - 1; j >= 0; j--) {
if (a[j] < a[i]) {
break;
}
}
if(j != i-1){//如果找到位置
int temp = a[i];
//将大于a[i]的数往后移一位
for (int k = i-1; k > j; k--) {
a[k+1] = a[k];
}
a[j+1] = temp;//将a[i]放到合适位置
}
}
}
下面给出一种改进方法，可以将找位置和移位合并起来，每次a[i]先和a[i-1]进行比较，如果a[i]>a[i-1]说明已经有序不需要找，反之，将大于a[i]的元素一边进行后移，一边查找插入位置，代码如下：
void insertSort2(int a[], int length) {
for (int i = 1; i < length; i++) {
int temp = a[i];
//将找位置与数据后移合并
if (a[i] < a[i - 1]) {
int j;
for (j = i-1; j >= 0 && a[j] > temp; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
我在网上也看到过另一种改进方法，将数据后移用交换函数替代，这样写代码十分简洁：
void insertSort3(int a[], int length) {
for (int i = 1; i < length; i++) {
for (int j = i-1; j >= 0 && a[j] > a[j+1]; j--) {
//用交换代替数据后移
swap(a[j], a[j+1]);
}
}
}
