我已经用 C 实现了希尔排序，它只比冒泡排序快 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 种希尔排序和冒泡排序的变体。这四种变体中的三个具有相似的计时属性；第四个比其他三个差得多。然而，当排序大小为 1000 时，3 个 shell 排序需要不到 100μs，而慢速排序需要不到 600μs，冒泡排序需要不到 900μs，但在大小为 10,000 时，时间在 1-2ms 与 70ms 与 142ms 之间变化，当大小为 100,000 时，时间在 14-30 毫秒、8.6 秒和 18 秒之间变化。因此，其中一种希尔排序的速度大约是冒泡排序的一半，但其他排序要好得多。 – 乔纳森·莱夫勒
好吧，我改变了实现，在希尔排序期间使用插入排序逻辑对子 vector 进行排序，所以现在它按预期执行 - LynnXe
关于c - 希尔排序仅比冒泡排序快 3 倍？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38540118/