希尔排序

1、希尔排序

1、希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，
同时该算法是冲破O(n^2)的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

2、希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

2、时间复杂度

最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)　

3、动态演示

Image text

4、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package sort;

public class ShellSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {99,45,67,12,84,59,32};
		shellSort(a);
		printArr(a);
	}
	
	public static void shellSort(int [] a) {
		int cur;//记录即将插入的当前值
		int dk=a.length/2;//增量
		
		while(dk>0) {
			for(int i=dk;i<a.length;i++) {//比较a.length-1趟
				int index=i-dk;//记录有序数组的最后一位坐标
				cur=a[i];
			
				while(index>=0 && cur<a[index]) {//当前值小于有序数组中的值时
					a[index+dk]=a[index];//记录后移
					index=index-dk;
				}
			
				//当前值不小于前一个值时，把当前值赋给index+dk
				a[index+dk]=cur;
			}
			
			dk=dk/2;
		}
	}
	
	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}

}