shell排序算法写错了 about cs-notes

[CyC2018]

@keqizwl 没有错的

[CyC2018]

@keqizwl

import java.util.Arrays;

public class Shell {
    public static void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1; // 1, 4, 13, 40, ...
        }
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static boolean less(Comparable x, Comparable y) {
        return x.compareTo(y) < 0;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 3, 2, 4, 8, 7, 0};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

[0, 1, 2, 3, 4, 7, 8]

[keqizwl]

排序没错，因为当h为1的时候就是插入排序，肯定能排正确，但是算法不是正确的shell算法，你可以搜索下shell算法实现，对比下。

[CyC2018]

@keqizwl 麻烦给以下比较权威的资料，我找到的方法都是这么实现的。

[keqizwl]

不好意思，是我弄错了，你实现是对的