[Algorithm] 演算法整理

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 。

暴力搜尋

依序枚舉每一個整數，看看陣列裡頭有沒有。

1. void brute_force(int array[], int N)
2. {
3.     int max_value = -1e9;
4.     int min_value = 1e9;
5.     for (int i=0; i<N; ++i)
6.     {
7.         max_value = max(max_value, array[i]);
8.         min_value = min(min_value, array[i]);
9.     }
10.  
11.     for (int i=min_value; i<=max_value; ++i)
12.     {
13.         // 看看陣列裡面有沒有
14.         for (int j=0; j<N; ++j)
15.             if (array[j] == i)
16.                 cout << i;
17.     }
18. }

令陣列最小值為 A ，最大值為 B 。令 A 和 B 之間的整數有 R 個， R = B-A+1 。時間複雜度為 O(RN) 。

Selection Sort

掃描一遍所有數字，找到最小值，挪至陣列左端。遞迴處理尚未排序的 N-1 個元素。

1. void selection_sort(int array[], int N)
2. {
3.     for (int i=0; i<N; ++i) // N改為N-1更精準
4.     {
5.         // 從尚未排序的數字當中，找出最小的數字。
6.         // （它也是全部數字當中第i小的數字。）
7.         int min_index = i;
8.         for (int j=i+1; j<N; ++j)
9.             if (array[j] < array[min_index])
10.                 min_index = j;
11.  
12.         // 把第i小的數字，放在第i個位置。
13.         swap(array[i], array[min_index]);
14.     }
15. }

Bubble Sort

由左到右，相鄰兩兩比較，較大者往右挪，最後最大值會出現在陣列右端。遞迴處理尚未排序的 N-1 個元素。

1. void bubble_sort(int array[], int N)
2. {
3.     for (int i=0; i<N; ++i) // N改為N-1更精準
4.         for (int j=0; j<N-i-1; ++j)
5.             if (array[j] > array[j+1])
6.                 swap(array[j], array[j+1]);
7. }

稍做改良：一旦排序好，便趕快結束。當資料很亂時，這麼做效益不彰。

1. void bubble_sort(int array[], int N)
2. {
3.     for (int i=0; i<N; ++i) // N改為N-1更精準
4.     {
5.         bool sorted = true;
6.         for (int j=0; i<N-j-1; ++j)
7.             if (array[j] > array[j+1])
8.             {
9.                 swap(array[j], array[j+1]);
10.                 sorted = false;
11.             }
12.         if (sorted) return;
13.     }
14. }

Gnome Sort

原理和 Bubble Sort 相同，但是兩兩比較的先後次序有所改變。特色是程式碼只有一個迴圈，結構簡單。

1. void gnome_sort(int array[], int N)
2. {
3.     for (int i=0; i<N; )
4.         if (i == 0 || array[i-1] < array[i])
5.             i++;
6.         else
7.         {
8.             swap(array[i-1], array[i]);
9.             i--;
10.         }
11. }

Insertion Sort

由左到右，逐一把數字插入到目前已排序的陣列當中。需將大量數字往右挪，以騰出空間插入數字。

1. void insertion_sort(int array[], int N)
2. {
3.     for (int i=2; i<N; ++i)
4.     {
5.         int pivot = array[i];
6.  
7.         int j;
8.         for (j=i-1; j>=0; --j)
9.             if (pivot < array[j])
10.                 array[j+1] = array[j];  // 先行往右挪
11.             else
12.                 break;
13.  
14.         array[j+1] = pivot; // 插入
15.     }
16. }

資料結構如果是 array ，可以使用 Binary Search 快速找到插入點；但是很不幸的，插入時還是要挪動整塊記憶體。

資料結構如果是 list ，就無法使用 Binary Search 得到插入點；但是很幸運地，插入時不必挪動整塊記憶體。

UVa 10107

Shell Sort

Shell 是一個人名，是發明這個演算法的人，不是殼的意思。

運用 Scaling Method ：以固定間隔取得數字做為一組，各組各自做 Insertion Sort ；然後減少間隔大小，重複上述動作。

