排序算法的演进

前言

　　前段时间看到友商宣传他们打造了Go语言最快的排序算法，有些观点不敢苟同。为此，特意梳理了一下排序算法的演进，发现没有最快，只有更快。

排序算法谱系

　　考虑到算法的通用性，我们这里只讨论比较排序。比较排序算法有御三家，目前占据C位的快速排序极其子孙。当然，排序算法谱系庞大种类繁多，本文只关注其中的佼佼者，以便于大家理解。

朴素排序算法

冒泡排序

　　冒泡排序的原理很简单，就是不断调整相邻元素的顺序来达到排序的效果。冒泡算法的比较和移动操作都很多，快不了。

选择排序

　　选择排序的原理也很简单，就是不断选出剩下元素中的最值来实现排序。选择排序的数据移动是精准操作，比冒泡算法强。

插入排序

　　插入排序相对复杂一些，新加入元素要在已排序列里找到合适的位置插进去。由于插入位置可以通过二分查找获得，插入排序的比较次数远小于冒泡排序和选择排序。数据移动次数上选择排序占优，不过顺序数据移动的开销远不及比较，因此旧世代御三家中，插入排序往往是最快的。

高级排序算法

快速排序

　　快速排序（QuickSort）可以理解成一种批量冒泡排序，每个元素的浮沉不再取决于和相邻元素的比较，而是取决于和中枢元素的比较，每次浮沉也不再是一个身位，而是直接到达上下半区。风水轮流转，新世代御三家中，快速排序通常是最快的。

堆排序

　　堆排序是一种改进的选择排序，使用堆结构来优化选择过程。堆结构的层间操作需要两次比较和一次数据移动，更糟糕的是数据访问存在跳跃，正是这多一倍的比较次数和不规则的访存使得堆排序在新世代御三家中速度垫底，通常不及快速排序的四成。

归并排序

　　归并排序可以理解成一种批量插入排序，由于插入项本身也是有序的，数据移动可以一步到位，比较高效。可是，快速排序每轮操作只需要移动一半多的元素（上半区元素有一半本来属于上半区，不需要挪，下半区同理），因这半步之差，归并排序的性能逊于快速排序。

先进排序算法

Dual-Pivot Quicksort

　　双枢三分快排（Dual-Pivot Quicksort）为2009年问世的一种改进版快速排序，从Java 7开始为Java标准库的所采用。和经典快排不同的是，该算法引入两个中枢点将序列分成三段。这样做会有什么效果呢？此处有三重境界：

　　一、三分递归的深度只有二分的63%左右，直观感觉会赚。

　　二、由于三分操作比二分复杂很多，综合分析发现双枢三分快排无论是总比较次数还是总数据移动次数均多于经典快排，没有道理比经典快排更快。

　　三、对于现代计算机而言，数据操作最慢的过程是首次读入，读入后短时间内进行多次访问的情况下，由于数据在cache中开销并没有那么大。从第一层分析可知，三分确实可以比二分显著减少冷数据的访问。而第二层分析到的操作复杂度增加都是增加在热数据上面的，因此综合下来双枢三分快排还是可以比经典快排更快，尤其是在内存敏感型程序上（如Java和Go程序）。当然，这种胜利建立在双枢三分算法更擅长利用cache上，在某些嵌入式设备上可能并不成立。

　　2016年有人专门发paper分析过，感兴趣可以看一下：Why Is Dual-Pivot Quicksort Fast。

BlockQuicksort

　　又是2016年，团快排（BlockQuicksort）问世，尝试从比较操作上优化快排。Dual-Pivot Quicksort发现了冷数据访问比热数据访问更应该被重视，BlockQuicksort则指出比较其实不痛不痒，真正应该重视的是分支处理。对随机数据而言，排序中数据比较引起的分支几乎是不可预测的，非常讨厌，于是BlockQuicksort在这里引入了分支消除技术。什么是分支消除技术这里不展开叙述，从C/C++版BlockQuicksort能比经典快排快上一倍的结果看，其威力不容小觑。不过分支消除技术的实现和CPU指令集以及编译器都有紧密关系，配合不到位的时候不但不能获得收益反而可能会带来额外开销。

　　如果条件允许，BlockQuicksort是快于Dual-Pivot Quicksort的，就是这个条件可能有点苛刻。

Pattern-defeating Quicksort

　　pdqsort（Pattern-defeating Quicksort）为近年问世的一种快排变种。这个算法的思想非常直白：对特殊模式的数据开小灶。特殊模式在实际业务中还是蛮常见的，的确值得关注。常见的pdqsort实现（如Rust和Boost）会带上BlockQuicksort的分支消除技巧，随机数据排序看起来也很给力，不过pdqsort本身的创新在其中其实几乎没什么贡献。

友商的谬误

　　个人认为友商有三处观点欠妥：

　　一、Go的算法应该主要借鉴C++和Rust这个思路是有问题的。其实这个点上，Go目前的性能特性更接近于Java而非C++，Java采用的双枢三分快排对目前的Go来说才是最优解。

　　二、Go的编译不给力所以BlockQuicksort在Go上没有用这个观点是错的。实测BlockQuicksort可以对纯数值数排序加速30%-40%，只是没有C++和Rust上加速100%这么明显而已。

　　三、pattern-defeating技巧是神器这个观点值得商榷。pattern-defeating技巧有用，对特殊模式数据有几倍甚至几十倍的加速。不过特殊模式数据原来就处理得比较快，在混合工况中总时间占比很低（注意是总时间占比，不要被数量占比偷换概念），加速几十倍的收益都抵不过对瓶颈点加速10%。