Counting sort is a stable sorting algorithm. Count sorting uses an additional array Count_arr, where the i-th element is the number of elements with a value equal to i in the array Arr to be sorted. Then, according to the array Count_arr, the elements in Arr are arranged to the correct position.
It is divided into four steps:
1. Find the largest and smallest elements in the array to be sorted
2. Statistics the number of times each element with a value of i appears in the array, and save the i-th item of the array Count_arr
3. Accumulate all counts (starting from the first element in Count_arr, each item and the previous item are added)
4. Reversely traverse the original array: place each element i in the Count_arr(i) item of the new array, and subtract Count_arr(i) by 1 for each element.
Example:
The code copy is as follows:
/**
* Count sorting is a non-comparison-based sorting algorithm.
* This algorithm was proposed by Harold H. Seward in 1954.
* Its advantage is that when sorting integers within a certain range,
* Its complexity is Ο(n+k) (where k is the range of integers),
* Faster than any comparison sorting algorithm.
*
*/
function countSort(arr, min, max) {
var i, z = 0, count = [];
for (i = min; i <= max; i++) {
count[i] = 0;
}
for (i=0; i < arr.length; i++) {
count[arr[i]]++;
}
for (i = min; i <= max; i++) {
while (count[i]-- > 0) {
arr[z++] = i;
}
}
return arr;
}
// test
var i, arr = [];
for (i = 0; i < 100; i++) {
arr.push(Math.floor(Math.random() * (141)));
}
countSort(arr, 0, 140);