算法：用Java实现计数排序(CountSort)

本文我准备用Java实现计数排序（计数排序由于其独有的排序方式，只适合待排序的数字都是非负整数的情况）。具体的排序算法过程已经在注释里面了，大家可以复制代码到IDE里面，用DEBUG模式研究算法的过程：

import java.util.Arrays;
import java.util.Random;

/**
 * @author LiYang
 * @ClassName CountSort
 * @Description 计数排序算法
 * @date 2019/11/5 17:17
 */
public class CountSort {
    
    /**
     * 计数排序算法(CountSort)
     * 注意：计数排序由于其独有的排序方式，只适合
     * 待排序的数字都是非负整数的情况
     * @param arr 待排序数组
     */
    public static int[] countSort(int[] arr) {
        //求最大值，得出数组长度
        int max = 0;
        
        //遍历求最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        
        //用作计数的数组，初始化都为0
        //注意，这里数组的大小是max+1
        //因为数组是从0开始的
        int[] count = new int[max + 1];
        
        //遍历计数
        for (int i = 0; i < arr.length; i++) {
            //重要：count数组的作用是，如果这个数字出现了两次，
            //则以这个数字作为下标的值就是2，也就是计数
            //count数组就是计算每个数字出现了多少次，然后再
            //从大到小（数组遍历）地将这些计数还原成有序数组
            count[arr[i]] ++;
        }
        
        //用作装排序结果的数组
        int[] result = new int[arr.length];
        
        //上述数组的记录下标
        int index = 0;
        
        //遍历计数的数组，并处理计数结果
        for (int i = 0; i < count.length; i++) {
            
            //遇到计了数的
            if (count[i] > 0){
                
                //重要：i的大小就是元素大小，count[i]就是该元素的个数
                //将i元素装count[i]次
                for (int elementNum = 0; elementNum < count[i]; elementNum++) {
                    result[index++] = i;
                }
            }
        }//计数排序统计完毕
        
        //返回计数排序完成的有序新数组
        return result;
    }

    /**
     * 验证计数排序算法
     * @param args
     */
    public static void main(String[] args) {
        //待排序数组
        int[] arr = new int[30];

        //随机数类
        Random random = new Random();

        //随机生成排序数组（50以内的整数）
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(50);
        }

        //打印待排序数组
        System.out.println("计数排序前：" + Arrays.toString(arr));

        //进行计数排序，返回排好序的新数组
        int[] countSortedArr = countSort(arr);

        //这里可以将排好序的数组，重新赋给原来的数组，保持之前的操作
        arr = countSortedArr;

        //打印计数排序后的数组
        System.out.println("计数排序后：" + Arrays.toString(arr));
    }
    
}

运行 CountSort 类的main方法，计数排序算法测试通过：

计数排序前：[27, 31, 44, 0, 40, 37, 35, 28, 37, 9, 19, 30, 2, 40, 11, 5, 23, 9, 41, 6, 13, 34, 21, 14, 1, 8, 16, 1, 3, 42]
计数排序后：[0, 1, 1, 2, 3, 5, 6, 8, 9, 9, 11, 13, 14, 16, 19, 21, 23, 27, 28, 30, 31, 34, 35, 37, 37, 40, 40, 41, 42, 44]