如何实现计数排序算法？

计数排序(Counting Sort)是一种稳定的排序算法。它通过计算每个元素出现的次数,然后依次将元素放入正确位置完成排序。

我们可以实现计数排序算法如下:

public void countingSort(int[] nums) {
    if (nums.length == 0) return;

    int maxVal = Integer.MIN_VALUE;
    for (int num : nums) maxVal = Math.max(maxVal, num);

    int[] counts = new int[maxVal + 1];

    for (int num : nums) counts[num]++;

    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        for (int j = 0; j < counts[i]; j++) {
            nums[index++] = i;
        } 
    }
}

算法流程:

1. 找到数组中的最大值maxVal。
2. 根据最大值初始化计数数组counts,下标代表元素的值,值代表出现次数。
3. 遍历原数组,将每个元素的值作为下标,给对应的计数加1。
4. 遍历计数数组,将每个元素按出现次数放入原数组。
5. 重复步骤4,直到计数数组遍历完成,排序结束。

时间复杂度O(n + k),k为数组最大值,空间复杂度O(k)。

所以,计数排序的关键是:

1. 找到最大值确定计数数组大小。
2. 遍历原数组统计每个元素出现次数。
3. 遍历计数数组,将元素按出现次数放入原数组。
4. 重复步骤3,完成排序。