对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插 ...
对于大规模乱序数组插入排序很慢,因为它只会交换相邻的元素,因此元素只能一点一点地从数组的一端移动到另一端。例如,如果主键最小的元素正好在数组的尽头,要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序,交换不相邻的元素以对数组的局部进行排序,并最终用插入排序将局部有序的数组排序。
1.基本思想
希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说,一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组(见下图)。在进行排序时,如果h很大,我们就能将元素移动到很远的地方,为实现更小的h有序创造方便。用这种方式,对于任意以1结尾的h序列,我们都能够将数组排序。这就是希尔排序。
希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初,各个子数组都很短,排序之后子数组都是部分有序的,这两种情况都很适合插入排序。子数组部分有序的程度取决于递增序列的选择。透彻理解希尔排序的性能至今仍然是一项挑战。实际上,它是我们唯一无法准确描述其对于乱序的数组的性能特征的排序方法。
2.具体算法
/** * 希尔排序 * @author huazhou * */public class Shell extends Model{ public void sort(Comparable[] a){// System.out.println("Shell"); //将a[]按升序排列 int N = a.length; int h = 1; //1,4,13,40,121,364,1093,... while(h < N/3){ h = 3*h + 1; } //将数组变为h有序 while(h >= 1){ //将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中 for (int i = h; i < N; i++) { for (int j = i; j >= h && less(a[j],a[j-h]); j-=h) { exch(a, j, j-h); } } h = h/3; } }}
原标题:算法—3.希尔排序(中等规模最佳算法)
关键词:排序
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。