Question

父之齿随行，兄之齿鴈行，朋友不相踰。《礼记．王制》

Sort

排序。把一群数字由小到大排好。

实际要做排序，有两个方向，一是将数字放入循序性资料结构（例如 array 与 list），然后执行下述其中一种排序演算法。二是使用有排序功效的资料结构，例如 binary heap、binary search tree，将数字整个倒进去、整个倒出来即排序完毕。

               | best     average  worst    | extra | stable
               | case     case     case     | space |
---------------+----------------------------+-------+--------
brute force    | O(NR)    O(NR)    O(NR)    | O(N)  | O
selection sort | O(NN)    O(NN)    O(NN)    | O(1)  | X
bubble sort    | O(N)     O(NN)    O(NN)    | O(1)  | O
gnome sort     | O(N)     O(NN)    O(NN)    | O(1)  | O
insertion sort | O(N)     O(NN)    O(NN)    | O(1)  | O
Shell sort     | O(NN)    O(NN)    O(NN)    | O(1)  | X
merge sort     | O(NlogN) O(NlogN) O(NlogN) | O(N)  | O
quicksort      | O(NlogN) O(NlogN) O(NN)    | O(N)  | X
heapsort       | O(NlogN) O(NlogN) O(NlogN) | O(1)  | X
counting sort  | O(N+R)   O(N+R)   O(N+R)   | O(R)  | O
bucket sort    | O(N+B+?) O(N+B+?) O(N+B+?) | O(B)  | X
radix sort     | O(ND)    O(ND)    O(ND)    | O(D)  | O

除了数字可以排序之外，事实上字元也可以排序，因为电脑中的字元就是数字（请参照 ASCII 表）。指标也可以排序，因为指标就是记忆体位址也就是数字。一般资料也可以排序，只要资料裡的某个特定栏位是数字，这个栏位被称作键值（key）。

排序原理

排序的基本原理，当今只有两种，一是对调（数字是实数），二是放置（数字必须是整数）。

纯粹透过对调来排序，已证明出数字两两比较的次数是Ω(NlogN)，不可能更少了，当今也已经有了到达下限的排序演算法，例如 merge sort。同时透过对调与放置来排序，则可以打破方才的下限，例如 flashsort。

纯粹透过放置来排序，需要额外的记忆体空间来放置数字。时间複杂度通常是数字数量加上记忆体用量，效率相当好，只可惜只能处理整数，例如 counting sort。

暴力搜寻

依序枚举每一个整数，看看阵列裡头有没有。

Search

众里寻他千百度，蓦然回首，那人却在，灯火阑珊处。《辛弃疾．青玉案》

Search

搜寻。在资料结构当中，找出一个东西的位置。

常与 Search 相提并论的有 Sort：在资料结构当中，把所有东西排好顺序，放在正确位置。另外还有 Select：在资料结构当中，找到特定顺位的资料。

资料结构千变万化，各有其独特的 Search、Sort、Select 演算法。在阵列中，便有 Binary Search、Bubble Sort、Quickselect 这些演算法；在图论中，则有 Depth-first Search 这样的演算法。

甚至也有专为 Search、Sort、Select 而设计的资料结构，如各种 Priority Queue、各种 Search Tree、Hash Table、……等等。

Search in Array: Sequential Search

循序搜寻。依序看一遍，无一遗漏。时间複杂度是 O(N)。

Search in Sorted Array: Binary Search

二元搜寻。相信各位耳熟能详。这裡只作重点归纳。

Binary Search 的功用，是在一个排序过的数列（递增数列、递减数列）当中，找出某个数字的索引值（index）。

基本原理是 Divide and Conquer。当资料存放在阵列──Binary Search 是将一个将排序好的阵列，分为大的一边和小的一边，再看看我们要找的元素会在哪一边。如此下去直到找到为止。分割的时候，也是採用对半分，时间複杂度是 O(logN)，以 2 为底的 logN。

我想大家最好自己重新写一份，并且验证它在任何情形下，结果都是正确无误的，而不会有超出阵列范围的结果。另外也请看看这篇文章： Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken 。

