Counting sort [No. 43]

The running time of counting sort is O(n), and usually, the running time of sorting algorithms will be either O(n^2) or O(n lgn), the reason why counting sort is O(n) is that it doesn't have the comparison.In fact, the sorting is hidden from line 19 to line 27.

public static int[] CountingSort(int[] A) {
    int max = A[0];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > max) {
            max = A[i];
        }
    }
    int[] C = new int[max];
    int[] B = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        C[A[i] - 1] += 1;
    }
    for (int i = 1; i < C.length; i++) {
        C[i] += C[i - 1];
    }
    //array C record the position of A[i] in array B
    for (int i = 0; i < A.length; i++) {
        B[C[A[i] - 1] - 1] = A[i];
        C[A[i] - 1]--;
    }
    for (int i = 0; i < A.length; i++) {
        A[i] = B[i];
    }
    return A;
}

The code segment above is only suitable for the case in which all the elements in the array are non-negative. If the array

has negative element, we can simply 'shift' the element, such as the minimum element will be considered as 0. I use 'span'

to shift the element.

public static int[] CountingSort(int[] A) {
    int max = A[0];
    int min = A[0];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > max) max = A[i];
        if (A[i] < min) min = A[i];
    }
    int[] C = new int[max - min + 1];
    int[] B = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        C[A[i] - min] += 1;
    }
    for (int i = 1; i < C.length; i++) {
        C[i] += C[i - 1];
    }
  //array C record the position of A[i] in array B
    for (int i = 0; i <  A.length; i++) {
        B[C[A[i] - min] - 1] = A[i];
        C[A[i] - min]--;
    }
    for (int i = 0; i < A.length; i++) {
        A[i] = B[i];
    }
    return A;
}