算法 ： 计数排序

算法的步骤如下：

• （1）找出待排序的数组中最大和最小的元素
• （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

JavaScript 实例

function countingSort(arr, maxValue) {     var bucket = new Array(maxValue+1),         sortedIndex = 0;         arrLen = arr.length,         bucketLen = maxValue + 1;     for (var i = 0; i 0:             arr[sortedIndex] = j             sortedIndex+=1             bucket[j]-=1     return arr

Go 实例

func countingSort(arr []int, maxValue int) []int {         bucketLen := maxValue + 1         bucket := make([]int, bucketLen) // 初始为0的数组         sortedIndex := 0         length := len(arr)         for i := 0; i < length; i++ {                 bucket[arr[i]] += 1         }         for j := 0; j < bucketLen; j++ {                 for bucket[j] > 0 {                         arr[sortedIndex] = j                         sortedIndex += 1                         bucket[j] -= 1                 }         }         return arr }

Java 实例

public class CountingSort implements IArraySort {     @Override     public int[] sort(int[] sourceArray) throws Exception {         // 对 arr 进行拷贝，不改变参数内容         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);         int maxValue = getMaxValue(arr);         return countingSort(arr, maxValue);     }     private int[] countingSort(int[] arr, int maxValue) {         int bucketLen = maxValue + 1;         int[] bucket = new int[bucketLen];         for (int value : arr) {             bucket[value]++;         }         int sortedIndex = 0;         for (int j = 0; j  0) {                 arr[sortedIndex++] = j;                 bucket[j]--;             }         }         return arr;     }     private int getMaxValue(int[] arr) {         int maxValue = arr[0];         for (int value : arr) {             if (maxValue