上面这支程式亦可改用递迴写出来，不妨试试。

资料往往都是排序整齐的，也因此，Binary Search 常被用来加速程式。一旦看到数据资料有排序、递增递减、成正比反比的时候，便要想到 Binary Search。

还有一种常见的应用是：资料恰有两种性质，明显地分做两边──想找到分界之处，便可以用 Binary Search。

很多问题其实都隐含著上述这种性质，只是不容易发现。尝试从问题当中发掘这种性质，并且写程式解决问题，这便是程式设计深奥且有趣之处。

UVa 10611 10077

Search in Sorted Array

“ Interpolation Search ”、“ Fibonacci Search ”。鸡肋。

Search in Sorted Unbound Array: Doubling Search

倍增搜寻。主持人心中有一正整数，我们可以一直猜他心中的正整数，但是他只会回答“太高”或“太低”或“正确”。请问要怎麽猜可以最快猜到他心中的正整数呢？

有个类似的团康游戏叫做“终极密码”，常常在综艺节目出现。“终极密码”的规则比较不一样，数字范围通常只有 1 到 100，而且是很多个人轮流猜，越晚猜出来越好。这裡的猜数字游戏，数字范围是 1 到无限大，只有一个人猜，越早猜出来越好。

言归正传。从 1 开始一个一个往上猜，实在太慢了。比较快的猜法，是将问题分成两个步骤，第一个步骤是先确定范围，第二个步骤再来缩小范围。

确定范围的方式，可以从 1、2、4、8、……这个顺序下去猜。如果主持人不断回答太低，我们就不断往大数字猜，一直到主持人回答太高为止。如果主持人心中的正整数为 N，则可以用 O(logN) 的时间得到一个合理的范围，N 会落在( 2^(k-1) , 2^k ]之间。

缩小范围的方式，可以使用 Binary Search！从( 2^(k-1) , 2^k ]之间找出正确的正整数，只需 O(logN) 时间。

二分搜寻和倍增搜寻相互对立，前者除以二、后者乘以二。

Search in Sorted Arrays: Fractional Cascading

http://en.wikipedia.org/wiki/Fractional_cascading

Search in Sorted Matrix: Saddleback Search

一个排序过的阵列可以用 Binary Search 来搜寻数字，那麽一个排序过的二维矩阵呢？当一个二维矩阵裡的元素经过排序，任一位置往右、往下都呈现严格递增时（严格递减也行），此时有个很巧妙的搜寻方式，时间複杂度为 O(X+Y)，X 与 Y 分别为矩阵的长与宽。

首先在脑中将矩阵的元素切割为大于 n 的一边（右下角）与不大于 n 的一边（左下角）。现在我们所要作的，便是游走于大与小的边缘来寻找 n！从矩阵的右上角开始，尝试走到左下角，若走到了大于 n 的一边，就立即往不大于 n 的另一边移动，反之亦同。

各位可以想想当找到目标元素时，应该往左还是往下走好？当矩阵元素是非严格递增的时候会产生什麽问题？

UVa 12192

Search in Sorted Matrix: 2D Binary Search

只有特殊情况能派上用场。

一个排序过的阵列可以用 Binary Search 来搜寻数字，那麽一个排序过的二维矩阵呢？

搜寻已排序阵列，都是切对半、从中位数切成两半。搜寻已排序矩阵，亦可如法炮制，从中位数们的中位数（中中数）切成两半。

矩阵切成一条一条阵列，找到中中数；实施 Saddleback Search，以中中数将矩阵分为大的一边和小的一边，递迴找其中一边。

时间複杂度分析：

一、每一条阵列（已排序），各自找到中位数，总共 O(Y)。

二、中位数们（未排序），找到中位数，使用后面章节的演算法，O(X)。

三、Saddleback Search，O(X+Y)。

四、小于等于中中数的数字们，至少佔 1/4。大于等于亦如是。递迴找其中一边，至少删 1/4、至多剩 3/4。总共 O(logXY) 回合。

每回合的时间複杂度为 O(X+Y)，总共 O(logXY) 回合，总时间複杂度为 O((X+Y)logXY)。

