Counting Sort 計數排序

維基百科:當輸入的元素是n個0到k之間的整數時,它的運行時間是Θ(n + k)。 整數很重要 整數很重要 整數很重要 整數很重要

最壞時間複雜度{O(n+k)}

最優時間複雜度{O(n+k)}

平均時間複雜度{O(n+k)}

空間複雜度{O(n+k)}

public static int[] countingSort(int[] A) {
int[] B = new int[A.length];
// 假设A中的数据a'有,0<=a' && a' < k并且k=100
int k = 100; //數字的範圍
countingSort(A, B, k);
return B;
}
private static void countingSort(int[] A, int[] B, int k) {
int[] C = new int[k];
// 计数
for (int j = 0; j < A.length; j++) {
int a = A[j];
C[a] += 1;
}
// 求计数和
for (int i = 1; i < k; i++) { // 類似說 前面有幾個人 所以 如果當前 值是 2 表示第二大 如果是 6 表示第六大
C[i] = C[i] + C[i - 1];
}
// 整理
for (int j = A.length - 1; j >= 0; j--) {
int a = A[j];
B[C[a] - 1] = a; // 減 1 是因為從 陣列從 0 開始
C[a] -= 1; // 這大概是怕會有重複的數字 (處理重複數字)
}
}

優化的方法 (節省空間)

public static int[] countSort(int []a){
int b[] = new int[a.length];
int max = a[0], min = a[0];
for(int i : a){ //找最大最小之後可以訂出 K
if(i > max){
max = i;
}
if(i < min){
min = i;
}
}
//这里k的大小是要排序的数组中,元素大小的极值差+1
int k = max - min + 1;
int c[] = new int[k];
for(int i = 0; i < a.length; ++i){
c[a[i]-min] += 1;//优化过的地方,减小了数组c的大小
}
for(int i = 1; i < c.length; ++i){
c[i] = c[i] + c[i-1];
}
for(int i = a.length-1; i >= 0; --i){
b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
}
return b;
}

通俗地理解,例如有10個年齡不同的人,統計出有8個人的年齡比A小,那A的年齡就排在第9位,用這個方法可以得到其他每個人的位置,也就排好了序。當然,年齡有重複時需要特殊處理(保證穩定性),這就是為什麼最後要反向填充目標數組,以及將每個數字的統計減去1的原因。算法的步驟如下:

  1. 找出待排序的數組中最大和最小的元素
  2. 統計數組中每個值為i的元素出現的次數,存入數組 C 的第 i
  3. 對所有的計數累加(從C中的第一個元素開始,每一項和前一項相加)
  4. 反向填充目標數組:將每個元素i放在新數組的第C(i)項,每放一個元素就將C(i)減去1

後來想想 所謂的保證穩定性 就是 stable 的意思啦XD (所以倒著填充回來一定會保證stable,因為 重複的元素再意義上來說就是 會在當下一直減減減去(上面那行每放一個元素就減去1))