[Counting Sort, Radix Sort] 計數排序, 基數排序

 Counting Sort是一種效率很高的排序方式，複雜度為$\ord{n+k}$，其中$k$是Bucket的大小，由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為，在這方面應該能做到很大的加速。

另外一個問題是Counting Sort雖然簡單，很多人甚至可以自己想到實作方法，但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort：

參數的解釋如下：

• First, Last:
  和std::sort的定義一樣，需要排序的範圍，注意不一定要是random access iterator。
• BucketFirst, BucketLast:
  Counting Sort正統的實作方式會有一個正整數陣列作為Bucket，考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多，必須要是random access iterator。
• OutputFirst:
  Counting Sort的output是直接將input存到另一個陣列中，因此OutputFirst指的是Output陣列的開頭，必須要是random access iteator，且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式，如果想要保留原本input的話可以將其拿掉。
• Key:
  這是一個函數，Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。

有了Counting sort，Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort，所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。

以整數(int, -2147483648~2147483647)排序為例，可以先針對第十億位做為Key進行排序，接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key，最後再以正負號最為Key進行排序，這樣就可以完成一般範圍的整數排序。

實際上一般不會這樣用，通常是用在有多個Key值的情況，以下面的程式碼來說，可以自行執行看看花費的時間有多少：

[Discretize Relabeling] 離散化器

離散化是演算法競賽常用的操作，在各種實際問題上也能看到其應用。最基本的情況，是對於n個可排序的元素，製造一個map使得它們可以和自己的名次一一對應，但通常的應用中這n個元素確定之後就不太會有增減的動作，因此可以存到vector中排序去除重複的部分，搜索的部分就用二分搜尋來取代。

[ Median-of-Medians Algorithm ] 中位數演算法

這是一個可以在保證線性時間(c++ std::nth_element是隨機演算法)找出一個序列中第k大元素的演算法，網路上已經有不少教學，但是很多人都認為常數太大因此缺乏實作。

教學文在此：http://tmt514-blog.logdown.com/posts/484313-divide-and-conquer-method-iii-find-the-median

其實我高中時就想要試著去時做看看，但是因為那時的程式能力太差的關係，做出來的東西一直有bug，後來去忙其他事情後就被我忘掉了。最近因為學長面試有被問到一樣的問題跑來問我，才慢慢想起來有一份沒寫完的code，於是今天抱著不管怎樣都要寫出來的精神把他寫完了：

[ C++ std::sort python implement ] C++std::sort Python實作

最近有一個很靠北的課需要用python寫一些C++很容易做到的東西。
這次我們被要求寫一個quick sort，但是他要求的做法實在太糟糕了，於是我就參考了C++ std::sort來實做了一個quick sort(不包含heap sort的部分)：