时间複杂度难以记忆。简易的方式，是把 X 和 Y 视作相等，等于 N。每回合需时 O(N)，总共 O(logN^2) = O(logN) 回合，总时间複杂度为 O(NlogN)。

此演算法没有实务上的价值，只有理论上的价值，而且只有特殊情况能派上用场：资料恰有两种性质，明显地分做两边──想找到分界之处。Saddleback Search 每一步都要判断在哪一边，总共判断 O(N) 次。2D Binary Search 每一回合只需判断中中数在哪一边，总共判断 O(logN) 次。

Select

羽望见良麾盖，策马刺良于万众之中，斩其首还。《三国志》

Select

选择。找到特定名次的数字，例如第 k 小、第 k 大的数字。或者，找到特定数字的名次。

最简单的方式就是先排序、再搜寻。以下我们探讨更快的方法。

UVa 10041 10107 11875

Select in Array: Quickselect

Quicksort 只递迴其中一边。最佳、平均时间複杂度为 O(N)，最差是 O(N^2)。

Select in Array: Median-of-Medians Algorithm

找到中位数们的中位数，将数字分成大的一边和小的一边，递迴找其中一边。时间複杂度 O(N)，但是不实用。

1. 五个五个分堆，最后一堆可以没有满。

   第一堆 ● ● ● ● ●
   第二堆 ● ● ● ● ●
   第三堆 ● ● ● ● ●
   第四堆 ● ● ● ● ●
   第五堆 ● ● ● ● ●
   第六堆 ● ● ●

2. 每堆各自排序。然后求出每堆的中位数 ○。

      小  →  大
   ↑  ● ● ○ ● ●
   没 ● ● ○ ● ●
   有 ● ● ○ ● ●
   顺 ● ● ○ ● ●
   序 ● ● ○ ● ●
   ↓    ● ○ ●     ← 最后一堆对齐一下比较好看

3. 求出中位数们的中位数 x。递迴套用此演算法求得 x。

      小  →  大
   ↑  ● ● ○ ● ●
   没 ● ● ○ ● ●
   有 ● ● ○ ● ●
   顺 ● ● ○ ● ●
   序 ● ● x ● ●   ← 中位数可能在任何一个地方
   ↓    ● ○ ●

4. 将全部的数字分成两边，一边小于 x ，一边大于等于 x。

         小于 x ←|   |→ 大于等于 x
   ... ● ● ● ● ● ● x ● ● ● ● ● ● ● ● ...

5. 看看 k 是在哪一边。递迴下去找出答案。

时间複杂度証明

          小  →  大
   第一堆 ● ● ○ ● ●
   第二堆 ● ● ○ ● ●
   第三堆 ● ● ○ ● ●
   第四堆 ● ● ○ ● ●
   第五堆 ● ● x ● ●
   第六堆   ● ○ ●

依照中位数们的大小，重新排列每一堆。

              小  →  大
   第四堆  中 ● ● ○ ● ●
   第二堆  位 ● ● ○ ● ●
   第五堆  数 ● ● x ● ●   ← 中位数 x 变成排在中间
   第一堆  小 ● ● ○ ● ●
   第三堆  ↓  ● ● ○ ● ●
   第六堆  大   ● ○ ●

观察一定小于等于 x 的数、一定大于等于 x 的数。

   一定小于    一定大于
   等于 x 的数   等于 x 的数
   ◊ ◊ ◊ ● ●   ● ● ○ ● ●
   ◊ ◊ ◊ ● ●   ● ● ○ ● ●
   ◊ ◊ x ● ●   ● ● x ◊ ◊
   ● ● ○ ● ●   ● ● ◊ ◊ ◊
   ● ● ○ ● ●   ● ● ◊ ◊ ◊
     ● ○ ●       ● ◊ ◊

推得“小于等于 x 的数至少有 3n/10 - 6 个。大于 x 的数至多有 7n/10 + 6 个。”
推得“大于等于 x 的数至少有 3n/10 - 6 个。小于 x 的数至多有 7n/10 + 6 个。”

  至多 7n/10 + 6         差不多至多 7n/10 + 6
         小于 x ←|   |→ 大于等于 x
   ... ● ● ● ● ● ● x ● ● ● ● ● ● ● ● ...

