【数据结构】——排序算法——1.2、希尔shell排序 @H_403_4@

一、先上维基的图：希尔排序wiki

图一、插入排序的例子

@H_301_28@ @H_301_28@ @H_301_28@ @H_301_28@ @H_301_28@ @H_301_28@

分类	排序算法
数据结构	数组
最差时间复杂度	根据步长序列的不同而不同。已知最好的：
最优时间复杂度	O(n)
平均时间复杂度	根据步长序列的不同而不同。
最差空间复杂度	O(n)

二、描述 @H_403_4@

希尔排序简单地举个例子来说，一个年级的人要按某一科分数排序，那么先叫所有班级的人内部先排好一次。然后再将每个班同个名次的按顺序排成一队。想象一种极端情况，如果每个班级班内的人数、排名及对应排名的分数是完全一样的。那么此时的一次希尔排序就完成了整个排序。而且数据极端情况下最大的移动跨度是班级人数的大小、而不是整个年级的人数大小。这样就大大提高了排序的效率。 @H_403_4@

但是现实并不是这样子。所以，需要将一堆人数以一定步长进行划分，最后步长为总人数时，便是一个直接插入排序了，只是此时的队列已经是初步排好的，最后的插入排序便十分快速。 @H_403_4@

Wiki上的具体例子如下： @H_403_4@

例如，假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样： @H_403_4@

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

然后我们对每列进行排序： @H_403_4@

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 ].这时10已经移至正确位置了，然后再以3为步长进行排序： @H_403_4@

排序之后变为： @H_403_4@

此时为[ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 ] @H_403_4@

可以看到，单个数据在几次操作内，“大步”地先走到正确位置附近。最后以1步长进行排序（此时就是简单的插入排序了）。 @H_403_4@

@H_403_4@

三、Java程序 @H_403_4@

static <E extends Comparable<? super E>> void shellSort(List<E> a) {
    int h = 1;
    while (h < a.size()/3) {
          h = h*3 + 1;    // <O(n^(3/2)) by Knuth,1973>: 1,4,13,40,121,...
    }
 
    for (; h >= 1; h /= 3) {
        for (k = 0; k < h; k++) {
            for (int i = h + k; i < a.size(); i+=h) {
                for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h) {
                   Collections.swap(a,j,j-h);
                }
            }
        }
    }
}

@H_403_4@ 另一个非wiki的版本： @H_403_4@

public class ShellInsertion {  
    public static int count = 0;  
  
    public static void main(String[] args) {  
  
        int[] data = new int[] { 5,3,6,2,1,9,8,7 };  
        print(data);  
        shellSort(data);  
        print(data);  
    }  
    public static void shellSort(int[] data) {  
        // 计算出最大的h值  
        int h = 1;  
        while (h <= data.length / 3) {  
            h = h * 3 + 1;  
        }  
        while (h > 0) {  
            for (int i = h; i < data.length; i++) {  
                if (data[i] < data[i - h]) {  
                    int tmp = data[i];  
                    int j = i - h;  
                    while (j >= 0 && data[j] > tmp) {  
                        data[j + h] = data[j];  
                        j -= h;  
                    }  
                    data[j + h] = tmp;  
                    print(data);  
                }  
            }  
            // 计算出下一个h值  
            h = (h - 1) / 3;  
        }  
    }  
  
    public static void print(int[] data) {  
        for (int i = 0; i < data.length; i++) {  
            System.out.print(data[i] + "\t");  
        }  
        System.out.println();  
    }  
  
}

@H_403_4@