建站
咨詢
售后
建站咨詢
新聞中心
排序，面試中，問的比較多。
公司主營業(yè)務：成都網(wǎng)站建設、做網(wǎng)站、移動網(wǎng)站開發(fā)等業(yè)務。幫助企業(yè)客戶真正實現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。創(chuàng)新互聯(lián)是一支青春激揚、勤奮敬業(yè)、活力青春激揚、勤奮敬業(yè)、活力澎湃、和諧高效的團隊。公司秉承以“開放、自由、嚴謹、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領域給我們帶來的挑戰(zhàn)，讓我們激情的團隊有機會用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出都江堰免費做網(wǎng)站回饋大家。
時間復雜度為O(n)的排序，除了基數(shù)排序(Radix Sort)，還有計數(shù)排序(Counting Sort)。今天，1分鐘，通過幾幅圖，爭取讓大家搞懂計數(shù)排序。
計數(shù)排序的適用范圍?
待排序的元素在某一個范圍[MIN, MAX]之間。
畫外音：很多業(yè)務場景是符合這一場景，例如uint32的數(shù)字排序位于[0, 2^32]之間。
計數(shù)排序的空間復雜度?
計數(shù)排序需要一個輔助空間，空間大小為O(MAX-MIN)，用來存儲所有元素出現(xiàn)次數(shù)(“計數(shù)”)。
畫外音：計數(shù)排序的核心是，空間換時間。
計數(shù)排序的關鍵步驟?
- 步驟一：掃描待排序數(shù)據(jù)arr[N]，使用計數(shù)數(shù)組counting[MAX-MIN]，對每一個arr[N]中出現(xiàn)的元素進行計數(shù);
- 步驟二：掃描計數(shù)數(shù)組counting[]，還原arr[N]，排序結(jié)束;
舉個栗子：
假設待排序的數(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]來存儲計數(shù)。
***步：統(tǒng)計計數(shù)
掃描未排序的數(shù)組arr[N]，對每一個出現(xiàn)的元素進行計數(shù)。
掃描完畢后，計數(shù)數(shù)組counting[0, 10]會變成上圖中的樣子，如粉色示意，6這個元素在arr[N]中出現(xiàn)了4次，在counting[0, 10]中，下標為6的位置計數(shù)是4。
第二步：還原數(shù)組
掃描計數(shù)數(shù)組counting[0, 10]，通過每個元素的計數(shù)，還原arr[N]。
如上圖粉色示意，count[0, 10]下標為6的位置計數(shù)是4，排完序是4個連續(xù)的6。
從counting下標MIN到MAX，逐個還原，填滿arr[N]時，排序結(jié)束。
神奇不神奇!!!
計數(shù)排序(Counting Sort)，總結(jié)：
- 計數(shù)排序，時間復雜度為O(n);
- 當待排序元素個數(shù)很多，但值域范圍很窄時，計數(shù)排序是很節(jié)省空間的;
希望這一分鐘，大家有收獲。
【本文為專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】
戳這里，看該作者更多好文
本文名稱：拜托，面試別再問我計數(shù)排序了?。?！
本文地址：http://www.5511xx.com/article/dpijcoo.html
