计数排序

十大经典排序算法

计数排序（Counting sort）是一种非基于比较的排序算法，他的排序原理和桶排序有点类似，不同的是桶排序中桶的尺寸比较小，有些桶里可能有不同的元素，所以桶排序中还要对每个桶进行单独排序。计算排序可以把它看做有一个非常大的桶，足够存储所有的元素，并且每个桶里只能有相同的元素，取的时候从桶值最小的开始取。如下图所示。

private void countingSort(int[] nums) {
    int length = nums.length;
    int max = Arrays.stream(nums).max().getAsInt();
    int min = Arrays.stream(nums).min().getAsInt();
    int bucketLength = max - min + 1;// 桶的大小。
    int[] buckets = new int[bucketLength];
    for (int i = 0; i < length; i++)
        buckets[nums[i] - min]++;// 把数组元素放到对应的桶里。
    // 遍历所有桶，取出桶里的元素。
    for (int i = 0, j = 0; j < bucketLength; j++) {
        if (buckets[j] == 0)// 当前桶里元素的个数。
            continue;
        for (int k = 0; k < buckets[j]; k++)
            nums[i++] = j + min;
    }
}

稳定性分析

从前往后遍历数组，相同的值在桶里的相对顺序并没有被打乱，从桶里取值的时候相同的值也是先取前面的，所以是稳定的。我们看下代码中有 3 个 for 循环，其中第一个 for 循环的时间复杂度是 O(n) ，第二个和第三个属于嵌套，嵌套的时间复杂度是 O(n+m) ， m 是桶的大小，所以计数排序总的时间复杂度是 O(n+m) 。

时间复杂度：O(n+m)，m是数组中最大值和最小值的差，也是桶的大小。
稳定性：稳定

相关链接