首页 文章

为什么不总是使用堆排序[重复]

提问于
浏览
63

这个问题在这里已有答案:

Heap Sort 排序算法似乎具有O(nlogn)的最差情况复杂度,并且使用O(1)空间进行排序操作 .

这似乎比大多数排序算法更好 . 那么,为什么不总是使用Heap Sort作为排序算法(为什么人们使用排序机制,如Merge sort或Quick sort)?

此外,我看到人们使用Heap排序中的“不稳定”一词 . 这意味着什么?

5 回答

  • 9

    稳定排序可维护具有相同键的项的相对顺序 . 例如,假设您的数据集包含具有员工ID和名称的记录 . 最初的订单是:

    1, Jim
    2, George
    3, Jim
    4, Sally
    5, George
    

    您想按名称排序 . 稳定排序将按此顺序排列项目:

    2, George
    5, George
    1, Jim
    3, Jim
    4, Sally
    

    请注意,“George”的重复记录与初始列表中的重复记录的顺序相同 . 与两个“吉姆”记录相同 .

    不稳定的排序可能会安排这样的项目:

    5, George
    2, George
    1, Jim
    3, Jim
    4, Sally
    

    堆不稳定,因为堆上的操作可以更改相等项的相对顺序 . 并非所有Quicksort实现都是稳定的 . 这取决于您如何实现分区 .

    虽然Heapsort的案例复杂性最差 O(n log(n)) ,但并未考虑到这一点 . 在Heapsort vs. Quicksort的情况下,事实证明有些方法(例如,中位数为5)使Quicksort的最坏情况非常罕见 . 此外,维护堆不是免费的 .

    给定一个具有正态分布的数组,Quicksort和Heapsort都将在 O(n log(n)) 中运行 . 但是Quicksort的执行速度会更快,因为它的常数因子小于Heapsort的常数因子 . 简单来说,分区比保持堆快 .

  • 0

    Heap Sort 的最坏情况复杂度为 O(n log(n)) . 然而实证研究表明,通常 Quick Sort (以及其他排序算法)比堆排序快得多,尽管其最坏情况的复杂性是 O(n²)http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort3.html

    此外,来自维基百科上的quick sort article

    quicksort最直接的竞争对手是heapsort . Heapsort的最坏情况运行时间总是为O(n log n) . 但是,假设heapsort平均比标准的就地快速排序慢一些 . 这仍然是辩论和研究,一些出版物表明相反 . [13] [14] Introsort是quicksort的一种变体,当检测到坏的情况时切换到heapsort以避免quicksort的最坏情况运行时间 . 如果事先知道heapsort是必要的,直接使用它将比等待introsort切换到它更快 .

    但是,快速排序不应该用于需要保证响应时间的应用程序!

    Stackoverflow上的源:Quicksort vs heapsort

  • 107

    没有银弹......

    只是提到我还没有看到的另一个论点:

    如果您的数据集非常庞大并且不适合内存,那么合并排序就像魅力一样 . 它经常用于集群,其中数据集可以跨越数百台机器 .

  • 6

    稳定的排序算法使用相同的密钥保持记录的相对顺序

    有些应用程序喜欢这种稳定性,大多数都不关心,例如Google就是你的朋友 .

    至于你断言“人们使用排序机制,如合并排序或快速排序”,我敢打赌,大多数人使用他们语言中的任何内容,并没有考虑排序算法那么多 . 那些自己动手的人可能没有听说过堆排序(最后是个人经历) .

    最后也是最大的原因是不是每个人都想要一个排序堆 . 有些人想要排序列表 . 如果普通Joe Programmer的老板说“排序这个列表”,Joe说“这是你从未听说过的堆数据结构,老板!”,Joe的下一次绩效评估不会那么好 .

  • 0

    当我在80年代中期在Tandem Non-Stop计算机上工作很短时间时,我注意到系统内核排序例程是HeapSort,正是因为它提供了有保证的NlogN性能 . 我不知道有没有理由使用它的人,所以我不知道它在实践中是如何运作的 . 我喜欢heapsort,但是除了上面提到的缺点之外,我听说过它很难使用现代记忆,因为它可以让所有地方都能进行内存访问,而快速排序甚至是小基数排序都会结束 . 混合相对少量的顺序读写流 - 因此缓存更有效 .

相关问题