十大排序算法之——计数排序算法（Java实现）及思路讲解

计数排序是一种线性时间复杂度的排序算法，适用于整数排序，特别是当整数的范围比较小的时候效率很高。计数排序不是基于比较的排序算法，其核心思想是将输入的数据值转化为键存储在额外开辟的数组空间中。计数排序是一种稳定的排序算法。

以下是一个简单的Java实现：

public class CountingSort {

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

        // 1. 得到数列的最大值和最小值，并算出差值d
        int max = arr[0];
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int d = max - min;

        // 2. 创建统计数组并计数
        int[] countArray = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i] - min]++;
        }

        // 3. 统计数组做变形，后面的元素等于前面的元素之和
        for (int i = 1; i < countArray.length; i++) {
            countArray[i] += countArray[i - 1];
        }

        // 4. 倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组
        int[] sortedArray = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sortedArray[countArray[arr[i] - min] - 1] = arr[i];
            countArray[arr[i] - min]--;
        }

        // 5. 将有序数组覆盖到原数组
        System.arraycopy(sortedArray, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {3, 0, 2, 5, 4, 1, 3, 2, 5, 6, 0, 8, 7, 1, 9};
        countingSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

这个Java程序定义了一个countingSort方法，该方法接受一个整数数组作为输入，并对其进行排序。main方法中创建了一个待排序的数组，并调用countingSort方法对其进行排序，然后打印排序后的结果。

这个算法的时间复杂度是O(n+k)，其中k是整数的范围。当k不是很大的时候，计数排序是非常高效的。但是，如果k的值非常大，那么计数排序可能会因为需要创建一个非常大的计数数组而变得不实用。此外，计数排序只能用于整数排序，对于其他类型的数据（如浮点数、字符串等），计数排序并不适用。

注意：上述代码在排序时是倒序遍历原始数组的，这是为了保证排序的稳定性。如果正序遍历，可能会导致相同元素的相对顺序发生改变，从而破坏排序的稳定性。