问题1的解决方法是：取数组中的最大值max和最小值min，新建(max-min +1)长度的数组，数组的元素存放在新数组中的（arr[i]-min）索引处。
问题2的解决方法是：新建一个统计数组，其长度为(max-min +1)，其索引存放的是新数组该索引之前元素的和，这个和表示的是该索引（该元素）在原数组中的排序顺序，就是排第几。

4.4、计数排序的最终步骤

取无序数组arr中的最大值max和最小值min，新建(max-min +1)长度的数组newArr和长度为(max-min +1)的统计数组countArr。
遍历原数组arr，将其值作为newArr的键，元素的个数作为值存放在该键处。
遍历newArr，使统计数组countArr和newArr相同索引处存放的是newArr该索引之前元素的和。
新建一个最终数组result，反向遍历原数组，取原数组的值arr[i]-min作为索引，从统计数组countArr取出该索引的值减1，作为最终数组result的索引，值为原数组的arr[i]，同时统计数组该索引处值减1，遍历结束后，最终数组result为排序后的数组。

5、代码实现


package com.kgf.algorithm.sort;
 
/***
 * 计数排序
 */
public class CountSort {
 
    public static void main(String[] args) {
        int[] nums = {1, 4, 9, 2, 5, 3, 7, 6, 22, 23, 15, 24, 0, 3,
                4, 5, 2, 3, 5, 12, 1, 3, 4, 2, 1,
                3, 45, 1, 1};
        // 计数排序
        CountSort countSort = new CountSort();
//        countSort.sort(nums);
        int[] ints = countSort.sort2(nums);
        for (int num : ints) {
            System.out.print(num+"\t");
        }
        System.out.println();
    }
 
    /***
     * 计数排序优化
     * @param nums
     */
    public int[] sort2(int[] nums){
        //找到数组最大值和最小值
        int max = nums[0],min = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (max<nums[i]){
                max = nums[i];
            }
            if (min>nums[i]){
                min = nums[i];
            }
        }
 
        //首先创建一个固定长度的空数组
        int[] newArr = new int[max-min+1];
        //将nums的值作为下标，数量作为值存入newarr
        for (int i = 0; i < nums.length; i++) {
            newArr[nums[i]-min]++;
        }
 
        //为了防止相同的元素顺序不一致，使用countArr数组进行排序
        int[] countArr = new int[newArr.length];
        for (int i = 0; i < newArr.length; i++) {
            if (i==0){
                countArr[i] = newArr[i];
                continue;
            }
            countArr[i] = newArr[i]+countArr[i-1];
        }
        //定义一个数组用来存储排序后的元素
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[countArr[nums[i]-min]-1] = nums[i];
            countArr[nums[i]-min]--;
        }
        return result;
    }
 
    /***
     * 简单的计数方法
     * @param nums
     * @return
     */
    public void sort(int[] nums){
        //找到数组最大值
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (max<nums[i]){
                max = nums[i];
            }
        }
        //首先创建一个固定长度的空数组
        int[] newArr = new int[max+1];
        //将nums的值作为下标，数量作为值存入newarr
        for (int i = 0; i < nums.length; i++) {
            newArr[nums[i]]++;
        }
        //创建一个最终的空数组存储
        int j = 0;
        for (int i = 0; i < newArr.length; i++) {
            for (int k = 0; k < newArr[i]; k++) {
                nums[j] = i;
                j++;
            }
        }
    }
}

6、总结

计数排序是非比较排序，时间复杂度是O(n+k)，空间复杂度是O(k)，是稳定算法。（n表示的是数组的个数，k表示的max-min+1的大小）

时间复杂度是O(n+k)：通过上面的代码可知最终的计数算法花费的时间是3n+k，则时间复杂度是O(n+k)。

空间复杂度是O(k)：如果出去最后的返回数组，则空间复杂度是2k，则空间复杂度是O(k)

稳定算法：由于统计数组可以知道该索引在原数组中排第几位，相同的元素其在原数组中排列在后面，其从原数组的后面遍历，其在最终数组中的索引也在后面，所以相同的元素其相对位置不会改变。

7、计数排序的类比

计数排序的重点是：将序列中的元素作为键存储在额外的数组空间中，通过遍历来排序。类似于：我要给一系类弹珠从小到大排列，我可以拿一个模具，模具上有从小到大的孔洞，我把弹珠放进孔洞中，最后只要从模具中从小到大的孔洞中倒出弹珠即可。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/913047