1. void shell_sort(int array[], int N)
2. {
3.     for (int gap = N/2; gap > 0; gap /= 2)
4.         for (int i = gap; i < N; ++i)
5.             for (int j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
6.                 swap(v[j], v[j+gap]);
7. }

Merge Sort

運用 Divide and Conquer ： Divide 是陣列分兩半； Conquer 是兩半分別排序； Combine 是兩半各自排序好的陣列，弄成一條排序好的陣列。

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

UVa 10810

Quicksort

運用 Divide and Conquer ： Divide 是選定 pivot ，把 pivot 挪到陣列邊緣，然後把陣列分成大的一邊和小的一邊； Conquer 是兩邊分別排序； Combine 不做任何事。

可以任選一個數字當作 pivot ，排序結果皆正確。要讓 Quicksort 達到最佳效率，就是每次選中的 pivot ，都剛好可以把陣列分成兩等份，如此一來時間複雜度是 O(NlogN) ，這是帶點運氣成份的。幸運的是，即便把陣列分成數量懸殊的兩半，即便是 1000000:1 ，只要有個比例，時間複雜度還是 O(NlogN) 。

固定選擇最後一個數字當作 pivot ，也有機會把陣列分成兩等份。但是這卻產生一個古怪的現象：遇到已經排序的陣列，卻會變成每次都沒有分到，時間複雜度變成 O(N²) ，超級慢。

結果導致 Quicksort 有時快、有時卻很慢，遇到幾乎排序好的陣列，更是慢到吐血。時快時慢，該快不快，那不是很莫名其妙嗎？

為了避免這種情況，可以每次都用亂數指定 pivot ，這樣不管給定陣列是有排序的或是沒排序的，兩等份的機會都一樣多，如此就比較不會出現前述的古怪情形。不過這又衍生出一個問題，只是想做個排序，卻還得載入亂數模組，耗損系統資源、拖慢系統速度，帶來了新的壞處。

最後大家捨棄亂數，轉而構思一些簡單小技巧，讓選出來的 pivot 儘可能把陣列分成兩等分。例如 Java 的 Quicksort 是把陣列切成前中後三段，拿這三段中央的數字，三個數字的中位數當作 pivot 。這便是一個簡單實用的小技巧。

蠟燭兩頭燒

1. // sort interval [left, right]
2. void quick_sort(int array[], int left, int right)
3. {
4.     if (left < right)
5.     {
6.         // divide (partition)
7.         int pivot = array[(left+right)/2];  // 可以隨便選
8.         int i = left - 1, j = right + 1;
9.         while (i < j)
10.         {
11.             do ++i; while (array[i] < pivot);
12.             do --j; while (array[j] > pivot);
13.             if (i < j) swap(array[i], array[j]);
14.         }
15.  
16.         // then conquer
17.         quick_sort(array, left, i-1);
18.         quick_sort(array, j+1, right);
19.  
20.         // no need to combine sub-solutions
21.     }
22. }

蠟燭燒一頭

1. void quick_sort(int array[], int left, int right)
2. {
3.     if (left < right)
4.     {
5.         // divide (partition)
6.         int pivot = array[(left+right)/2];  // 可以隨便選
7.         swap(array[right], array[(left+right)/2]);  // 換到最右邊
8.  
9.         int i = left, j = left;
10.         for (; j < right; ++j)
11.             if (array[j] <= pivot)
12.             {
13.                 if (i < j) swap(array[i], array[j]);    // 不加if也可以
14.                 i = i + 1;
15.             }
16.         if (i < right) swap(array[i], array[right]);    // 不加if也可以
17.  
18.         // then conquer
19.         quick_sort(array, left, i-1);
20.         quick_sort(array, i+1, right);
21.  
22.         // no need to combine sub-solutions
23.     }
24. }

stackless quicksort（數字為正數）

1. void quick_sort(int array[], int left, int right)
2. {
3.     int array[N] = -1;
4.     for (int i=0; i<N; ++i)
5.     {
6.         while (array[i] > 0)
7.         {
8.             int pivot = array[i], k = i;
9.             for (int j=i+1; array[j] < 0; ++j)
10.                 if (array[j] < pivot)
11.                     swap(array[++k], array[j])
12.  
13.             swap(array[i], array[k])
14.             array[k] = -array[k];
15.         }
16.         array[i] = -array[i];
17.     }
18. }

stackless quicksort

1. https://github.com/yuhanlyu/Snippets/blob/master/sort/quickstackless.c

Quicksort 演算法的陷阱相當多，須考慮數字全都相等、判斷式是小於還是小於等於、分割點恰好選到最大值或者最小值、遞迴的區段範圍、遞迴的區段很短、 …… 等等問題。編寫 Quicksort 的程式碼時，最好是寫一支窮舉所有排列的程式，一一排序、一一驗證。如果擔心自己寫的程式碼用在正事上不妥當，也可以採用程式語言函式庫內建的 Quicksort 。

UVa 755

© 2010 tkcn. All rights reserved.

Heapsort

陣列可以做為二元樹資料結構。把陣列本身當作是 heap ，逐一把數字加入 heap ，達到排序功效。

Introsort

Quicksort 的加強版。遞迴分割陣列，區間越來越短，數字也幾乎排序好了。對於幾乎已經排序好的區間， Quicksort 效率非常差，所以改用 Heapsort 。

分水嶺通常設定成 logN² = 2logN ， N 是陣列長度。

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

Counting Sort

全部數字依其數值大小，放到相符位置。接著由小到大讀取各個位置的數字。

1. void counting_sort(int array[], int N)
2. {
3.     // 歸類並標記
4.     int count[10000] = {0};
5.     for (int i=0; i<N; ++i)
6.         count[ array[i] ]++;
7.  
8.     // 計數陣列的索引值大小順序，正是元素大小順序。
9.     for (int i=0, k=0; k<N; ++i)
10.         while (count[i]--)
11.             array[k++] = i;
12. }

1. struct Data {int key, data;};
2.  
3. void counting_sort(Data* array[], int N)
4. {
5.     // 歸類並標記
6.     vector<Data*> count[10000];
7.     for (int i=0; i<N; ++i)
8.         count[ array[i]->key ].push_back( array[i] );
9.  
10.     // 索引值的大小順序，剛好也是元素的大小順序。
11.     for (int i=0, k=0; k<N; ++i)
12.         for (int j=0; j<count[i].size(); ++j)
13.             array[k++] = count[i][j];
14. }

UVa 484 11462

Bucket Sort

全部數字依其數值區間，放到相符桶子。接著各個桶子各自排序之後，再由小到大讀取各個桶子的數字。

Radix Sort

由低位數到高位數，每個位數依序做為鍵值，做 D 次 counting sort ， D 為位數大小。

資料是數字，數字表示成二進位， D = logR 。

Flash Sort

http://www.cnblogs.com/kkun/archive/2011/11/24/2261529.html

延伸閱讀：以指標排序

排序會搬動資料，但是大多數時候我們不希望搬動資料。此時可以取出資料的記憶體位址，存入指標，對指標進行排序。

也有人以索引值排序，道理跟指標相同。

UVa 482

延伸閱讀： stable

兩筆相同資料，原本排在前頭的，排序後仍在前頭；原本排在後頭的，排序後仍在後頭。這稱作 stable 的排序演算法，相同資料、順序不變。

只要是放在陣列的資料，任何一種排序演算法，都可以擴充成 stable 的排序演算法。你想到解決方法了嗎？

延伸閱讀： lexicographical order

當資料是高維度數據，如何比較大小呢？其中一種方式叫做字典順序，先比較第一維度；如果平手，再比較第二維度；如果又平手，再比較第三維度；以此類推。

英文字典，即採用了字典順序，排序所有英文單字。英文字典當中，兩個英文單字比較大小的方式，就是字典順序。

延伸閱讀： Sorting Network

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 。

1. int binary_search(int left, int right, int pivot)
2. {
3.     while (left <= right)
4.     {
5.         int mid = (left + right) / 2;
6.         if (array[mid] < pivot)
7.             left = mid + 1;
8.         else if (array[mid] > pivot)
9.             right = mid - 1;
10.         else if (array[mid] == pivot)
11.             return mid;
12.     }
13.     return left;    // 如果找不到，就回傳稍大一點的數值位置。
14. }

我想大家最好自己重新寫一份，並且驗證它在任何情形下，結果都是正確無誤的，而不會有超出陣列範圍的結果。另外也請看看這篇文章： 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ᵏ⁻¹, 2ᵏ] 之間。

