Counting Sort

Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.

Example:

Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].

Solution:

When k is less than n, we could find the total counts for each number from 1 to k. Then print each number out in aascending order with respect to its count.

Complexity: Time O(n), Space O(k)

Code:

class Solution {
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */

    // counting sort: O(n) space O(k)
    public void sortColors2(int[] colors, int k) {
        if (colors == null || colors.length == 0) {
            return;
        }
        int n = colors.length;
        int[] counts = new int[k];
        for (int i = 0; i < n; i++) {
            counts[colors[i] - 1]++;
        }
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (counts[j] > 0) {
                colors[i] = j + 1;
                counts[j]--;
            } else if (counts[j] == 0) {
                j++;
                i--;
            }
        }
    }
}