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

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

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

学习了，谢谢啊！

表示只会冒泡

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

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

希尔排序在面对数据量庞大的时候排序能力要在快排之上。其实在比如限量的少数据（100之内）的时候两者看不出来的

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

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

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

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

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

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

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

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

希尔排序

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

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

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

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

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

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

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

yes，I think so！

希尔排序~

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

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

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