黑马程序员技术交流社区

标题: 关于毕向东老师第04天-05视频的一个问题 [打印本页]

---

作者: 夏凡    时间: 2013-3-16 17:04
标题: 关于毕向东老师第04天-05视频的一个问题


毕老师在讲数组的“选择排序”的时候，顺便说了一句“最快的排序算法是希尔排序”，但是我查了一下资料，“快速排序”应该才是目前性能最好的排序算法，求解释

---

作者: 徐鸿燕    时间: 2013-3-16 17:27


百度百科：希尔排序

关于这个算法的话，涉及到时间复杂度，这个还不是我们初学者理解的时候。

---

作者: HM汪磊    时间: 2013-3-16 17:40
不同排序方法针对不同情况效率是不同的：
（1）从平均时间复杂度来考虑
   直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。
  （2）从最好的时间复杂度考虑
直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同
（3）从最坏的时间复杂度考虑
快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。

---

作者: 陈丽莉    时间: 2013-3-17 19:37
一个是最快的，一个是性能最好的，这不一样的。
性能是综合的，比如稳定性啊，占空间内存多少之类。而快是单纯形容速度的。
若还有问题，请继续追问；没有的话，请将帖子分类改成【已解决】~

---

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

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