CountingSort

算法思路及原理

1. 扫描整个集合arr，对每一个arr中的元素，在线性表count中存储对应的数量；
2. 扫描整个线性表count，对count中记录的每一个元素，按顺序放到对应位置，并将count对应元素数量减1。

算法分析

时间复杂度

O(N+K)

空间复杂度

需要额外的储存count的空间K，和储存重新排序好的arr的temp空间N，即O(n+k)

稳定性

优化前因为不能确定相同元素的位置，所以不稳定。优化后稳定

for (int i = 1; i < count.length; i++) {
    count[i] = count[i] + count[i-1];
}
System.out.println(Arrays.toString(count));

int[] temp = new int[arr.length];
// 由后向前按顺序将对应的元素赋值给temp中，所以相同元素的前后顺序不变
for (int i = arr.length-1; i >= 0; i--) {
    temp[--count[arr[i]]] = arr[i];
}

实现代码

import java.util.Arrays;

public class CountingSort2 {
    public static void main(String[] args) {
        int[] arr = {2, 4, 3, 6, 2, 7, 1, 3, 5};
        sort(arr, 1, 7); // 最小为1，最大为7
    }
    static void sort(int[] arr, int start, int end) {
        int[] count = new int[end - start + 1];
        for (int value : arr) {
            count[value - start]++;
        }

        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i-1];
        }

        int[] temp = new int[arr.length];
        for (int i = arr.length-1; i >= 0; i--) {
            temp[--count[arr[i]-start]] = arr[i];
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp[i];
        }
    }
    static void printArr(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
        System.out.println();
    }
}