计数排序

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

【算法描述】

具体算法描述如下：

第1步，找出待排序的数组中最大和最小的元素。

第2步，统计数组中每个值为i的元素出现的次数，存入数组C的第i项。

第3步，对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）。

第4步，反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

【代码实现】

function  countingSort(array) {
    var len = array.length, B = [], C = [], min  = max = array[0];
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min :  array[i];
        max = max >= array[i] ? max :  array[i];
        C[array[i]] = C[array[i]] ? C[array[i]]  + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j + 1] = (C[j + 1] || 0) + (C[j] ||  0);
    }
    for (var k = len - 1; k >=0; k--) {
        B[C[array[k]] - 1] = array[k];
        C[array[k]]--;
    }
    return B;
}