希尔排序

一、希尔排序

定义增量序列 DM > DM-1 > … > D1 = 1

对每个 Dk 进行“Dk-间隔”排序( k = M, M-1, … 1 )

注意： “Dk-间隔”有序的序列，在执行“Dk-1-间隔”排序后，仍然是“Dk-间隔”有序的

 

希尔增量序列

原始希尔排序 DM = [ N / 2 ] , Dk = [ Dk+1 / 2 ]

void Shell_sort(ElementType A[], int N)
{
    for(D=N/2;D>0;D/=2) {    /* 希尔增量序列 */
        for(P=D;P<N;P++) {     /* 插入排序 */
            Tmp = A[P];
            for(i=P;i>=D && A[i-D]>Tmp;i-=D)
                A[i] = A[i-D];
            A[i] = Tmp;
        }
    }
}

最坏的情况：T = O(N²)

增量元素不互质，则小增量可能根本不起作用

 

二、更多增量序列

Hibbard增量序列

• D_k = 2^k – 1 — 相邻元素互质

• 最坏情况： T = O( N^3/2 )
• 猜想： T_avg = O ( N^5/4 )

Sedgewick增量序列

• {1, 5, 19, 41, 109, … }　　— 9x4ⁱ – 9x2ⁱ + 1 或 4ⁱ – 3x2ⁱ + 1
  
• 猜想： T_avg = O ( N^7/6 )， T_worst = O ( N^4/3 )