如果空间无限，根据排序的key直接放入数组在时间上显然是最快的。快排在worst-case也是O(n^2)，跟冒泡、选择一样。所以说算法效率高低要先看说的是时间效率还是空间效率，以及约束条件。
就平均情况来说，shell排序是比不上快排、堆排的，我试过java上用shell排100w个double就明显感觉到慢了。而且，shell是不稳定排序。不过shell排序实现非常简单，不需要额外存储空间，十万个以下的元素排序还是很轻松的。

qian0217wei 发表于 2015-4-26 16:46
说得很好！不过我记得没错的话，快排也是不稳定排序，堆排的时间复杂度与快排相同，空间复杂度要小于快排 ...

抱歉，是我记错了，快排也是不稳定的。jdk中Collections.sort是用归并实现稳定排序。堆排不常用应该不是理论原因而是基于现实考虑。堆排对缓存的利用率比较差，因为可能要访问整个堆，很可能miss。快排基本上就是访问相近元素，hit的概率比较大

qian0217wei 发表于 2015-4-26 18:26
我在网上看到有网友说是因为快排之所以快是使用了分治思想，各子问题都可以独立运行！ ...

那得多核处理器并行才有意义。但是快排被广泛采用应该早于多核处理器的普及