希尔排序

/**
 * 希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长
 * 最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了,步长很小,插
 * 入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些!
 * 希尔排序时间复杂度为O(nlog(n)) ~ O(n ^ 2)
 */

#include <stdio.h>

void shell_sort(int array[], int n)
{
    // increment为步长
    int tmp, i, j, increment;

    for(increment = n / 2; increment > 0; increment /= 2)
    {
        // 内部是插入排序,因此决定了此算法的时间复杂度
        for(i = increment; i < n; ++i)
        {
            tmp = array[i];

            // for循环中注意j应该大于increment而不是0
            for(j = i; j >= increment && tmp < array[j - increment]; j -= increment)
            {
                array[j] = array[j - increment];
            }
            array[j] = tmp;
        }
    }
}

main()
{
    int array[] = {-100, -1, 101, 10, 0, -1};
    shell_sort(array, 6);
    for(int i = 0; i < 6; ++i)
        printf("%d ", array[i]);
}

运行结果: -100 -1 -1 0 10 101