希尔排序

希尔排序是插入排序的改进版本。

希尔的C实现:

void shell(int *n, int len)
{
    int gap, i, j, temp;
    for (gap=0; gap<len; gap=gap*3+1);
    while (gap > 0) {
        for (i=gap; i<len; i++) {
            temp = *(n+i);
            j = i - gap;
            while (j>=0 && (temp < *(n+j))) {
                swap(n+j+gap, n+j);
                j -= gap;
            }
        }
        gap = (gap - 1) / 3;
    }
}

希尔排序的时间复杂度根据其选取步长串行的不同有所不同,对上述实例中的复杂度为\(O(n^{3/2})\) ,总体其复杂度可以认为是\(O(n^s)\) ,其中\(1<s<2\) , 平均复杂度为\(O(n \log n)\) . 希尔排序是不稳定的。

下图为希尔排序的一些步长及其对应复杂度(来自维基 ):

shell sort
comments powered by Disqus