Shell排序只比冒泡排序快3倍？

Question

我用C语言实现了Shell排序，它只比Bubble排序快3倍。以下是我的排序持续时间(秒)：

For list of 100 integers:
BubbleSort: 0.000333
ShakeSort: 0.000282
QuickSort: 0.000048
QuickSort_Iter: 0.000063
InsertionSort: 0.000188
ShellSort: 0.000150

For list of 1000 integers:
BubbleSort: 0.028191
ShakeSort: 0.019354
QuickSort: 0.000435
QuickSort_Iter: 0.000528
InsertionSort: 0.011917
ShellSort: 0.003664

For list of 5000 integers:
BubbleSort: 0.241116
ShakeSort: 0.222127
QuickSort: 0.001306
QuickSort_Iter: 0.001592
InsertionSort: 0.151656
ShellSort: 0.091002

For list of 10000 integers:
BubbleSort: 0.959580
ShakeSort: 0.872648
QuickSort: 0.002877
QuickSort_Iter: 0.003379
InsertionSort: 0.601329
ShellSort: 0.350866

这是正常的，还是可能是我的实现有问题？

Answer 1

我有一个排序基准程序，内置了shell排序和冒泡排序的4个变体。四个变种中有三个具有相似的计时属性；第四个变种比其他三个变种差得多。但是，当排序大小为1000时，3种shell排序所需时间不到100µs，而慢速shell排序所需时间不到600µs，气泡排序所需时间不到900µs，但在大小为10,000时，时间在1-2ms与70ms与142ms之间变化，而在大小为100,000时，时间在14-30ms与8.6s与18s之间变化。因此，其中一种shell排序的速度大约是冒泡排序的一半，但其他排序的速度要好得多。--乔纳森·莱弗勒

好的，我更改了实现，在Shell排序过程中使用插入排序逻辑对子向量进行排序，因此现在它的执行情况与预期一致- LynnXe

Answer 2

我会说这是你的实现中的一个“问题”。

shellsort的棘手之处在于，对于要排序的n个值的给定序列，只有一组间隙会导致shellsort -在平均情况下-优于所有其他间隙组-或标准算法*。不太好的差距集将导致平淡无奇甚至是糟糕的性能。

Knuth，Sedgewick，Ciura和其他人的序列并不是那么好，但让我们面对它，考虑到我们对算法的秘密知之甚少，找到给定n的最佳间隔集是一项艰巨的任务。

正如我在关于here的文章中所写的那样，评估多组间隙以找到最好的间隙是一件棘手的事情(特别是对于较大的值集合)。

• 测试了n<=16

中的值集

___________________编辑___________________

我建议您尝试n=100的以下间隔集：{99,60,16,4,1}，我认为这将改善您的100整数外壳排序结果。