分两边后，
小于的那一边至多有 7n/10 + 6 个，
大于等于的那一边差不多至多有 7n/10 + 6 个。
递迴下去，总时间複杂度为 O(n)。

可以直接使用 STL 的 nth_element()。

Select in Sorted Array

O(1)。

Select in Sorted Arrays

找到中位数们的中位数，每列皆实施 Binary Search，最后所有数字分为大的一边和小的一边，递迴找其中一边。两边的数量至少都是一半的列的一半，每回合至少削减一半的列的一半。每列各自建立首尾索引值，记录剩下的元素。

每回合需时 O(XlogY)，总共 O(logY) 回合，时间複杂度为 O(XlogYlogY)。其中 X 是阵列数量，Y 是阵列长度。

简单来说，此演算法是搜寻中中数、分两边、递迴一边。

Select in Sorted Arrays

找到中位数们的中位数，找到最大中位数、最小中位数。最小中位数至少小于一半的数字，最大中位数亦如是。判断第 K 大是小于一半或大于一半，每回合削减最大中位数的右半或最小中位数的左半。每次删除一列的一半，总共 O(XlogY) 回合。

以大小为 X 的二元搜寻树储存中位数，每回合可以快速找到最大与最小中位数。一共操作 O(XlogY) 次，每次操作 O(logX)，时间複杂度为 O(XlogXlogY)。其中 X 是阵列数量，Y 是阵列长度。

Select in Sorted Matrix

切成一列一列，找到中位数们的中位数，再利用 Saddleback Search 将矩阵分为大的一边和小的一边，递迴找其中一边。

每回合需时 O(N)，总共 O(logN) 回合，时间複杂度为 O(NlogN)。

Select in Sorted Matrix

http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

Divide and Conquer。O(N)。

Count

选出牡丹第一枝，劝君折取莫迟疑，世间若问相知处，万事逢春正及时。《六十甲子籤》

Longest Plateau

一条数列，找到连续出现最多次的数字暨次数。

Pairwise Sum

X+Y

穷举法。O(N^2)。

Fourier Transform。O(N + RlogR)。

Sort in X+Y

先穷举，再排序。O(N^2 * logN^2) = O(N^2 * logN)。

先排序，N-way Merge。O(N^2 * logN)。

Fourier Transform。O(N + RlogR)。

Search in X+Y

先排序。想像矩阵 add[i][j] = a[i] + b[j]，已排序矩阵的搜寻。O(NlogN)。

Select in X+Y

先排序。想像矩阵 add[i][j] = a[i] + b[j]，已排序矩阵的选择。O(NlogN)。

Search in 2D X+Y

http://arxiv.org/abs/0809.1171

找 y/x。最差 O(NlogNlogN)，平均Θ(NlogN)。

Select in 2D X+Y

http://arxiv.org/abs/0809.1171

找 y/x。Θ(NlogN)。

Extremum in 2D X+Y

找 y/x。必在凸包上。Θ(NlogN)。

Pairwise Distance

All Row Minimums

以下介绍三个特殊矩阵，以及其“每一个横条（直条）的最小值”的演算法。

Monge Matrix ⇒ Totally Monotone Matrix ⇒ Monotone Matrix。从特例到通例，限制从强到弱，数量从少到多，演算法从快到慢。

Monge Matrix (concave)
[standard form] ↖ + ↘ ≤ ↗ + ↙      主对角线和，小于等于次对角线和
     [row form] ↘ - ↙ ≤ ↗ - ↖      横条各处斜率，往上递增
  [column form] ↘ - ↗ ≤ ↙ - ↖      直条各处斜率，往左递增

Totally Monotone Matrix
   [row type] if ↙ ≤ ↘ then ↖ ≤ ↗  横条小于等于关係，往上递增
[column type] if ↗ ≤ ↘ then ↖ ≤ ↙  直条小于等于关係，往左递增