縮小範圍：可以使用 Binary Search ！從 (2ᵏ⁻¹, 2ᵏ] 之間找出正確的正整數，只需 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²) = O(2logN) = 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²) 。

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

一條數列，找到連續出現最多次的數字暨次數。

1. int longest_plateau(int a[], int n)
2. {
3.     if (n == 0) return 0;
4.  
5.     int counter = 1;
6.     int length = 1;
7.  
8.     for (int i=1; i<n; i++)
9.     {
10.         if (a[i] == a[i-1])
11.         {
12.             counter++;
13.             length = max(length, counter);
14.         }
15.         else
16.             counter = 1;
17.     }
18.     return length;
19. }

已排序數列，有更簡單的做法。

1. int longest_plateau(int a[], int n)
2. {
3.     if (n == 0) return 0;
4.  
5.     int length = 1;
6.     for (int i = 1; i<n; i++)
7.         if (a[i] == a[i-length])
8.             length++;
9.  
10.     return length;
11. }

Mode

一條數列，找到出現最多次的數字暨次數。

先排序再搜尋。採用交換式排序，例如 quicksort 或者 merge sort ，時間複雜度 O(NlogN) ，額外的空間複雜度 O(1) 。採用索引式排序，例如 counting sort 或者 hash table ，時間複雜度 O(N+R) ，額外的空間複雜度 O(R) 。

