希尔排序运行时间过长

来源：2-4 希尔排序法的性能

Star3327752

2022-08-19 11:40:26

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多秒。。。为啥啊，能帮我分析一下吗

写回答

1回答

liuyubobobo

2022-08-19

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

========

对小数组的插入排序过程，内循环需要这个 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 行，都请再仔细理解一遍）。

继续加油！：）

hiuyubobobo

htar3327752

hp>我更新在了原回答中。继续加油！：）

h022-08-20

共2条回复

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2603 学习 · 1086 问题

查看课程

相似问题

快速排序法:空间复杂度O(1),原地和栈使用空间的定义是否有矛盾？

回答 1

冒泡排序法的时间复杂度

回答 1

老师您看一下这样写对吗？看您第四层循环的排序那里不是很理解，所以自己改写了一下

回答 1

老师冒泡排序移动次数为什么时3*n(n-1)/2,移动次数和交换次数有什么区别

回答 1

请问老师堆排序的测试用例

回答 1

打开慕课网App查看更多内容