基本思想是征唬，用待排序的數(shù)作為計(jì)數(shù)數(shù)組的下標(biāo)谨履，統(tǒng)計(jì)每個(gè)數(shù)字的個(gè)數(shù)琅关。然后依次輸出即可得到有序序列。
public class CountSort {
public static void countSort(int[] arr) {
if (arr == null || arr.length == 0)
return;
int max = max(arr); //尋找數(shù)組中最大值
int[] count = new int[max + 1]; //建立臨時(shí)數(shù)組, 長度為max+1
Arrays.fill(count, 0); //使用0填充數(shù)組中的元素
//使用待排序數(shù)組的元素作為臨時(shí)數(shù)組的下標(biāo)哗伯，并且統(tǒng)計(jì)每個(gè)元素的個(gè)數(shù)
for (int i = 0; i < arr.length; i++) {
count[arr[i]] = count[arr[i]] + 1;
}
int arrIndex = 0;
for (int i = 0; i <= max; i++) { //從0到max挨個(gè)遍歷
//遍歷臨時(shí)數(shù)組某下標(biāo)對應(yīng)的數(shù)組元素值荒揣，數(shù)組元素值代表下標(biāo)值出現(xiàn)了幾次篷角，依次添加到目標(biāo)數(shù)組
for (int j = 0; j < count[i]; j++) {
arr[arrIndex++] = i;
}
}
}
public static int max(int[] arr) {
int max = Integer.MIN_VALUE;
for (int ele : arr) {
if (ele > max)
max = ele;
}
return max;
}
}
計(jì)數(shù)排序.gif