[ Mo's algorithm ]莫隊算法

對於一些詢問區間答案的資料結構題，我們已經知道了區間[l,r]的答案，且能在極少的時間( \(\ord 1 \) or \(\ord{logN}\) )內得到區間[l+1,r]、[l-1,r]、[l,r+1]、[l,r-1]的答案，題目也准許離線，只要滿足這些性質就可以使用莫隊。

首先我們須將所有詢問記錄下來，將序列分成sqrt(n)塊，找出每筆詢問l所在的塊，每塊內r由小排到大

這裡n是序列的長度

之後就按造順序一個一個將序列元素在一些維護費用很小的資料結構進行插入刪除，直到等於當前區間為止，此時就可以把這個資料結構的答案存到ans陣列裡，然後結束後一次輸出

這裡進行一下簡單的證明:

• 假設序列長度為N，我們將序列每K個分成一塊，在排完序後，左界屬於同一塊的詢問，每次都不會移動操過K次；而左界屬於不同塊的操作，從第i塊移動到第i+1塊最多要移動2*K次，總共分成N/K塊，故移動次數加起來不操過2*K*(N/K)=2*N次，因此左界移動的複雜度為\(\ord{Q*K}+\ord N\)，Q為詢問次數
• 對於右界，在同一塊內因為是遞增的關係所以移動次數不會操過N次，而最多只有N/K塊，因此複雜度為\(\ord{N*N/K}\)
• 這個時候我們可以取K=sqrt(N)得到一個複雜度為\(\ord{Q*K+N+N*N/K}=\ord{(Q+N)*sqrt(N)}\)的方法

這是區間眾數的模板(對於每個詢問l,r輸出區間[l,r]眾數的個數):

[ Difference Cover modulo 3, DC3 ] 後綴數組線性DC3演算法

DC3 是歷史上第一個線性時間的後綴數組演算法，而且相對於 SA-IS 來說更容易作為教材。

這是 DC3 的原始論文：
https://www.cs.helsinki.fi/u/tpkarkka/publications/jacm05-revised.pdf

首先是後綴分類。我們會將所有後綴根據其起始位置 $i$ 對 3 的餘數進行分類，形成三種不同的類型：

• Type A ($i$%3=0):
  這類後綴的起始位置是 3 的倍數。它們不會直接參與初始排序，而是透過 Type B 的排序結果間接排序。
• Type B1 ($i$%3=1):
  這類後綴會與 Type B2 一起組成 Type B 後綴集合，並進行初步排序。
• Type B2 ($i$%3=2):
  同樣屬於 Type B 後綴集合，與 B1 一起進行排序。

以 "mississkp" 為例，為了方便操作我們在其尾端加入兩個哨兵字元 '\0'。

如圖1 所示，首先我們對於每個 Type B 後綴，我們取出其前三個字元作為排序鍵值，將這些三元組視為新的字元（透過 radix sort 將三元組映射為整數，實作上呼叫了三次 counting sort），並對它們進行排序。若排序後的鍵值唯一，則排序完成；否則需將這些鍵值壓縮成新的字母表，並遞迴呼叫 DC3 來排序這個縮小版的問題。

圖1

如圖2 所示，此時 Type B 後綴的排名已經確定了。對於每個 Type A 後綴 i，我們無法直接比較整個後綴（因為效率問題），但可以利用 Type B 的排名來構造一個排序鍵值：

• 對於每個 Type A 後綴 i，我們取：

• $S[i]$：當前字元
• $R[i+1]$：Type B1 後綴的排名（因為 i+1 % 3 = 1）

一次 counting sort 後，我們得到了  Type A 後綴的排名。

圖2

接著我們要合併兩種後綴的排序結果，可以使用 std::merge 合併，但須要寫一個 $\ord{1}$ 的比較函數。設比較函數 $cmp(x,y)$， $x$ 是某個 Type B 後綴的編號，$y$ 是某個 Type A 後綴的編號：

1. $S[x]\ne S[y]$：
   直接比較 $S[x],\;S[y]$
2. Type B1 後綴 ($x$ % 3 = 1)：
   此時 $x+1$ 和 $y+1$ 都是 Type B 後綴，直接比較 $R[x+1],\;R[y+1]$
3. Type B2 後綴 ($x$ % 3 = 2)：
   此時 $x+1$ 是 Type A 後綴， $y+1$ 是 Type B 後綴，直接呼叫 $!cmp(y+1,x+1)$

圖3 展示了當前範例的合併結果，DC3 算法到這邊就結束了。

整體時間複雜度 $T(n)=T(2n/3)+\ord{n}=\ord{n}$，但要注意空間使用量
$$M(n) =
\begin{cases}
n + \delta(n) + 2, & n \leq 2 \\
n + \delta(n) + 2 + M\left(\left\lfloor \frac{2(n + \delta(n))}{3} \right\rfloor\right), & n > 2\end{cases}\\ \delta(n) = [n\equiv 1\left(\bmod 3\right)]$$

根據 AI 的推導 $M\left(n\right)\le 3n+\left\lfloor 4\log_{1.5}\left(n-2\right)\right\rfloor+1$。

圖3

2025/10/10 更新：有人發現我原始的程式碼在當 n%3=1 遞迴時在 Type B1 和 Type B2 之間沒有隔離符號，有可能導致這兩類後綴排序錯誤，聽說我一開始的參考資料 ([2009] 后缀数组——处理字符串的有力工具 by. 罗穗骞) 也有一樣的問題，因此我花了點時間重寫了 DC3 的教學。

錯誤原因如圖4 所示，若不加上這個哨兵字元的話，後綴 7 就不會被加入遞迴運算，這樣會導致某個 Type B1 後綴將不是自己正確後綴的 Type B2 後綴連接起來排序導致結果錯誤。

圖4

以下提供模板(註解是請 AI 寫的，拿掉之後程式碼應該會很短):

[ Suffix Array Prefix doubling algorithms ] 後綴數組倍增算法

後綴數組(又稱尾碼陣列)是一個十分強大的字串處理武器，大部分的問題都可以用它來解決，它可以幾乎做到所有後綴樹(Suffix Tree)能做到的事，所以這邊就不介紹後綴樹了

因為後綴數組可以由後綴樹進行遍歷轉換而來，而構造後綴樹僅需花費線性的時間，所以構造後綴數組的時間可為線性\(\ord N\)，但是後綴數組本身就是為了減少構造後綴樹的空間與代碼量而被發明出來的，直接由後綴樹轉換是沒意義的
但是仍然有其他線性構造後綴數組的方法，像是DC3、SA-IS等會在下一篇介紹，這次要講的是比較簡單常用的方法-----倍增法
關於後綴數組的使用說明可以參考《后缀数组——处理字符串的有力工具》
關於倍增法的說明可以參考 演算法筆記-SuffixArray 的部分
這邊提供\(\ord{N*logN*logN}\)及\(\ord{NlogN}\)的模板

\(\ord{N*logN*logN}\):
\(\ord{NlogN}\):
注意此方法必須要在字元集大小為常數的情況下有效，否則必須離散化

所需的陣列長度只需要與字串陣列相同即可
當然\(N*logN*logN\)的做法會比較值觀，\(NlogN\)的方法則是利用radix_sort進行的，radix_sort本來在倍增的時候要先排序第一關鍵字跟第二關鍵字，但是第二關鍵字排序的結果可以用已經求好的SA直接求出來
對radix_sort還不了解的人請看這個網頁:https://www.cs.usfca.edu/~galles/visualization/RadixSort.html
如果想對Suffix Array算法進行測試請使用這個Online Judge:
http://www.spoj.com/problems/SARRAY/