排序算法之希尔排序原理与实战

说到希尔排序我就想到了插入排序，因为希尔排序是基于插入排序的以下两点性质而提出改进方法的：
1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
以下列出小编对各种排序算法的性能测试的结果，仅供大家参考(性能测试20000大小随机数组)：

通过分析比较希尔排序在效率上还是很理想的。下面将详细讲解希尔排序的原理和实践。
基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
下图为希尔排序的排序分解过程：

希尔排序的完整实现代码如下：

public static void test0(){
	int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1};
    int d=a.length;
	while(true){
		d=d/2;
		for(int x=0;x<d;x++){
			for(int i=x+d;i<a.length;i=i+d){
				int temp=a[i],j;
				for(j=i-d;j>=0&&a[j]>temp;j=j-d){
					a[j+d]=a[j];
				}
				a[j+d]=temp;
			}
		}
		if(d==1)
			break;
	}// 排序结果如下
	for(int i=0;i<a.length;i++){
		System.out.print(a[i]+" ");
	}
}
public static void test1(){
	while(true){
		for(int i=0;i<d;i++){
			for(int j=i;j+d<a.length;j+=d){
				int temp;
				if(a[j]>a[j+d]){
					temp=a[j];
					a[j]=a[j+d];
					a[j+d]=temp;
				}
			}
		}
		if(d==1)
			break;
		d--;
	}
}
public static void main(String [] args){
	test0();
	test1();
}

版权声明：本文为博主原创文章，未经博主允许不得转载。原文地址http://www.xttblog.com/?p=443

： » 排序算法之希尔排序原理与实战