package sort;
public class CountSorting {
public static void countSort(int[] nums){
if (null == nums || nums.length < 2)
return;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
//找数组的最大值和最小值
for (int num: nums){
if (num < min)
min = num;
if (max < num)
max = num;
}
int[] ans = new int[max - min + 1];//构造能放[min,max]的连续数值数组；
//统计每个位置有多少元素
for (int i = 0; i < nums.length; i++){
ans[nums[i] - min]++;
}
int k = 0;
//依次将ans不为0的下标加min复制到nums，nums即为有序数组
for (int h = 0; h < ans.length; h++){
while (ans[h] > 0){//处理nums中重复的元素，当ans[i]计数为0时退出
nums[k++] = h + min;//此处下标+min
ans[h]--; //nums中添加了一个元素，ans计数值就减1
}
}
}
//最好情况：所有元素重复，T(n) = 2n（比较）+ n (统计) + n (判断) = 4n = O(n)
//此时空间复杂度为O(1)
//最坏情况：所有元素均不相同，假设k=max-min（数值范围)
// T(n)=2n(比较)+n(统计)+k(判断) = 4n = O(n)，空间复杂度：O(k)
//平均时间复杂度：O(n+k) ，空间复杂度为：O(k)，稳定算法，适合数组范围限定且不大的情况。
public static void main(String[] args){
int[] nums = {2,0,1,9,1,0,2,8};
countSort(nums);
for (int num: nums)
System.out.print(num+" ");
}
}
