学过数据结构的都知道，快排被认为是效率最高的排序方式，而且使用也是最广泛的，可是毕老师在视频中为什么会说希尔排序是效率最高的，快排和希尔排序到底哪个快！

快排效率高是高在 对无序数列排序会相对高，而希尔的时间复杂度是稳定的 数据越多越能体现他的高效

fantacyleo 发表于 2015-4-27 13:40
那得多核处理器并行才有意义。但是快排被广泛采用应该早于多核处理器的普及 ...

这你都知道，真是太强了，我也只是看到有人在博客说过，也不太清楚！真是太感谢了！学习了很多东西！

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

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

还没有看过算法。。。。

小栀子 发表于 2015-4-26 22:37
学习了，一直用的都是快排除非制定排序算法

没看懂！

学习了，一直用的都是快排除非制定排序算法

fantacyleo 发表于 2015-4-26 18:02
抱歉，是我记错了，快排也是不稳定的。jdk中Collections.sort是用归并实现稳定排序。堆排不常用应该不是 ...

我在网上看到有网友说是因为快排之所以快是使用了分治思想，各子问题都可以独立运行！

希尔排序~

知来者之可追 发表于 2015-4-26 17:49
我觉得快速排序的效率更高

yes，I think so！

frankzheng329 发表于 2015-4-26 17:19
时间复杂度除了big O notation（upper bond）, 还有平均复杂度，也就是说对于各种数据的一个期望或者叫平均 ...

其实快排，堆排，归并排序平均时间复杂度是相同的，快排之所以快好像和分治有关！

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

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

我觉得快速排序的效率更高

时间复杂度除了big O notation（upper bond）, 还有平均复杂度，也就是说对于各种数据的一个期望或者叫平均值。这个是比最大复杂度更为有效的衡量算法的方法。不过是比较难算的，需要很强的数学基础。

希尔排序

fantacyleo 发表于 2015-4-26 13:19
如果空间无限，根据排序的key直接放入数组在时间上显然是最快的。快排在worst-case也是O(n^2)，跟冒泡、选 ...

说得很好！不过我记得没错的话，快排也是不稳定排序，堆排的时间复杂度与快排相同，空间复杂度要小于快排，不懂，为什么快排会快！

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

IDhmpj 发表于 2015-4-26 12:46
没学过数据结构，目前只会冒泡

抽空可以看看，对学习编程还是很有帮助的

晓声 发表于 2015-4-26 12:06
希尔排序在面对数据量庞大的时候排序能力要在快排之上。其实在比如限量的少数据（100之内）的时候两者看不 ...

应该是快排在数据量庞大时要优于shell排序

没学过数据结构，目前只会冒泡