数据结构与算法(20): 排序- 希尔排序

发表于   |   分类于

希尔排序是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩减增量排序，因DL．Shell于1959年提出而得名。

  希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。
  时间复杂度：与增量有关，Hibbard增量为O($N_{3/2}$)。（亚二次时间界）
  希尔排序是不稳定的。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
	/**
     * 希尔排序：从大到小
     * Hibbard增量：1,3,7,...,2^k-1
     */
    public class ShellSort extends Sort{
    public static void sort(int[] a){
        int N = a.length;
        int maxK = (int)(Math.log(N + 1)/Math.log(2));
        for (int k = maxK; k >= 1; k--){
            int gap = (int) Math.pow(2, k) - 1;
            // 将数组变成gap有序
            for (int i = gap; i < N; i++){
                // 将a[i]插入到a[i-gap],a[i-2*gap],a[i-3*gap]...子数组之中
                for (int j = i; j >= gap; j-=gap){
                    if (a[j] > a[j - gap]){
                        swap(a, j, j-gap);
                    }
                }
            }
            System.out.println("------"+gap+"排序后-------");
            print(a);
        }
    }
}

感谢:http://www.cnblogs.com/skywang12345/p/3597597.html