计数排序详解

计数排序是一种非比较的排序方法，是将数组中的元素转化为健存储在额外开盘的数组空间中。算法的复杂度O(n+k),其中K是数组元素的范围

1.算法步骤

• 初始化一个新的数组，数组长度是排序数组最大值元素 +1。
• 取数组中的元素，把元素当作新数组的坐标，如果新数组该坐标位置为空，默认设置为0，再对应值+1。
• 循环取出新数组的元素，根据计数的个数，取出同样个数的坐标值的数据，插入原来数组中，完成排序。

2.算法演示流程

3.算法代码

function countSort(arr, maxValue){

                var bucket = new Array(maxValue + 1);

                for(var i = 0; i < arr.length; i++){
                    if (!bucket[arr[i]]) {
                        bucket[arr[i]] = 0;
                    }
                    bucket[arr[i]]++;
                }

                var sortIndex = 0;

                for(var j = 0; j < bucket.length; j++){
                    while(bucket[j] > 0){
                        arr[sortIndex++] = j;
                        bucket[j]--;
                    }
                }

                return arr;
            }