本教程显示了如何用Java编写计数排序程序。计数排序是一种整数排序算法。它不同于其他基于比较的算法，例如合并排序，选择排序，因为它不会通过比较值进行排序。在计数排序中，对每个元素的频率进行计数，并使用它来计算每个元素的最终位置。

使用计数排序时的限制之一是必须知道元素的范围(最大元素)。计数排序还需要额外的空间来存储元素的频率。

计数排序Java程序

public class CountingSort {
  public static void main(String[] args) {
    int[] arr = {10, 5, 15, 6, 12, 5, 8, 9, 0, 10, 1, 7};
    // Find the maximum element in the input array
    int max = findMaxElement(arr);
    System.out.println("Max Value in input array-" + max);
    System.out.println("Original Array- " + Arrays.toString(arr));
    int[] sortedArr = countingSort(arr, max+1);
    System.out.println("Sorted array after counting sort- " + Arrays.toString(sortedArr));
  }
	
  private static int findMaxElement(int[] arr) {
    int max = arr[0];
    for(int val : arr) {
      if (val > max)
        max = val;
    }
    return max;
  }
	
  private static int[] countingSort(int[] arr, int range){
    int[] result = new int[arr.length];
    int[] count = new int[range];
    //Calculate frequency of each element, put it in count array
    for(int i = 0; i < arr.length; i++){
        count[arr[i]]++;
    }
    System.out.println("Count array- " + Arrays.toString(count));
    
    // Modify count array to get the final position of elements
    for(int i = 1; i < range; i++){
        count[i] = count[i] + count[i-1];
    }
    System.out.println("Modified count array- " + Arrays.toString(count));
    
    // Add elements to output sorted array 
    for(int i = 0; i < arr.length; i++){
      result[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }
    return result;
  }
}

输出：

Max Value in input array-15
Original Array- [10, 5, 15, 6, 12, 5, 8, 9, 0, 10, 1, 7]
Count array- [1, 1, 0, 0, 0, 2, 1, 1, 1, 1, 2, 0, 1, 0, 0, 1]
Modified count array- [1, 2, 2, 2, 2, 4, 5, 6, 7, 8, 10, 10, 11, 11, 11, 12]
Sorted array after counting sort- [0, 1, 5, 5, 6, 7, 8, 9, 10, 10, 12, 15]

计算排序时间和空间复杂度

如果要排序的元素数是N并且元素的范围是0到K，则第一个循环将迭代输入数组以获取计数数组，即O(n)。修改Count数组以获得步骤具有复杂度O(k)的最终位置。第三个循环再次迭代输入数组，因此该步骤的时间复杂度为O(n)。总计为O(2n + k)，或者我们可以说Counting sort的时间复杂度为O(n + k)，因为常量未使用Big O表示法进行计数。

计数数组占用k个空间，输出数组的长度与输入数组的长度相同，即N。因此，计数排序的空间复杂度为O(n + k)。