Counting Sort

计数排序算法

基本属性

• 空间复杂度

  • O(MAX-MIN) 用空间换时间

• 时间复杂度

  • O(n)

• 适用范围

  • 待排序数组值域较窄，而待排序元素个数较多时，比较节省空间，反之则非常浪费空间

  • 适用所有数字排序 int32 int64 [0, 2^32] ~ [0, 2^64] 之间

• 关键步骤

  • Step 1: 遍历待排序数据array[N]，在计数器数组(count[MAX-MIN])中记录出现次数； e.g.count[array[index]] ++

  • Step 2: 遍历count[MAX-MIN]，得到 array[N]，排序结束

• 代码

public static void main(String[] args) {
    int[] array = new int[]{5, 7, 1, 8, 9, 2, 3, 4, 1, 3, 6, 2, 4, 0};
    int[] count = new int[9 - 0 + 1];
    // counting sort
    for (int i = 0; i < array.length; i++) {
        count[array[i]] = count[array[i]] + 1;
    }
    // iterate counting
    for (int i=0;i<count.length;i++){
        int temp = count[i];
        for(int j=0;j<temp;j++){
            System.out.print(i);
        }
    }
    // result
    // 01122334456789
}

• 图示