Java实现Shell(希尔)排序

发表于 更新于

如需下载源代码，请到github：https://github.com/wahyd4/java-sorting

Shell(希尔)排序是建立在直接插入排序基础上之上的，只是它会先将这个数组按照一定的间隔分成若干个小数组先进行直接插入排序。以先比较较远的元素，再比较较近的元素，最后比较相邻的元素。可以逐步减小比较的次数。其时间复杂度优于直接插入排序。

更多的信息请查看百度百科或者维基百科的介绍。下面上希尔排序的代码：

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
26
27
28
29
30
31
public class ShellSort {

    // 定义需要排序的数组
    private static int[] data = { 16, 20, 1, 6, 3, 19, 7, 14, 5, 60, 29, 40 };

    public static void shellSort(int[] data) {
        //获取数组长度
        int length = data.length;
        // 首先进行分组,每次组中元素为之前1/2。
        for (int gap = length / 2; gap > 0; gap = gap / 2) {
            // 对每个组进行插入比较
            for (int i = gap; i = gap && data[j] < data[j - gap]; j = j- gap) {
                    //缓存下表最大的那个数
                    int temp = data[j];
                    //将两数交换位置，将较大数保存到下标最大的位置。
                    data[j] = data[j - gap];
                    data[j - gap] = temp;
                }

            }
        }
    }

    public static void main(String[] args) {
        shellSort(data);
        for (int flag : data) {
            System.out.print(flag + " ");
        }
    }

}

虽然代码里面希尔排序是三层循环，但是只有中间层循环才是n数量级，外层循环为lbn,最里程循环也远小于n.平均时间复杂度还优于直接插入排序。