一、原理

計(jì)數(shù)排序是一種穩(wěn)定的排序算法，核心在于將輸入的數(shù)據(jù)值變化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中。作為一種限行時(shí)間復(fù)雜度的排序，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

（1）找出待排序數(shù)組中的最大值和最小值
（2）通過(guò)最大值最小值確定中間數(shù)組的長(zhǎng)度,
（3）循環(huán)舊數(shù)組計(jì)數(shù)排序，統(tǒng)計(jì)原始數(shù)組值出現(xiàn)的次數(shù)，存入中間數(shù)組C中
（4）創(chuàng)建最終數(shù)組，與原始數(shù)組長(zhǎng)度相同，反向填充數(shù)組，將每個(gè)元素i放在新數(shù)組的第C[i]項(xiàng)，每放一個(gè)元素就將C[i]減去1

最佳情況： T(n) = O(n + k)? ? 最差情況：T(n) = O(n+k)? ? 平均情況： T(n) = O(n+k)

二、代碼實(shí)現(xiàn)