7.2 希尔排序

Donald Shell

希尔排序：

• 定义增量序列DM >DM-1 >...>D1 =1
• 对每个 Dk 进行“Dk-间隔”排序( k = M, M-1, ... 1 )
• 注意:“Dk-间隔”有序的序列，在执行“Dk-1-间隔”排序后，仍然是“Dk- 间隔”有序的。

原始希尔排序代码

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 = θ(N平方)；

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