直接插入排序

导语

接上一篇文章(冒泡排序也要写得优雅出众) 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]);
        }
    }
}