我在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
这是正常的，还是我的实现可能有问题？
我有一个排序基准测试程序，内置了shell排序和bubble排序的四个变体。四个变体中有三个具有相似的时序属性；第四个比其他三个差得多。然而，当排序大小为1000时，3种外壳排序所需时间不到100µs，而慢速外壳排序所用时间不到600µs，气泡排序所需的时间不到900µs，但在大小为10000时，时间在1-2ms与70ms与142ms之间变化，在大小为100000时，时间从14-30ms与8.6s与18s之间变化。因此，其中一种外壳排序的速度大约是泡沫排序的一半，但其他的要好得多Jonathan Leffler
好的，我改变了实现，在Shell排序过程中使用Insertion排序逻辑对子向量进行排序，所以现在它按预期执行–LynnXe
我会说它是一个"问题"；与您的实施。
shellsort的棘手之处在于，对于要排序的n个值的给定序列，有一组间隙会导致shellsord(在平均情况下(优于所有其他间隙集，或标准算法*。不太好的间隙集将导致性能低下甚至较差。
Knuth、Sedgewick、Ciura和其他人的序列并不那么好，但让我们面对现实，考虑到我们对算法的秘密知之甚少，在给定n的情况下找到最佳的间隙集是一项艰巨的任务。
正如我在这里所写的，评估差距集以找到最好的差距是很棘手的(尤其是对于大的值集(。
- 针对其中n<16
___________________编辑___________________
我建议您尝试以下一组n=100的间隙：{99,60,16,4,1}，我认为这将改进您的100整数shell排序结果。