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))

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.