Majority Vote

一條數列，找到出現過半的數字暨次數。時間複雜度 O(N) ，額外的空間複雜度 O(1) 。

1. int find_mode(int a[], int n)
2. {
3.     int mode = a[0], counter = 0;
4.     for (int i=0; i<n; i++)
5.         if (counter == 0)
6.             mode = i, counter = 1;
7.         else
8.             if (a[i] == mode)
9.                 counter++;
10.             else
11.                 counter--;
12.  
13.     counter = 0;
14.     for (int i=0; i<n; i++)
15.         if (a[i] == mode)
16.             counter++;
17.  
18.     if (counter < (n+1)/2) return -1;
19.     return counter;
20. }

Maximum Gap

給定一串未排序數列，排序之後，考慮相鄰兩數的差值，其中最大的差值稱作「最大間隔」。可能同時有許多個「最大間隔」。

時間複雜度 O(N) ，不必排序，就能找出所有最大間隔。但是前提是 floor 運算是 O(1) 。

一、找到最大值max、最小值min。
二、建立N-1個bucket，
　　一個bucket的範圍大小是 D = (max-min)/(N-1)。
三、除了最大值、最小值以外，
　　剩下的N-2個數字通通塞入bucket，
　　數字 x 塞到 floor[(x-min)/D]。
回、N-1個bucket，N-2個數字，必有空的bucket。
　　所以最大間隔的兩數必定跨過空的bucket，最大間隔大於D。
　　換句話說，最大間隔的兩數不在同一個bucket。
四、刪除空的bucket，重新編號。
　　算出各個bucket內含數字的最大值bucket[i].max、最小值bucket[i].min。
五、max { bucket[i+1].min - bucket[i].max } 即是最大間隔。

Minimum Gap

一串數列當中，找到相差最小的兩個數字。

給定一串未排序數列，排序之後，考慮相鄰兩數的差值，其中最小的差值稱作「最小間隔」。一條數列可能同時有許多個「最小間隔」。

時間複雜度 O(NlogN) 。

【待補文字】

Count Distinct

一串數列當中，找到相異數字個數。

http://ravi-bhide.blogspot.tw/2011/04/flajolet-martin-algorithm.html

https://chenjiehua.me/database/hyperloglog-bigdata.html

末一位可能是0/1，如果都出現，答案至少2
末二位可能是00/01/10/11，如果都出現，答案至少4

【待補文字】

Pairwise Sum

X+Y

窮舉法。 O(N²) 。

Fourier Transform 。 O(N + RlogR) 。

Sort in X+Y

先窮舉，再排序。 O(N²logN²) = O(N²logN) 。

