Java常见排序算法详解——希尔排序

Demo_Yang

发布于 2019-04-18 17:05:04

4520

发布于 2019-04-18 17:05:04

概念：

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

原理：

先取一个正整数 d1(d1 < n)，把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序
然后取 d2(d2 < d1) 重复上述分组和排序操作；直到取 di = 1(i >= 1) 位置，即所有记录成为一个组，
最后对这个组进行插入排序。一般选 d1 约为 n/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。列如：我们有一个数组[ 13 14 94 33 82 25 59 94 65 23 45 27 73如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

我们可以看到通过第一趟之后，我们得到的数组是: 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 之后，我们再以3为步长进行排序：

排序之后:

最后再以1位步长进行排序，这时候就是个一个简单的插入排序了。

实现代码:

    public  void sort() {
        int number = array.length / 2;
        int i;
        int j;
        int temp;
        while (number >= 1) {
            for (i = number; i < array.length; i++) {
                temp = array[i];
                j = i - number;
                while (j >= 0 && array[j] > temp) { //需要注意的是，这里array[j] > temp将会使数组从小到到排序。
                    array[j + number] = array[j];
                    j = j - number;
                }
                array[j + number] = temp;
            }
            number = number / 2;
        }
    }