常见的排序算法——插入排序

插入排序

a. 基本思想

每一次将一个待排序的元素，按其排序码的大小，插入到前边以排好序的合适位置上，直到元素全部插完为止。

直接插入排序

当插入第 i 个元素时，前边的 i - 1 个元素已经排好序，此时用第 i 个元素和 i - 1、i - 2、…..的元素比较，找到插入位置即将第i个元素插入，原来的位置上的元素顺序后移。

代码如下：

void InsertSort(int array[], int size)
{

    //一张牌的时候不用排，因此i从1开始
    for (int i = 1; i < size; ++i)
    {
        int key = array[i];
        int end = i - 1;

        while(end >= 0 && key < array[end])
        {
            //array[end+1]的值已经给key了，因此可以覆盖
            array[end + 1] = array[end];
            end--;
        }

        array[end + 1] = key;
    }

}

因为直接插入排序，前边的i-1个元素是已经排好的。在查找位置时，我们可以用二分查找对其继续进行优化。

优化后的代码如下

void InsertSort(int array[], int size)
{
    for (int i = 1; i < size; ++i)
    {

        int key = array[i];
        int end = i - 1;
        int left = 0;

        //二分查找先找到位置，

#if 0
        int right = i - 1;
        //这里是左闭右闭区间，因此是小于等于
        while (left <= right)
        {
            int mid = left + ((right - left) >> 1);

            if (array[mid] > key)
                right = mid - 1;
            else
                left = mid + 1;
        }
        //找到元素的位置后，将left及其后边的元素都往后搬一个位置
        while (end >= left)
        {
            array[end + 1] = array[end];
            end--;
        }
#endif
        int right = i;
        //左闭右开区间
        while (left < right)
        {
            int mid = left + ((right - left) >> 1);

            if (array[mid] >key)
            {
                right = mid;
            }
            else
                left = mid + 1;
        }
        //找到元素的位置后，将left及其后边的元素都往后搬一个位置
        while (end >= left)
        {
            array[end + 1] = array[end];
            --end;
        }

        array[end + 1] = key;
    }
}

总结

• 元素集合越接近有序，直接插入排序算法的时间效率越高
• 最差情况下：时间效率为O（n）
• 最差情况下：时间复杂度为O(n^2)
• 空间复杂度为：O（1）
• 直接插入排序算法是一种稳定的排序算法

希尔排序

希尔排序又称缩小增量排序，是对直接插入排序的优化，算法先将要排序的一组数按某个增量gap分成若干组，每组中记录的下标相差gap.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。

代码如下：

void ShellSort(int array[], int size)
{
    int gap = size;

    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (int i = gap; i < size; i += gap)
        {
            int key = array[i];
            int end = i - gap;

            //这里的end必须大于等于0，否则数组会越界
            while (end >= 0&&array[end] > key)
            {
                array[end + gap] = array[end];
                end -= gap;
            }
            array[end + gap] = key;
        }

    }
}

总结

• 时间复杂度为O(N^1.25)~O(1.6N^1.25)
• 空间 复杂度为O(1)
• 希尔排序时适合数据量大的数据集合排序
• gap=gap/3+1为最优