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

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

[[247748]]

計(jì)數(shù)排序的適用范圍?

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

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

計(jì)數(shù)排序的空間復(fù)雜度?

計(jì)數(shù)排序需要一個(gè)輔助空間，空間大小為O(MAX-MIN)，用來存儲(chǔ)所有元素出現(xiàn)次數(shù)(“計(jì)數(shù)”)。

畫外音：計(jì)數(shù)排序的核心是，空間換時(shí)間。

計(jì)數(shù)排序的關(guān)鍵步驟?

• 步驟一：掃描待排序數(shù)據(jù)arr[N]，使用計(jì)數(shù)數(shù)組counting[MAX-MIN]，對(duì)每一個(gè)arr[N]中出現(xiàn)的元素進(jìn)行計(jì)數(shù);
• 步驟二：掃描計(jì)數(shù)數(shù)組counting[]，還原arr[N]，排序結(jié)束;

舉個(gè)栗子：

假設(shè)待排序的數(shù)組，

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

很容易發(fā)現(xiàn)，待排序的元素在[0, 10]之間，可以用counting[0,10]來存儲(chǔ)計(jì)數(shù)。

***步：統(tǒng)計(jì)計(jì)數(shù)

掃描未排序的數(shù)組arr[N]，對(duì)每一個(gè)出現(xiàn)的元素進(jìn)行計(jì)數(shù)。

掃描完畢后，計(jì)數(shù)數(shù)組counting[0, 10]會(huì)變成上圖中的樣子，如粉色示意，6這個(gè)元素在arr[N]中出現(xiàn)了4次，在counting[0, 10]中，下標(biāo)為6的位置計(jì)數(shù)是4。

第二步：還原數(shù)組

掃描計(jì)數(shù)數(shù)組counting[0, 10]，通過每個(gè)元素的計(jì)數(shù)，還原arr[N]。

如上圖粉色示意，count[0, 10]下標(biāo)為6的位置計(jì)數(shù)是4，排完序是4個(gè)連續(xù)的6。

從counting下標(biāo)MIN到MAX，逐個(gè)還原，填滿arr[N]時(shí)，排序結(jié)束。

神奇不神奇!!!

計(jì)數(shù)排序(Counting Sort)，總結(jié)：

• 計(jì)數(shù)排序，時(shí)間復(fù)雜度為O(n);
• 當(dāng)待排序元素個(gè)數(shù)很多，但值域范圍很窄時(shí)，計(jì)數(shù)排序是很節(jié)省空間的;

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

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】

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