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平方)；
//如果 增量元素不互质，则小增量可能根本不起作用。
网友评论