计数排序是用于在特定范围之间进行分类元素的特殊排序技术。
假设元素属于1到k范围，然后计数排序可用于在O(n)次中排序元素。

计数排序的基本思想以查找小于x的元素数，因此x可以放在正确的位置。

计数排序的步骤：

• 拍摄数组来存储每个元素的计数。假设阵列元素包含1到k，然后用K初始化计数数组。
• 现在添加计数数组的元素，因此每个元素都存储其先前元素的求和。
• 修改的计数阵列在实际排序阵列中存储元素的位置。
• 基于修改的计数阵列迭代阵列并将元素放在正确的序列中，并减少计数1.

用于计数排序的Java程序：

package org.arpit.theitroad;
 
import java.util.Arrays;
 
public class CountingSortMain {
 
 public static void main(String[] args) {
 System.out.println("Before Sorting : ");
 int arr[]={1,4,7,3,4,5,6,3,4,8,6,4,4};
 System.out.println(Arrays.toString(arr));
 arr=countingSort(arr);
 System.out.println("=======================");
 System.out.println("After Sorting : ");
 System.out.println(Arrays.toString(arr));
 }
 
 static int[] countingSort(int arr[])
 {
 int n = arr.length;
 
 //The result will store sorted array
 int result[] = new int[n];
 
 //Initialize count array with 9 as array contains elements from range 1 to 8.
 int count[] = new int[9];
 for (int i=0; i<9; ++i)
 count[i] = 0;
 
 //store count of each element in count array
 for (int i=0; i<n; ++i)
 ++count[arr[i]];
 
 //Change count[i] so that count[i] now contains actual
 //position of this element in output array
 for (int i=1; i<=8; ++i)
 count[i] += count[i-1];
 
 for (int i = 0; i<n; ++i)
 {
 result[count[arr[i]]-1] = arr[i];
 --count[arr[i]];
 }
 
 return result;
 }
 
}

运行上面的程序时，我们将得到以下输出：

Before Sorting : 
[1, 4, 7, 3, 4, 5, 6, 3, 4, 8, 6, 4, 4]
=======================
After Sorting : 
[1, 3, 3, 4, 4, 4, 4, 4, 5, 6, 6, 7, 8]

时间复杂度= o(n)