Monotone Matrix
   [row type] argmin ⤷             横条最小值位置，往下递增
[column type] argmin ⤵             直条最小值位置，往右递增

Monge Matrix

矩阵当中所有田字四个格子皆满足不等式：↖ + ↘ ≤ ↗ + ↙。

不等式分成凹凸两种，大小相反、性质颠倒。以下以凹为主。

Concave Monge Matrix: a[i][j] + a[i+1][j+1] ≤ a[i][j+1] + a[i+1][j]
 Convex Monge Matrix: a[i][j] + a[i+1][j+1] ≥ a[i][j+1] + a[i+1][j]

另一种等价的写法：所有子矩形的四个端点皆满足不等式。

a[i₁][j₁] + a[i₂][j₂] ≤ a[i₁][j₂] + a[i₂][j₁] when i₁ < i₂ and j₁ < j₂

移项一下，得到横条（直条）斜率递减的形式。彷彿凹函数。

Monge Matrix 乘以非负倍率，仍是 Monge Matrix。Monge Matrix 相加，仍是 Monge Matrix。

Monge Matrix has "non-negative linearity":
(1) X is Monge Matrix, k ≥ 0   ⇒ kX is Monge Matrix
(2) X and Y are Monge Matrices ⇒ X+Y is Monge Matrix

Monge Matrix 删除任意横条（直条），仍是 Monge Matrix。Monge Matrix 的其中一个横条（直条），一齐加上同一个非负数，仍是 Monge Matrix。

Symmetric Monge Matrix = Supnick Matrix。恰好沿著主对角线对称。矩阵行列索引值，可以自由对调。

Convex/Concave Monge Matrix = Submodular/Supermodular Function。矩阵行列索引值，视作区间左右边界。

举个实际范例。例如二维平面上，凸四边形上下边相加 ≤ 两条对角线相加，距离双向均等，符合 Supnick Matrix 不等式。

Supnick Matrix 的延伸意义是：不交换最好。寻找最佳排列的问题，例如 Travelling Salesman Problem、Bipartite Matching，若满足 Supnick Matrix，则有快速演算法。

Totally Monotone Matrix

分成凹凸两种，又细分成横直两种，共四种。以下以凹为主。

横条往左（直条往上），<与=的总数量递增。只会增加或不变、不会减少。< p="">

concave row version:    if ↙ ≤ ↘ then ↖ ≤ ↗
concave column version: if ↗ ≤ ↘ then ↖ ≤ ↙

还有另一种更严格的定义：≤的数量递增。

concave row version:    (if ↙ < ↘ then ↖ < ↗) and
                        (if ↙ = ↘ then ↖ ≤ ↗)
concave column version: (if ↗ < ↘ then ↖ < ↙) and
                        (if ↗ = ↘ then ↖ ≤ ↙)

自然界难以见到 Totally Monotone Matrix，其定义是计算学家故意设计的，是从 Monge Matrix 的不等式所推导出来的性质。

Monge Matrix ⇒ Totally Monotone Matrix 的证明：横条（直条）斜率递减的形式当中，若左式非负，则右式也非负。

Monotone Matrix

分成凹凸两种，又细分成横直两种，共四种。以下以凹为主。

横条往右（直条往下），每个横条（直条）的第一个最小值位置递增。最小值可能有许多个，所谓的第一个是指索引值最小者。

row version:    argmin r₀ ≤ argmin r₁ ≤ argmin r₂ ≤ ... 
column version: argmin c₀ ≤ argmin c₁ ≤ argmin c₂ ≤ ... 

自然界难以见到 Monotone Matrix，其定义是计算学家故意设计的，是从 Totally Monotone Matrix 的不等式所推导出来的性质。

Totally Monotone Matrix ⇒ Monotone Matrix 的证明：因为上方横条（左方直条）小于等于关係不变，所以最小值位置只可能一样、或者更往左（更往上）。

寻找 Monotone Matrix 的每个横条（直条）的第一个最小值

分治法。找到中央横条的最小值，然后左上矩阵与右下矩阵，分别递迴求解。时间複杂度 O(YlogX)。