十大经典排序算法-计数排序

排序算法

编程算法

发布日期: 2020-11-18

文章字数: 646

阅读时长: 2 分

前言

本文重点讲解十大经典排序算法的计数排序

要点

计数排序（Counting Sort）是一个非基于比较的稳定的线性时间排序算法，该算法于1954年由 Harold H. Seward 提出。

基本思想

根据待排序集合中最大元素和最小元素的差值范围，申请额外空间。
遍历待排序集合，将每一个元素出现的次数记录到元素值对应的额外空间内。
对额外空间内数据进行计算，得出每一个元素的正确位置。
将待排序集合每一个元素移动到计算得出的正确位置上。

代码实现

以下代码由java实现

public class CountingSort {

    /**
     * 计数排序
     * @param arr
     * @return
     */
    public static int[] sort(int[] arr) {
        if (arr.length <= 0) {
            return null;
        }
        // 初始化结果数组
        int[] result = new int[arr.length];
        // 用于对值进行统计 未计算最大值和最小值的差值 计算可节省开辟空间
        int[] count = new int[findMax(arr) + 1];
        for (int i = 0; i < arr.length; i++) {
            // 把数值当坐标进行统计
            count[arr[i]]++;
        }
        /**
         * TODO 不稳定计数排序
         */
        /*for (int i = 0, j = 0; i < count.length; i++) {
            while(count[i]-- > 0) result[j++] = i;
        }*/
        /**
         * TODO 稳定计数排序
         */
        // 累加数组
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        // 对应 累加数组 进行递减倒排
        for (int i = arr.length - 1; i >= 0; i--) {
            result[--count[arr[i]]] = arr[i];
        }
        return result;
    }

    public static int findMax(int[] arr) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 3, 6, 8, 1, 2, 3, 11, 52, 32, 11, 23};
        System.out.println(Arrays.toString(sort(arr)));
    }
}