java - 如何使用经验派生的增量进行 shell 排序？

Question

根据维基百科的文章，我正在尝试使用经验派生的增量来实现 Shell 排序以执行 h 排序：

1,4,10,23,57,132,301,701

目前，我正在使用h = 3*h + 1执行排序，这是我的实现：

    public class Solution
{
    private static final int arr[] = {9,4,5,1,2,8,7,6,12,45,21,34,1,2,3};
    public static void main(String[] args)
    {
        int N = arr.length;
        int h = 1;
        while(h<N/3)
            h = 3*h + 1;
        while(h>=1)
        {
            for(int i=h;i<N;i++)
            {
                for(int j=i;j>=h && arr[j-h]>arr[j];j-=h)
                {
                    int temp = arr[j-h];
                    arr[j-h] = arr[j];
                    arr[j] = temp;
                }
            }
            h/=3;
        }

        for(int x:arr)
            System.out.println(x);

    }
}

现在，这很好地完成了任务。但问题是，如果我要通过使用经验派生的序列来执行 h 排序来实现 shell 排序，我应该如何根据数组的大小选择我必须使用的增量？

Answer 1

将经验导出的序列存储在数组中，并找到该数组中小于数据数组大小的最后一个元素。

例如，如果数据大小为 500，则第一步必须得到 301