排序，面試中，問的比較多。

時間復雜度為O(n)的排序，除了基數排序(Radix Sort)，還有計數排序(Counting Sort)。今天，1分鐘，通過幾幅圖，爭取讓大家搞懂計數排序。

[[247748]]

計數排序的適用范圍?

待排序的元素在某一個范圍[MIN, MAX]之間。

畫外音：很多業務場景是符合這一場景，例如uint32的數字排序位于[0, 2^32]之間。

計數排序的空間復雜度?

計數排序需要一個輔助空間，空間大小為O(MAX-MIN)，用來存儲所有元素出現次數(“計數”)。

畫外音：計數排序的核心是，空間換時間。

計數排序的關鍵步驟?

• 步驟一：掃描待排序數據arr[N]，使用計數數組counting[MAX-MIN]，對每一個arr[N]中出現的元素進行計數;
• 步驟二：掃描計數數組counting[]，還原arr[N]，排序結束;

舉個栗子：

假設待排序的數組，

arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6} 

很容易發現，待排序的元素在[0, 10]之間，可以用counting[0,10]來存儲計數。

***步：統計計數

掃描未排序的數組arr[N]，對每一個出現的元素進行計數。

掃描完畢后，計數數組counting[0, 10]會變成上圖中的樣子，如粉色示意，6這個元素在arr[N]中出現了4次，在counting[0, 10]中，下標為6的位置計數是4。

第二步：還原數組

掃描計數數組counting[0, 10]，通過每個元素的計數，還原arr[N]。

如上圖粉色示意，count[0, 10]下標為6的位置計數是4，排完序是4個連續的6。

從counting下標MIN到MAX，逐個還原，填滿arr[N]時，排序結束。

神奇不神奇!!!

計數排序(Counting Sort)，總結：

• 計數排序，時間復雜度為O(n);
• 當待排序元素個數很多，但值域范圍很窄時，計數排序是很節省空間的;

希望這一分鐘，大家有收獲。

【本文為51CTO專欄作者“58沈劍”原創稿件，轉載請聯系原作者】

戳這里，看該作者更多好文