计数排序

计数排序

• 只使用于小数据范围

实现

public class Solution{
    
    public void sortColors(int[] nums){
        
        // 处理元素取值范围是[0,r)的计数排序
        int r=3;

        int[] cnt = new int[r];
        for(int num:nums){
            cnt[num]++;
        }

        // [index[i],index[i+1])的值为i
        int[] index = new int[r+1];
        for(int i=0;i<r;i++){
            index[i+1]=index[i]+cnt[i];
        }
        for(int i=0;i+1<index.length;i++){
            // [index[i],index[i+1])的值为i
            for(int j=index[i];j<index[i+1];j++){
                nums[j]=i;
            }
        }
    }

    public void sortColors2(int[] nums){
        
        // 处理元素取值范围是[0,r)的计数排序
        int r=3;

        int[] cnt = new int[r];
        for(int num:nums){
            cnt[num]++;
        }

        // [index[i],index[i+1])的值为i
        int[] index = new int[r+1];
        for(int i=0;i<r;i++){
            index[i+1]=index[i]+cnt[i];
        }
        // temp 稳定排序
        int temp = new int[nums.length];
        for(int num:nums){
            temp[index[num]]=num;
            index[num]++;
        }
    }
}