黑马程序员技术交流社区

标题: 快速排序和希尔排序哪个效率更高 [打印本页]

作者: qian0217wei 时间: 2015-4-26 10:05
标题: 快速排序和希尔排序哪个效率更高
学过数据结构的都知道，快排被认为是效率最高的排序方式，而且使用也是最广泛的，可是毕老师在视频中为什么会说希尔排序是效率最高的，快排和希尔排序到底哪个快！

作者: yapo 时间: 2015-4-26 10:12
希尔排序比快排要慢一些，当数据量达到 500万以上时候，会越来越明显。至于冒泡、选择、直接插入，那当然就更慢了，当数据达到500万以上时候，象乌龟，以为电脑死了。另外快速排序复杂度是不定的，取决于要排序的队列，如果队列是 6，5，4，3，2，1，排序就很快，如果队列是已经排序完的，比如 1，2，3，4，5，6，复杂度就是 n平方，会非常耗时 2. 希尔排序无论队列是什么情况，复杂度都是一样。所以：希尔排序的理论复杂度比快排要好实践中广泛使用快排是因为在实践中它最快

作者: qian0217wei 时间: 2015-4-26 10:33

yapo 发表于 2015-4-26 10:12
希尔排序比快排要慢一些，当数据量达到 500万以上时候，会越来越明显。至于冒泡、选择、直接插入，那当然就 ...

学习了，谢谢啊！

作者: lslkkk 时间: 2015-4-26 10:35
表示只会冒泡

作者: qian0217wei 时间: 2015-4-26 11:30

lslkkk 发表于 2015-4-26 10:35
表示只会冒泡

我也只知道算法思想，具体怎么实现也不会。

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

作者: IDhmpj 时间: 2015-4-26 12:46
没学过数据结构，目前只会冒泡

作者: qian0217wei 时间: 2015-4-26 13:00

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

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

作者: qian0217wei 时间: 2015-4-26 13:06

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

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

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

作者: qian0217wei 时间: 2015-4-26 16:46

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

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

作者: ayl648989 时间: 2015-4-26 17:11
希尔排序

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

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

作者: fantacyleo 时间: 2015-4-26 18:02

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

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

作者: qian0217wei 时间: 2015-4-26 18:19

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

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

作者: qian0217wei 时间: 2015-4-26 18:21

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

yes，I think so！

作者: kolyneh 时间: 2015-4-26 18:23
希尔排序~

作者: qian0217wei 时间: 2015-4-26 18:26

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

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

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

作者: qian0217wei 时间: 2015-4-27 13:18

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

没看懂！

作者: 精湛学术 时间: 2015-4-27 13:27
还没有看过算法。。。。

作者: fantacyleo 时间: 2015-4-27 13:40

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

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

作者: qian0217wei 时间: 2015-4-27 14:05

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

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

作者: Zack 时间: 2015-4-27 17:35
快排效率高是高在对无序数列排序会相对高，而希尔的时间复杂度是稳定的数据越多越能体现他的高效

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2