常见排序算法(3)--直接插入排序

个人感觉直接插入排序比前面的冒泡排序和简单选择排序的代码要复杂一点点。直接上代码吧。

1. 直观的直接插入排序

void insertionSort0(int *arr, int length)
{
    for (int i = 1; i < length; i++)
    {
        int j = i;
        while (j >= 1 && arr[j] < arr[j - 1])
        {
            swap(arr,j,j-1);
            j--;
        }
    }
}

直观的直接插入排序.png

待排序数组是 arr[9] = {9, 3, 1, 4, 2, 7, 8, 6, 5};
最开始的时候，可以把arr[0]放到有序那边去。接下来说说上面的代码。我们以i=3举例吧，此时要把arr[3]=4放到左边的数组的正确的位置去。我们的方法是把arr[3]与arr[2]比较，如果前者小，就交换位置。然后继续比较arr[2]与arr[1]，依次这么比较下去，最终arr[i]肯定可以插入到正确的位置。j递减的过程中，如果出现了arr[j]>=arr[j-1],说明已经找到合适的位置了(由于arr[0]到arr[j-1]已经是有序的了)，while循环结束。

2. 优化的直接插入排序

上面的直接插入排序比较好理解，但是其实还是存在可以继续优化的地方，因为每执行一次外循环的时候，有可能会存在多次交换数组元素，其实这是没有必要的。

void insertionSort(int *arr, int length)
{
    int i, j, temp;
    for (i = 1; i < length; i++)
    {
        j = i;
        temp = arr[i];
        while (j >= 1 && temp < arr[j - 1])
        {
            arr[j] = arr[j-1];
            j--;
        }
        arr[j] = temp;
    }
}

这个方法其实跟上面的很像，区别就是引入了一个temp变量记录当前待插入的元素arr[i];其实while做的事情就是把arr[i]元素放到正确的位置，顺便把左边有序数组的比arr[i]大的元素都往后移一位。j>=1很重要，保证arr[j-1]的数组下标永远大于等于0。

虽然直接插入排序和冒泡排序、简单选择排序的时间复杂度都是O(n²)，不过直接插入排序性能更好一些。