先排序， N-way Merge 。 O(N²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

分成凹凸兩種，又細分成橫直兩種，共四種。以下以凹為主。

橫條往左（直條往上）， < 與 = 的總數量遞增。只會增加或不變、不會減少。

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) 。

1. const int X = 6;
2. const int Y = 8;
3. int a[X][Y];        // monotone matrix
4. int min_index[X];   // 記錄最小值位置
5.  
6. // call minimum(0, X-1, 0, Y-1) at first
7. void minimum(int i1, int i2, int j1, int j2)
8. {
9.     if (i1 > i2) return;
10.  
11.     /* divide：找到中央橫條的最小值 */
12.  
13.     int i = (i1 + i2) / 2, j;   // 中央橫條、最小值位置
14.     int min = 1e9;
15.     for (j=j1; j<=j2; ++j)
16.         if (a[i][j] < min)
17.         {
18.             min = a[i][j];
19.             min_index[i] = j;
20.         }
21.  
22.     /* conquer：左上矩陣與右下矩陣，分別遞迴求解。*/
23.  
24.     minimum(i1, i-1, j1, j);
25.     minimum(i+1, i2, j, j2);
26. }

尋找 Totally Monotone Matrix 的每個橫條（直條）的第一個最小值

限制更強了，擁有更快的演算法。分治法，三個步驟。

一、刪除多餘直條，將 X×Y 矩陣變成 X×X 方陣：

把矩陣裡面每一個橫條的第一個最小值圈出來。目標是：砍掉不含第一個最小值的直條。砍到變成方陣即可，不必趕盡殺絕。

任意橫條上面，任取兩個元素 a[i][j₁] a[i][j₂] ，比較大小。如果 a[i][j₁] ≤ a[i][j₂] ，表示右邊元素以上，皆不含第一個最小值。如果 a[i][j₁] > a[i][j₂] ，表示左邊元素以下，皆不含第一個最小值。

沿對角線前進，與右邊元素比較大小。如果 a[i][i] ≤ a[i][i+1] ，那麼姑且繼續前進，累積無效區域，使得上三角矩陣都是無效區域。如果 a[i][i] > a[i][i+1] ，那麼對角線當前元素以下是無效區域，恰好跟先前的無效區域，湊出一整個直條，得以刪除。

二、遞迴求解，以找到偶數橫條的最小值：

偶數橫條合併成一個 X/2×X 矩陣，遞迴求解。

三、內插夾擠，以找到奇數橫條的最小值：

把矩陣裡面每一個橫條的第一個最小值圈出來，從上往下看，第一個最小值的位置從左往右遞增。用偶數橫條的最小值位置，夾擠出奇數橫條最小值的可能位置，然後窮舉搜尋就行了。

此演算法稱做 SMAWK Algorithm 。時間複雜度 O(X+Y) 。

1. const int X = 6;
2. const int Y = 8;
3. int a[X][Y];    // totally monotone matrix
4.  
5. void reduce()   // 刪除多餘直條
6. {
7.     int i = 0;  // 直條編號，從0到Y-1。
8.  
9.     while (a尚未成為方陣就繼續)
10.     {
11.         // a[1:i][i+1]右上直條不含第一個最小值。
12.         if (a[i][i] <= a[i][i+1] && i+1 < Y-1)
13.         {
14.             i++;    // 繼續沿對角線前進，累積無效區域
15.         }
16.         // a[1:i][i+1]恰是矩陣最右端直條，恰是一整個無效直條。
17.         else if (a[i][i] <= a[i][i+1] && i+1 == Y-1)
18.         {
19.             砍第i+1直條;
20.             if (i > 0) i--;
21.         }
22.         // a[i:n][i]左下直條不含第一個最小值。
23.         else if (a[i][i] > a[i][i+1])
24.         {
25.             砍第i直條;  // 恰好湊成一整個無效直條。
26.             if (i > 0) i--;
27.         }
28.     }
29. }

1. https://github.com/hczhu/algorithm-collection/blob/master/data-structures/SMAWK.cpp

尋找 Monge Matrix 的每個橫條（直條）的第一個最小值

限制更強了，理應有更簡易的演算法，但是似乎沒人研究？

可以直接使用上述兩個演算法。

UVa 12311