See Chrome Devtools!

快速排序

多线程应该也可用。

• 稳定性

  不稳定（都瞎 jb 飞了）

• 复杂度

  • 时间复杂度

    O(n(log n)) ~ O(n^2)

    时间复杂度低因为主逻辑流程就是不断二分，最终形成一个深度为 log n 的调用堆栈，堆栈每层遍历一整遍 n，时间复杂度就是 n(log n) 级别。

    • 最好情况

      每次选择标记位都刚刚好选到了中间的值，那么调用堆栈的深度就刚刚好是 log n。

    • 最差情况

      如果每次选择标记位都刚好选到了最小值或者最大值，那么就意味着处理后两部分的大小分别为 n - 1 和 1，这样的话整个调用堆栈的深度就会从 log n 增加到 n（因为每次只减少 1）。

      但是这种情况十分罕见，因为需要在一个 n 长度的数组中，每次都选中最小的值，具体就不算了，概率是相当小的。

  • 空间复杂度

    O(log n)

    主要是递归导致的（递归深度 log n，每一层一个缓存变量）

• 原理

  选一个基准值，把比他大的放到它前面，比他小的放到它后面，最后把它自己插到中间，然后继续二分它左右的两部分，在内部重复这一流程，直到分割长度为 1 或者 0。

• 优化方法

  1. 纯粹的随机选 key 可以解决原数组已排序问题，但如果整个数组全部相同，还是会有问题。
  2. 可以使用三数取中，就是在三个数中（这时再使用随机数来找这三个数有点多余了，直接头尾和中间就好了）选定中间的值做区分值，进行数据处理。
  3. 当数组段小于一定长度时使用插排（性能提升不大）。
  4. 聚集相等元素，在排序过程中，遇到与本值大小相同的值，直接放在数组尾，等本次过完后，直接把这些相同的值交换过来，这样可以减少许多次相同值的排序。
  5. 尾递归优化（编译器会做）。