计数排序 | 黄皖's Blog

前言

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。

基本思想：

就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

实现过程

为方便理解我还准备了动图：

实现代码

package fg;

/**
 * @author 皖
 * @data 2020.5.13
 */
public class Counting{
    public static int[] countSort (int[] arr) {
        if (arr == null || arr.length < 2)
        return arr;
        int n=arr.length;
        int max=arr[0];
        //寻找数组的最大值
        for (int i = 1; i <n ; i++) {
            if (max<arr[i])
                max=arr[i];
            }
            //创建一个临时数组大小为max
            int []temp=new int[max+1];
            //统计元素出现次数
            for (int i = 0; i <n ; i++) {
                temp[arr[i]]++;

            }
            int k=0;
            //把临时数组统计好的数据汇总到原数组
            for ( int i = 0; i <=max ; i++) {
                for (int j = temp[i]; j >0 ; j--) {
                    arr[k++]=i;

                }

            }

        return arr;

    }

    public static void main (String[] args) {
        int[] arr = {5, 8, 2, 4, 6, 9, 7, 0, 1, 3};

        System.out.print("排序前:  ");
        print(arr);

        countSort(arr);  //此时已经成功

        System.out.print("排序后:  ");
        print(arr);
    }

    // 打印数组
    public static void print(int[] arr) {
        if (arr == null)    return;
        //遍历并且输出
        for(int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}