14 | 排序优化：如何实现一个通用的、高性能的排序函数？

精选留言(88)

• 

  刘強

  我们的教育让我们对标准答案的依赖太深了，让我们失去了独立思考的能力。深深的感受到了这一点。思考的过程比标准答案更重要，这句话才是关键。

  2018-10-22

   2

   280
• 

  Liam

  查看了下Arrays.sort的源码，主要采用TimSort算法, 大致思路是这样的：
  
  1 元素个数 < 32, 采用二分查找插入排序(Binary Sort)
  2 元素个数 >= 32, 采用归并排序，归并的核心是分区(Run)
  3 找连续升或降的序列作为分区，分区最终被调整为升序后压入栈
  4 如果分区长度太小，通过二分插入排序扩充分区长度到分区最小阙值
  5 每次压入栈，都要检查栈内已存在的分区是否满足合并条件，满足则进行合并
  6 最终栈内的分区被全部合并，得到一个排序好的数组
  
  Timsort的合并算法非常巧妙：
  
  1 找出左分区最后一个元素(最大)及在右分区的位置
  2 找出右分区第一个元素(最小)及在左分区的位置
  3 仅对这两个位置之间的元素进行合并，之外的元素本身就是有序的

  2018-10-22

  

   173
• 

  杨伟

  思考过程比答案重要这句话是不假，但是有答案来验证自己的思考是否准确在初学时期也很重要。
  
  学习知识每个人的理解会不同，有的人可能这么理解有的人可能那样理解。如果没有一个标杆，有些同学就会按照自己错误的理解继续学习下去。
  
  有了标准答案，同学就可以对照答案来反思自己的理解是否正确。也能够从别人的答案中看到更好的解答也是一种学习。
  
  当然自己偷懒不思考，依赖标准答案，那肯定是学不好的

  2018-10-22

  

   102
• 

  小确幸

  数据库里面的Order BY，用的是什么排序呢？

  2018-10-22

   3

   51
• 

  峰

  java1.8中的排序，在元素小于47的时候用插入排序，大于47小于286用双轴快排，大于286用timsort归并排序，并在timesort中记录数据的连续的有序段的的位置，若有序段太多，也就是说数据近乎乱序，则用双轴快排，当然快排的递归调用的过程中，若排序的子数组数据数量小，用插入排序。

  2018-10-22

  

   45
• 

  姜威

  总结：如何实现一个通用的高性能的排序函数？
  一、如何选择合适的排序算法？
  1.排序算法一览表
                   时间复杂度 是稳定排序？ 是原地排序？
  冒泡排序 O(n^2) 是 是
  插入排序 O(n^2) 是 是
  选择排序 O(n^2) 否 是
  快速排序 O(nlogn) 否 是
  归并排序 O(nlogn) 是 否
  桶排序 O(n) 是 否
  计数排序 O(n+k)，k是数据范围 是 否
  基数排序 O(dn)，d是纬度 是 否
  2.为什选择快速排序？
  1）线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。
  2）为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。
  3）同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。
  二、如何优化快速排序？
  导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下：
  1.三数取中法
  ①从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。
  ②如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。
  2.随机法：每次从要排序的区间中，随机选择一个元素作为分区点。
  3.警惕快排的递归发生堆栈溢出，有2中解决方法，如下：
  ①限制递归深度，一旦递归超过了设置的阈值就停止递归。
  ②在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。
  三、通用排序函数实现技巧
  1.数据量不大时，可以采取用时间换空间的思路
  2.数据量大时，优化快排分区点的选择
  3.防止堆栈溢出，可以选择在堆上手动模拟调用栈解决
  4.在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序
  5.用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致
  四、思考
  1.Java中的排序函数都是用什么排序算法实现的？有有哪些技巧？

  2018-10-22

   4

   26
• 

  李靖峰

  golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作不是一两句话可以描述出来，是基于首中尾中值的很复杂的变种

  2018-10-29

  

   24
• 

  蛐鸣

  看了一下，.NET里面的Array排序实现:
  1. 三个以内的，直接比较，交换进行实现
  2.大于3个小于16个的，用的是插入排序进行的实现
  3.对于大于16，并且深度限制是0的，用的是堆排序实现的
  4.对于大于15，并且深度限制不是0的，使用的是快速排序；然后快速排序分区使用的也是三数取中法

  作者回复: 👍

  2018-11-02

  

   21
• 

  Andrew 陈震

  老师，我有一个问题，关于递归太深导致堆栈溢出的问题。对于这个问题，您说一般有两种解决方法，一是设置最深的层数，如果超过层数了，就报错。对于这样的问题，我想排序一个数列，超过了层数，难道就不排了么？我看有留言说，stl中的sort默认是使用快排的，但当递归深度过大时 会转为使用归并排序。但是归并排序也是递归排序啊，如果两种排序都达到了最深层数怎么处理？另外，在排序之前，能否估算出排序是否超过最深层数呢？如果估算不出，那岂不是要先排一遍，发现超过层数，再换用别的。我的想法是设个阈值，不超过阈值，用一种，超过了，用另一种。
  
  第二种应对堆栈溢出的方法是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程。这个方法在您的几篇教程里都提到过，但是不详细，您能否稍微详细讲解一下。
  
  谢谢老师

  作者回复: 太深报错也没问题 不过不建议这么处理
  归并排序比较稳定 栈的深度是logn 非常小 所以不会堆栈溢出
  关于手动模拟栈 你可以看看qsort（）函数的实现

  2018-10-22

   1

   19
