目录
一 基本思想二 例子三 时间复杂度
一 基本思想
希尔排序的实质就是分组插入排序，该方法又称缩小增量排序。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，再对全体记录做一次插入排序。
二 例子
private void ShellSort(int[] array
)
{
int length
= array
.Length
;
for (int gap
= length
/ 2; gap
> 0; gap
/= 2)
{
for (int i
= gap
; i
< length
; i
++)
{
int temp
= array
[i
];
int j
;
for (j
= i
- gap
; j
>= 0 && array
[j
] > temp
; j
-= gap
)
{
array
[j
+ gap
] = array
[j
];
}
array
[j
+ gap
] = temp
;
}
}
}
三 时间复杂度
希尔排序的时间复杂度，与增量序列有关。如：例子的增量序列是{1， 2， 4 …}， 最坏 情况的时间复杂度是 O(n²)。Hibbard提出了另一个{1,3,7，…,2^k-1}，这种序列的最坏情况的时间复杂度是 O(n^1.5)。Sedgewick提出了几种增量序列，其最坏情形运行时间为O（n^1.3）,其中最好的一个序列是{1,5,19,41,109,…}
