Shell排序的时间复杂度
来源：3-5 快速排序法 - Quick Sort
P番薯oTATo
2019-12-31
老师，快排和归并排序的结果都没什么问题，但我用Shell排序测试了100w的数据量，发现竟然还保持在和快排以及归并排序的水准。
Test with random array, size = 1000000, randome range [0, 1000000]
Merge Sort: 0.116 S
Merge Sort EX: 0.114 S
Merge Sort BU: 0.114 S
Quick Sort: 0.081 S
Shell Sort: 0.106 S
写回答
1回答
-
liuyubobobo
2019-12-31
是的哦，希尔排序就是这么快哦。
从复杂度的角度，希尔排序可以近乎看作是 O(nsqrt(n)) 级别的排序（不够精准，但绝不是 O(n^2)，从复杂度的角度，比 O(nlogn) 高一些）。
但是从具体代码实现上，由于没有递归调用，所以，实际性能会很快：）
继续加油！：）
00
相似问题
时间复杂度
回答 1
归并排序的时间复杂度是如何计算得出的？
回答 1