希尔排序运行时间过长

ShellSort {
    (){}

    <Comparable<>> ([] data){
        h= data./(h>=){
            (start=start<hstart++){
                (i=start+hi< data.i=i+h){
                    t=data[i]j(j=ij-h>=j=j-h){
                        (data[j].compareTo(data[j-h])<){
                            (datajj-h)}
                    }
                }
            }
            h=h/}
    }

    <> (arr[]ab){
        temp= arr[a]arr[a]=arr[b]arr[b]=temp}

    (String[] args) {
        startTime=System.()Integer arr[]=Test.()ShellSort.(arr)endTime=System.()time =(endTime-startTime)/System..println(+time+)}
}

问题描述：

老师我的希尔排序运行10w需要20多秒。。。为啥啊，能帮我分析一下吗

Star3327752 2022-08-19

源自：冒泡排序，希尔排序和排序算法大总结 2-4 希尔排序法的性能

收起

1回答

liuyubobobo 2022-08-19 12:14:40

慕课网的问答区代码显示有问题，我看不到你的完整代码。请在评论里再把完整代码贴一下，谢谢。

========

对小数组的插入排序过程，内循环需要这个 else break：

for (j=i;j-h>=0;j=j-h){
    if (data[j].compareTo(data[j-h])<0){
        swap(data,j,j-h);
    }
    else break; // 需要这个 else break
}

这个 else break 非常关键，是插入排序面对有序数组能成为 O(n) 算法的核心。而插入排序面对有序数组是 O(n) 的，则是希尔排序的核心。（逐渐让数组有序）。

请你根据这个例子，再仔细体会一下插入排序算法的运行流程，以及逻辑的书写。

可以参考课程代码：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/04-Insertion-Sort/03-Insertion-Sort-Optimized/src/InsertionSort.java

（课程给出了两个写法，无论是 12-16 行，还是 18-19 行，都请再仔细理解一遍）。

继续加油！：）

收起回答

提问者 Star3327752 #1

package 排序;

public class ShellSort {
    private ShellSort(){}

    //做一个希尔排序的算法
    //外循环对一个数组进行分组，每一组的元素个数为h=length/2
    //直到h<1的时候停止分组，最后一次的h为1。h为多少，就有多少个小数组
    //对于每一组元素都会进行一次插入排序计算，这组元素的数组为[data,data+h,data+2h...]
    public static <E extends Comparable<E>> void Sort(E[] data){
        int h= data.length/2;//首先计算第一次数组的h值
        //开始外循环遍历
        while(h>=1){
            //开始内循环遍历//因为h为多少，就有多少个小数组，这个内循环是找出每个小数组的开头
            for (int start=0;start<h;start++){
                //找到每个小数组之后开始对小数组进行排序
                //对[data,data+h,data+2h...]进行排序
                for (int i=start+h;i< data.length;i=i+h){
                    E t=data[i];
                    int j;
                    //现在数组为[data,data+h,data+2h...]
                    //然后从data+h开始向后循环遍历查找
                    for (j=i;j-h>=0;j=j-h){
                        if (data[j].compareTo(data[j-h])<0){
                            swap(data,j,j-h);
                        }
                    }
                }
            }
            h=h/2;
        }
    }

    public static <E> void swap(E arr[],int a,int b){
        E temp= arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }

    public static void main(String[] args) {
        long startTime=System.nanoTime();
        //运行程序
        Integer arr[]=Test.Generate_Unordered_Array(10001,100000);
        ShellSort.Sort(arr);
        //运行结束
        long endTime=System.nanoTime();
        double time =(endTime-startTime)/1000000000.0;
        System.out.println("\ntime="+time+"s");

//        long startTime2=System.nanoTime();
//        //运行程序
//        Integer arr2[]=Test.Generate_Unordered_Array(100000,10000);
//        InsertSort.Sort(arr2);
//        //运行结束
//        long endTime2=System.nanoTime();
//        double time2 =(endTime2-startTime2)/1000000000.0;
//        System.out.println("\n+time2="+time2+"s");
//        //运行结束
    }
}

2022-08-19 14:11:36