0

我在 C 中实现了 Shell 排序，它只比冒泡排序快 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

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

4

2 回答 2

0

我会说这是您的实施的“问题”。

shellsort 的棘手之处在于，对于要排序的给定 n 值序列，有一组间隙将导致 shellsort - 对于一般情况 - 优于所有其他间隙集 - 或就此而言的标准算法* . 不太好的差距将导致性能低迷甚至糟糕。

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

正如我在这里所写的那样，评估一组差距以找到最好的差距是很棘手的（尤其是对于大型值集）。

  • 测试 n<=16 的值集

___________________ 编辑 ___________________

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

于 2020-10-13T12:39:52.507 回答
0

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

好的，我更改了实现，在 Shell 排序期间使用插入排序逻辑对子向量进行排序，所以现在它按预期执行 - LynnXe

于 2016-08-05T06:32:15.267 回答