Jan Fan     About     Archive     Feed     English Blog

再论排序的本质

排序问题早已是老生常谈,精辟的见解如刘未鹏的文章也已是金玉在前。 今天再做自己的一翻讲述,既当作是作为自己的思考结果的记录,也是作为一份自己力所能及的补充,因为深刻的本质需要从尽可能多的角度去认识

信息的保存实际上是一种传递性变换,把不稳定的可辨状态变换成一种稳定的可辨状态。B通常只反映了A的某一个侧面——如形状、气味等

也可以把信息的储存看作一种特殊的信息传递过程,它也遵守信息量衰减的规律。

——摘自《控制论与科学方法论》

控制论:工具的控制能力

排序问题,就是把一串无序的数列按顺序(譬如从小到大)重新排列好。

由于计算机计算模型的限制,大多数情况下我们讨论的都是Comparison Sort,即排序过程中唯一可以利用的工具就是“两个元素之间的数值比较”。

我们首先补充一个控制论中的概念——“工具的控制能力”,这里的工具即对应Comparison Sort中的“两个元素之间的数值比较”。

一切控制过程都有三个基本环节

  1. 了解事物面临的可能性空间
  2. 在可能性空间中选择某一些状况为目标
  3. 控制条件,使事物向既定的目标转化

排序的可能性空间是多少呢?排列组合可知\(N\)个元素的全部组合的可能性是\(N!\)

而“工具的控制能力”体现在第3步中,即工具对事物的可能性空间进行控制(通常是减少其可能性空间)。 “工具的控制能力”的定义是

工具的控制能力 = 控制前的可能性空间 / 控制后的可能性空间

就“两个元素之间的数值比较”这个工具而言,它的控制能力是2,即经过这个工具能使排序的可能性空间减半。

所以可得Comparison Sort是存在一个最优下界的——\(O(Nlog_2{N})\),依据斯特灵公式可以推得。

但在实际操作中,并不是每次比较都可以达到这个控制能力的,所以很多排序算法需要的比较次数的量级高于最优下限。

实际的排序过程

实际的排序过程我们可以这样看——一个元素一个坑(slot),目标是找到各个元素在有序排列下属于自己的唯一的坑(Stable Sorts)。

 1,3,5,7,9,2,4,6,8,10

 +-+-+-+-+-+-+-+-+-+-+
 +-+-+-+-+-+-+-+-+-+-+

就单个元素来看,想要找到自己的坑,应该怎么做?

  1. 与全部元素比较一遍
  2. 跟中位数比较(二分法)
  3. 不基于比较直接拥抱自己的坑(基数排序)

第一种方法遍历了全部两两元素之间的比较,最后的复杂度\(O(N^2)\),选择排序Selection Sort就是基于这个原则的,囊括了全部pair比较结果的可能性。

第二种方法做不到,但可以做到近似的二分。在无序数列中你怎么知道哪个元素就是中位数呢,即使是在有序数列中你也还得做一次二分查找才能找到。近似的做法,如快排常用的Median of three

最后一种就类似map基于Hash Table的实现,而Comparison Sort则类似于map基于决策树的实现,是做不到这种直接命中的,必须基于比较才能最后确定元素的坑。

为什么高级排序方法比三大初级排序方法快得多呢? 找坑的方法直接决定了排序算法的效率,而找坑的方法的本质差异在于挑选比较元素的方法。

一个元素尽量与跟自己相近的元素比较,避免与跟自己差距过于明显的元素比较。 从信息论的角度来说就是——在选择对象概念均等的条件下,获得的信息量最大。

假设元素a<b<c,在做了a<b之后,就应当避免a<c这样无谓的比较; 而当i<k, j<k时,做ij的比较就显得很有意义了。

各种排序算法

提高算法效率的原则—— 尽可能把元素按大小均分到不同的集合,然后在更小的集合内进行更细致的比较,增强每次比较的控制能力,以追求更少的比较次数。

例如,二分法就是把元素均分的两个同等大小的集合,而最暴力的逐一比较算法则是把元素分到一个大小只为1的集合和另一个包含其余所有元素的集合。

下面我们会分别讨论几种流行的排序方法

快速排序 Quick Sort

快排就是这个原理的最佳实践者。理想的轴(pivot)将数列分成均等的两半。 某个元素在跟pivot做一次比较之后,被归属到其中一方,从此再也不用跟另外一半的元素做比较了。

   <--- pivot: 5 --->
 0,1,2,3,4    6,7,8,9,10
 +-+-+-+-+-+-+-+-+-+-+-+
 +-+-+-+-+-+-+-+-+-+-+-+

归并和希尔排序 Merge Sort & Shell Sort

希尔和归并很相似,都是以两个有序数列之间的合并为基础,只是在总数列中划分有序数列的方式不一样。

两个排头的元素相比较(ascending order),假设分别为a与b,分属A与B两个有序数列。

   +-----------+
 A |a,a1,a2... |
   +-----------+
   +-----------+
 B |b,b1,b2... |
   +-----------+

假设a<b,a就避免了跟在b后面的整个B数列的比较,就是避免了与一半的元素的比较(a只需要与A中其它元素进行比较)。

堆排序 Heap Sort

以max-heap(堆顶为最大元素)为例。

在建堆(heap creation phase)或者排序(selection phase),都涉及到一个动作——“sift up”,将将数值更大的内部元素推上去,不合格的堆顶元素拉下来。

// float down the tree rooted at i: O(log n)
MAX-HEAPIFY(A, i) 

如下图的未完全的堆,堆顶1的两个child只要进行一次比较,就可以把较大的child(9)推上去,把堆顶1拉到相应的子堆(sub-heap)中,从而避免了与另一个子堆(rooted at 8)的比较,即避免一半的元素的参与。

       +-+
       |1|
       +-+
    +-+   +-+
    |8|   |9|
    +-+   +-+
  +-++-+ +-++-+
  |4||6| |5||7|
  +-++-+ +-++-+

缓存对排序的影响

大部分讨论都集中在算法的理论层面。 但单纯考虑理论上的最优解是不够的,我们还需要考虑计算机自身的物理特性——“缓存”。

拿快排和堆排来做例子。 除了堆排序每次是将最小的元素放到栈顶,隆低了元素比较的控制能力之外(参考这里),缓存也对它的速度产生了影响。

快排的存取模型的局部性(locality)更强。 参见下图。

Quick Sort:

   range1      range2
   /   \       /   \
  +-----+-----+-----+
  |1,3,2,pivot,8,7,9|
  +-----------------+

Heap Sort:

    range1 & range2
   /               \
  +-----------------+
  |1,8,9,pivot,3,2,7|
  +-----------------+
         +-+
         |1|
         +-+
      +-+   +-+
      |8|   |9|
      +-+   +-+
    +-++-+ +-++-+
    |1||3| |2||7|
    +-++-+ +-++-+

更具体的讲解可以参考这里

主要参考资料

Comments

多说 Disqus