【愚公系列】2021年11月 C#版 数据结构与算法解析(计数排序)

1、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1.1 算法描述

• 找出待排序的数组中最大和最小的元素；
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

1.2 动图演示

1.3 代码实现

/// <summary>
/// 计数排序
/// </summary>
public class Program {

    public static void Main(string[] args) {
        int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };

        CountingSort(array);
        ShowSord(array);

        Console.ReadKey();
    }

    private static void ShowSord(int[] array) {
        foreach (var num in array) {
            Console.Write($"{num} ");
        }
        Console.WriteLine();
    }

    public static void CountingSort(int[] array) {
        if (array.Length == 0) return;
        int min = array[0];
        int max = min;
        foreach (int number in array) {
            if (number > max) {
                max = number;
            }
            else if (number < min) {
                min = number;
            }
        }
        int[] counting = new int[max - min + 1];
        for (int i = 0; i < array.Length; i++) {
            counting[array[i] - min] += 1;
        }
        int index = -1;
        for (int i = 0; i < counting.Length; i++) {
            for (int j = 0; j < counting[i]; j++) {
                index++;
                array[index] = i + min;
            }
        }
    }

}

1.4 算法分析

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。