如何使用经验派生的增量进行 shell 排序?
How to use the empirically derived increment for shell sort?
根据 Wikipedia 文章,我正在尝试使用经验派生的增量来实现 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排序,我应该如何根据数组的大小来选择必须使用哪个增量呢?
将根据经验导出的序列存储在数组中,并找到该数组中小于数据数组大小的最后一个元素。
比如数据量是500,第一步要得到301
根据 Wikipedia 文章,我正在尝试使用经验派生的增量来实现 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排序,我应该如何根据数组的大小来选择必须使用哪个增量呢?
将根据经验导出的序列存储在数组中,并找到该数组中小于数据数组大小的最后一个元素。
比如数据量是500,第一步要得到301