1、基本概念
希尔排序是基于直插排序，也称为缩小增量排序。 把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
2、实现
public static void main(String[] args) {
int[] src = {
3,
2,
1,
4,
5,
6,
7,
16,
15,
14,
13,
12,
11,
10,
8,
9 };
shellSort(src);
print(src);
}
public static void shellSort(
int[] list) {
int gap = list.length /
2;
while (
1 <= gap) {
for (
int i = gap; i < list.length; i++) {
int j =
0;
int temp = list[i];
for (j = i - gap; j>=
0 && temp<list[j]; j = j - gap)
list[j + gap] = list[j];
list[j + gap] = temp;
}
gap = gap /
2;
}
}
public static void print(
int src[]){
for (
int i =
0; i < src.length; i++) {
System.out.print(src[i] +
" ");
}
System.out.println();
}
3、复杂度
希尔排序是当时第一个复杂度突破O(
n2
)的。希尔排序的关键是增量的选择。 平均时间 O(nlogn) 最坏情况 O(
ns
) (1
<
<script type="math/tex" id="MathJax-Element-113"><</script>s
<
<script type="math/tex" id="MathJax-Element-114"><</script>2)
参考 有图：http://www.cnblogs.com/chengxiao/p/6104371.html
