計(jì)數(shù)排序
- 基本思想
- 核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開辟的數(shù)組空間中。作為一種線性時(shí)間復(fù)雜度的排序醋奠，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)
- 算法步驟
- 知道待排序數(shù)組的范圍推汽，開辟新數(shù)組空間
- 遍歷待排序數(shù)組元素，值為k，則新數(shù)組第k項(xiàng)+1
- 遍歷新數(shù)組猬错，輸出所有值
-
動(dòng)圖演示
countingSort.gif 代碼實(shí)現(xiàn)
public static void countingSort(int[] arr, int max) {
if (null == arr || arr.length < 1) return;
int[] resultTemp = new int[max + 1];
for (int value : arr) {
resultTemp[value]++;
}
int index = 0;
for (int i = 0; i <= max; i++) {
while (resultTemp[i]-- > 0) {
arr[index++] = i;
}
}
}
- 時(shí)間復(fù)雜度分析
- 計(jì)數(shù)排序是一個(gè)穩(wěn)定的排序算法。當(dāng)輸入的元素是 n 個(gè) 0到 k 之間的整數(shù)時(shí)茸歧，時(shí)間復(fù)雜度是O(n+k)兔魂，空間復(fù)雜度也是O(n+k)，其排序速度快于任何比較排序算法举娩。
- 當(dāng)k不是很大并且序列比較集中時(shí)析校，計(jì)數(shù)排序是一個(gè)很有效的排序算法。
優(yōu)化
其缺點(diǎn)也是顯而易見的铜涉，當(dāng)k很大智玻，且數(shù)據(jù)比較分散時(shí)，會(huì)占用較大無用空間芙代，十分浪費(fèi)吊奢，桶排序、基數(shù)排序都是對其的優(yōu)化。
