希尔排序

发表于   |   分类于   |  

希尔排序

又称缩小增量排序，只要最后一个增量是1，任何的序列都是可行的。在使用增量H之后，对于每一个i,我们有A[i]<=A[i+H],及所有相隔H的元素都被排序

  • 最坏的运行时间是O(n^2)
  • 最好的序列是{1，5，19，41，109…} 的项是[94^i-92^i+1]和[4^i-3*2^i+1]

简单实现（Java）

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void shellSort(int[]table){
	//控制增量，增量减半
	for(int delta=table.length/2;delta>0;delta/=2){
		//一趟分若干组，一组进行直接插入排序
		for(int i=delta;i<table.length;i++){
			int temp=table[i],j;
			//每组元素相距delta远，寻找插入位置
			for(j=i-delta;j>=0&&temp<table[j];j-=delta)
				table[j+delta]=table[j];
				table[j+delta]=temp;
		}
	}
}
  • 使用Hibbard增量，平均运行时间是O(N^(5/4))
  • 使用{1，5，19，41，109…}平均运行时间O(N(7/6))