建站
咨詢
售后
建站咨詢
新聞中心
排序，面試中，問的比較多。
公司主營業(yè)務(wù)：成都網(wǎng)站建設(shè)、做網(wǎng)站、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。創(chuàng)新互聯(lián)推出都江堰免費(fèi)做網(wǎng)站回饋大家。
時(shí)間復(fù)雜度為O(n)的排序，除了基數(shù)排序(Radix Sort)，還有計(jì)數(shù)排序(Counting Sort)。今天，1分鐘，通過幾幅圖，爭(zhēng)取讓大家搞懂計(jì)數(shù)排序。
計(jì)數(shù)排序的適用范圍?
待排序的元素在某一個(gè)范圍[MIN, MAX]之間。
畫外音：很多業(yè)務(wù)場(chǎng)景是符合這一場(chǎng)景，例如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é)省空間的;
希望這一分鐘，大家有收獲。
【本文為專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
戳這里，看該作者更多好文
本文名稱：拜托，面試別再問我計(jì)數(shù)排序了?。?！
URL鏈接：http://www.dlmjj.cn/article/dpijcoo.html
