希尔排序

|
算法

希尔排序是插入排序的一种，又称缩小增量排序，是对插入排序的一个改进。

原理

对于一个给定的长度为n的数组，希尔排序是根据一个变量h（n>h>=1）把数组分为多个子分组，每个分组使用插入排序排好，h逐渐递减至1。

h的取值没有一个明确的规定，比如你可以每次取上一次的一半，第一次为数组长度的一半，也可以使用三分之一。

代码

1
2
3
4
5
6
7
8
9
10
11
12
public void sort(Comparable[] arr) {
    int n = arr.length;
    int h = n / 2 >= 1 ? n / 2 : 1;
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && less(arr[j], arr[j - h]); j -= h) {
                exch(arr, j, j - h);
            }
        }
        h = h / 2;
    }
}