常见排序算法(4)--希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是直接插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n²)的第一批算法之一。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

看文字可能比较迷糊，先看图吧。

例子.png

你可能会说，图我是看懂了，但是代码还是不知道咋写。别急，现在就来看代码。还记得前面的直接插入排序的代码吗？其实直接插入排序是下面的插入排序的一种特殊情况(increment=1)，我们只要把直接插入排序的代码拷贝过来，然后加入一个increment参数，把1改为increment就好了。简单吧。

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

现在来理解下这段代码。我们拿数组{8,9,1,7,2,3,5,4,6,0}举例。假设increment=4。insertionSort(arr,10,4)执行完成后，好像就是把原数组分成了若干小数组，如{arr[0]=8,arr[4]=2,arr[8]=6}，{arr[1],arr[5],arr[9]}，{arr[2],arr[6]}，{arr[3],arr[7]}。然后分别对此4个小数组进行了直接插入排序。
理解难点：我们这里说的分组其实不是真的分组，数组还是arr[0],arr[1]到arr[9]，只不过因为increment的缘故，好像被分为了4组。
作用：执行一次insertionSortt(arr,length, increment)后，数组就会逐渐变得局部有序。

下面来看看希尔排序的代码。上面的图我们选用的增量increment=length/2，这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量不是最优的。现代的研究证明，增量increment=2ⁿ-1时，效率最高。我们这里采用increment = length / 3 + 1作为最初的增量。希尔排序其实就是不断缩小增量，并且最后一个增量必须等于1(这样才能保证最后一次排序后数组有序)。希尔排序的时间复杂度

// 希尔排序
void ShellSort(int *arr,int length)
{
    int increment = length;
    while (increment > 1) {
        increment = increment / 3 + 1;
        insertionSort(arr, length, increment);
    }
}

希尔排序到这里已经说清楚了。可能读者看到这里已经知道代码怎么写。但是对为啥希尔排序速度比前面的简单排序快的原因不知道。现在我说说自己的理解。

希尔排序的最后一次是增量为1的直接插入排序，希尔排序相对于直接插入排序的不同就是，它通过increment增量不等于1的几次insertionSort排序，逐渐把数组变得局部有序。而直接插入排序对局部有序的数组的效率是很高的。