问题描述
实现Shell排序，对给定的无序数组，按照给定的间隔变化（间隔大小即同组数字index的差），打印排序结果，注意不一定是最终排序结果！
输入
输入第一行表示测试用例个数，后面为测试用例，每一个用例有两行，第一行为给定数组，第二行为指定间隔，每一个间隔用空格隔开。
输出
输出的每一行为一个用例对应的指定排序结果。
示例输入
1
49 38 65 97 76 13 27 49 55 4
5 3
示例输出
13 4 49 38 27 49 55 65 97 76
思路
参照希尔排序的思想
代码1
import java.util.Scanner;
public class Main {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int casesnum = sc.nextInt();
sc.nextLine();
while(casesnum>0){
String[] temp = sc.nextLine().split(" ");
int[] inputs = new int[temp.length];
for(int i=0;i<inputs.length;i++)
inputs[i] = Integer.parseInt(temp[i]);
String[] temp2 = sc.nextLine().split(" ");
int[] stride = new int[temp2.length];
for (int i=0;i<stride.length;i++)
stride[i] = Integer.parseInt(temp2[i]);
for (int i=0;i<stride.length;i++)//每个间隔
for (int j=0;j<stride[i];j++)//间隔内每个平移
for (int k=j+stride[i];k<inputs.length;k+=stride[i]){//一轮中所有待排序数
for (int l=j;l<k;l+=stride[i]){//一轮排序中所有已排序数
if (inputs[k]<inputs[l]){
int t = inputs[k];
for (int m=k-stride[i];m>=l;m-=stride[i]){
inputs[m+stride[i]] = inputs[m];
}
inputs[l] = t;
break;
}
}
}
for (int i=0;i<inputs.length;i++){
System.out.print(inputs[i]);
if(i<inputs.length-1)
System.out.print(" ");
else
System.out.println();
}
casesnum --;
}
}
}
代码2
上述方法for循环太多，代码显得复杂。更简洁的写法如下所示，其思想是每次并不追求把相同颜色的数字（如图1所示）都排好序，而是交叉地进行：对于每一个间隔gap，从下标i=gap开始每次加1直至最后，考察当前数字是否需要插到前面（如图2）
图1
图2.纠正：应该是从5开始，下标是4
import java.util.Scanner;
public class Main {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int casesnum = sc.nextInt();
sc.nextLine();
while(casesnum>0){
String[] temp = sc.nextLine().split(" ");
int[] inputs = new int[temp.length];
for(int i=0;i<inputs.length;i++)
inputs[i] = Integer.parseInt(temp[i]);
String[] temp2 = sc.nextLine().split(" ");
int[] stride = new int[temp2.length];
for (int i=0;i<stride.length;i++)
stride[i] = Integer.parseInt(temp2[i]);
for (int m=0;m<stride.length;m++){
int gap = stride[m];
for(int i=gap;i<inputs.length;++i)
{
int tmp=inputs[i];
int j=i;
for(;j>=gap&&tmp<inputs[j-gap];j-=gap)
{
inputs[j]=inputs[j-gap];
}
inputs[j]=tmp;
}
}
for (int i=0;i<inputs.length;i++){
System.out.print(inputs[i]);
if(i<inputs.length-1)
System.out.print(" ");
else
System.out.println();
}
casesnum --;
}
}
}
