希尔排序（java）

• 将原序列分为若干个自序列，此时对每个子序列的数据将会较少，然后在这些子序列中分别进行直接插入排序，当整个序列都基本有序的时候，再对全体记录进行一次直接插入排序。
• 所谓基本有序，就是最小的关键字基本在前面，大的关键字基本在后面，不大不小的在中间。
• 将相距某个"增量"的记录组成一个子序列，这样才能保证在自序列内分别进行直接插入排序后得到的结果是基本有序，而不是局部有序。
• 时间复杂度：O[nlogn] ~ O(n^2)，为不稳定的排序算法

代码

void hillSort(int[] arr){
    if (arr == null || arr.length == 0) {
        return;
    }
    int k = arr.length;
    while (k > 1) {
        // 增量k，增量值为 k/3 + 1是个经验值。
        // 增量的最后一个值必须为1，这样才能保证排序的正确性。
        k = k / 3 + 1;
        // 对子序列执行直接插入排序
        for (int i = k; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i;
            while (j >= k && (arr[j - k] > tmp)) {
                arr[j] = arr[j - k];
                j = j - k;
            }
            arr[j] = tmp;
        }
    }
}