Leetcode: 【每日一题】- 2020-06-10 - 堆排序和快速排序

[azl397985856]

堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法，其中 n 为数据规模。

那么两者谁更快呢？ 为什么？

[Liu821218213]

快排最坏情况下是O(n^2)，平均和最好是O(nlogn) ，堆排序始终为O(nlogn)，还是堆排序快吧

[feikerwu]

单纯从算法复杂度分析，快排和堆排的时间复杂度都是 $O(n*logn)$, 最坏情况下快排可能会达到$O(n * n)$, 但是真正在机器跑起来，快排是比堆排快的，从大多数语言自带的公共库的 sort 算法都是 qsort，可见一斑，快排比堆排快主要有两点:

1. 快排的比较次数比堆排少，编译出来的执行指令少
2. 快排执行时在计算机架构上更有效率

以下是具体分析，

1. 快排通过选定基准 pivot, 在做 value 和 pivot 一次比较之后，value 被分到 pivot 左边或者右边，这意味着，任意两个数最多只需要比较一次，另外如果有 a < pivot，b > pivot， 那么 a 和 b 之间不会再发生比较。

2. 目前的绝大多数计算机架构中，cpu 读写数据的流程都是 CPU > 寄存器 > Cache(多级高速缓存) > 内存 > 硬盘， 其中 Cache 的读写速度远大与内存，由于造价成本高，Cache 的存储一般做的很小。Cache 里一般会放读写频率高的数据，或者将会读取的数据（比如有序的内存数据），在做堆排序的时候，我们的比较数据是 arr[i] 和 arr[i + 1], 当数组和 i 足够大时，相当与在取数组前半部分和后半部分的数做比较，享受不到 Cache 这种架构带来的效率提升。而快排，每次读写都是顺序取下一个数，判断了 arr[i] 和 pivot 的大小，下一次比较的就是 arr[i+1], 所以每次读写只需要从内存取一个 block 的值到 Cache 中，CPU 之后都可以从 Cache 中读写，利用了高速缓存，会更快。

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.