• 

  Jerry银银

  说说我觉得文章可能存在的一个问题，再借此问题，正好回答下思考题！
  ----------------------
  文章中有一段话，如下：
  "时间复杂度是 O(nlogn) 的排序算法不止一个，我们已经讲过的有归并排序、快速排序，后面讲堆的时候我们还会讲到堆排序。堆排序和快速排序都有比较多的应用，比如 Java 语言采用堆排序实现排序函数，C 语言使用快速排序实现排序函数。"
  这里说，”Java语言采用堆排序实现排序函数“，这句话是不是错误的？
  
  在JDK中，排序相关的主要是两个工具类：Arrays.java 和 Collections.java，具体的排序方法是sort()。这里要注意的是，Collections.java中的sort()方法是将List转为数组，然后调用Arrays.sort()方法进行排序，具体代码如下(留言中代码格式可能有点混乱，讲究看看，也可以自行参看List.sort())：
  default void sort(Comparator<? super E> c) {
          Object[] a = this.toArray();
          Arrays.sort(a, (Comparator) c);
          ListIterator<E> i = this.listIterator();
          for (Object e : a) {
              i.next();
              i.set((E) e);
          }
      }
  
  在Arrays类中，sort()有一系列的重载方法，罗列几个典型的Arrays.sort()方法如下:
  public static void sort(int[] a) {
       DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
   }
  
  public static void sort(long[] a) {
       DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  }
  
  public static void sort(Object[] a) {
          if (LegacyMergeSort.userRequested)
              legacyMergeSort(a);
          else
              ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
  }
  重载方法虽然多，但是从“被排序的数组所存储的内容”这个维度可以将其分为两类：
  1. 存储的数据类型是基本数据类型
  2. 存储的数据类型是Object
  第一种情况使用的是快排，在数据量很小的时候，使用的插入排序；
  第二种情况使用的是归并排序，在数据量很小的时候，使用的也是插入排序
   
  以上两种场景所用到的排序都是「混合式的排序」，也都是为了追求极致的性能而设计的。另外，第二种排序有个专业的名称，叫：TimSort(可以自行Wikipedia)
  
  

  作者回复: 👍 细心，新版本的jdk估计有优化吧，可以从代码中发现：
          if (LegacyMergeSort.userRequested)
              legacyMergeSort(a);
  
  legacy的实现确实是堆排序！

  2019-03-02

   1

   18
• 

  leo

  排序的思维导图链接：https://share.weiyun.com/5X17MG3

  2018-10-29

  

   10
• 

  等风来

  使用快排如何解决不稳定排序的问题?

  作者回复: 并没解决 所以qsort不稳定

  2018-10-22

  

   9
• 

  Random.nextName()

  Google v8中对QuickSort的实现是:
  数据规模在10以内的话使用快排;
  数据规模在10到1000之间时选择中点作为pivot进行快排;
  数据规模在1000以上时，每隔200到215个数选一个数，将选出来的数排序，选择中间值作为pivot进行快排；
  而且还有几个细节：
  1是折半的时候用的是位运算；
  2是每一次遍历都会分成小于pivot，等于pivot，大于pivot的三个区间；
  3是小于pivot和大于pivot这两个区间中数据规模比较小的会递归执行QuickSort，数据规模大的会先通过while循环减小数据规模。
  附上源码链接: https://github.com/v8/v8/blob/master/src/js/array.js

  2018-10-30

  

   8
• 

  学习爱好者

  王老师，总结8种排序算法的那个图，桶排序不一定是稳定排序吧？比如桶内排序用快排的时候

  作者回复: 嗯嗯 用归并或者插入排序就稳定了

  2018-11-05

  

   7
• 

  Liam

  关于快排递归过深的处理的疑惑，以及关于 STL 里的 std::sort 是怎么实现的，可以看我这篇博客：https://liam.page/2018/09/18/std-sort-in-STL/

  2018-10-22

  

   7
• 

  城

  qsort中为避免递归调用过深，所以在堆上模拟了栈。不知道是否是将递归调用，改写为循环非递归方式呢？

  作者回复: 是的

  2018-10-22

  

   7
• 

  AF

  老师，你之前讲的快排、归并，原理我都理解的很清晰，但是一旦到转换成代码的时候，感觉一脸懵逼，你最开始这是这样吗？

  作者回复: 是有点 毕竟代码是写给机器执行的 多看几遍 再自己默写默写

  2018-10-23

  

   6
• 

  落叶飞逝的恋

  老师，你好，我终于认真消化完了前面的知识，没有半点马虎，也给自己打个卡记录。
  关于思考题：
  查看了Java的Arrays.sort
  1.若数组元素个数总数小于47，使用插入排序
  2.若数据元素个数总数在47~286之间，使用快速排序。应该是使用的优化版本的三值取中的优化版本。
  3.若大于286的个数，使用归并排序。
  底层实现的代码比之前示范写的代码校验多，所以目前只能看到这，下面继续加油吧！

  作者回复: 👍

  2018-12-04

   1

   5
• 

  favorlm

  虽然说思考很重要，但是面试还是需要你实现一种算法。

  作者回复: 留言区点赞最高的就是答案

  2018-11-04

  

   5
• 

  24隋心所欲

  针对 Java 语言：
  
  1. 对于基本类型的数组，Java 采用的是双枢轴快速排序（Dual-Pivot Quicksort），这个算法是 Java 7 引入的。在此之前，Java 采用的是普通的快速排序，双枢轴快速排序是对普通快速排序的优化，新算法的实现代码位于类 java.util.DualPivotQuicksort 中。
  
  2. 对于对象类型，Java 采用的算法是 TimSort，TimSort 算法也是 Java 7 引入的。在此之前，Java 采用的是归并排序。TimSort 算法实际上是对归并排序的一系列优化，TimSort 的实现代码位于类 java.util.TimSort 中。
  
  3. 在这些排序算法中，如果数组长度比较小，它们还会采用效率更高的插入排序。

  2019-03-23

  

   4