希尔排序

问题描述

       实现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 --;
        }

    }
}