c - 希尔排序仅比冒泡排序快 3 倍？

Question

我已经用 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

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

Answer 1

我有一个排序基准测试程序，内置了 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