9.计数排序

算法 > 排序算法算法排序算法

发布时间 : 2024-04-14 18:39

字数:1.8k 阅读 :

评论:

9.计数排序

9.计数排序

9.1 基础知识

核心思想

计数排序的核心思想是统计每个元素的个数，然后根据元素的值依次放置到有序的输出序列中。它不通过比较元素的大小，而是通过统计元素出现的次数来完成排序。

算法步骤

统计元素个数：遍历待排序数组，统计每个元素出现的次数，创建一个计数数组。
计算累积次数：对计数数组进行累加，得到每个元素在输出序列中的最后一个位置。
构建有序序列：遍历原始数组，根据计数数组中元素的累积次数，将元素放置到输出序列中相应的位置。
更新计数数组：每放置一个元素到输出序列，相应元素的计数减一。

时间复杂度

计数排序的时间复杂度为 O(n + k)，其中 n 是数组大小，k 是数组中元素的范围。计数排序在元素范围不大的情况下性能优越。

空间复杂度

计数排序是一种原地排序算法，但需要额外的计数数组，其空间复杂度为 O(k)，其中 k 是元素范围的大小。

稳定性

计数排序是稳定的排序算法，相同元素的相对顺序在排序后保持不变。

适用场景

适用于元素范围不大的情况，例如整数排序。由于不进行元素比较，计数排序在某些特定场景下性能较好。一般不涉及负数。

代码步骤

得最值：得到待排序数组中的最大值。
完成计数数组：初始化计数数组为，遍历待排序数组统计各元素个数累积次数。
遍历计数数组排序原数组：遍历原始数组，根据计数数组放置元素到输出序列，并减小计数数组的计数。

总体说明

计数排序是一种简单而有效的排序算法，特别适用于范围有限的整数排序。它通过统计元素个数避免了比较操作，具有线性时间复杂度。然而，由于需要额外的计数数组，当元素范围较大时，其空间复杂度可能较高。在一些特殊场景下，计数排序是一种值得考虑的排序方法。

9.2 思路框架

CountingSort(ref int[] array)
{
    找到数组中的最大值 maxValue

    创建一个计数数组 countArray，大小为 maxValue+1

    遍历原始数组，统计每个元素的出现次数并存储在计数数组中

    初始化一个索引变量 index 为 0

    遍历计数数组
    {
        循环：当前计数大于 0
        {
            将当前计数数组索引值依次放入原始数组，并将索引递增
            当前计数减一
        }
    }
}

9.3 纯净代码

static void CountingSort(ref int[] array)
{
    int maxValue = SortHelpTool.FindMaxValue(array);
    int[] countArray = new int[maxValue + 1];

    foreach (var num in array)
    {
        countArray[num]++;
    }

    int index = 0;

    for (int i = 0; i < countArray.Length; i++)
    {
        while (countArray[i] > 0)
        {
            array[index++] = i;
            countArray[i]--;
        }
    }
}

require("Lesson01_SortHelpTool")

-- 计数排序函数
function CountingSort(array)
    local maxValue = SortHelpTool.FindMaxValue(array)
    local countArray = {}
    for i = 1, maxValue + 1 do
        countArray[i] = 0
    end

    for _, num in ipairs(array) do
        countArray[num + 1] = (countArray[num + 1] or 0) + 1
    end

    local index = 1

    for i = 1, maxValue + 1 do
        while countArray[i] > 0 do
            array[index] = i - 1
            index = index + 1
            countArray[i] = countArray[i] - 1
        end
    end
end

SortHelpTool.PrintArray(SortHelpTool.arrayToSort,"排序前")
CountingSort(SortHelpTool.arrayToSort)
SortHelpTool.PrintArray(SortHelpTool.arrayToSort,"排序后")

9.4 带注释代码

using System;
using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用计数排序函数
        CountingSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 计数排序函数
    static void CountingSort(ref int[] array)
    {
        // 找到数组中的最大值，确定计数数组的大小
        int maxValue = SortHelpTool.FindMaxValue(array);

        // 初始化计数数组
        int[] countArray = new int[maxValue + 1];

        // 统计每个元素出现的次数
        foreach (var num in array)
        {
            countArray[num]++; // 增加对应元素值的计数
        }

        Console.WriteLine("生成的计数数组:");
        SortHelpTool.PrintArray(countArray);

        // 根据计数数组还原排序后的数组

        //还原排序后原数组索引标识
        int index = 0;

        //遍历计数数组
        for (int i = 0; i < countArray.Length; i++)
        {
            //当该数有计数时
            while (countArray[i] > 0)
            {
                array[index++] = i; // 将计数数组中的值按顺序还原到原数组
                countArray[i]--; // 减少计数

                Console.WriteLine("减少计数后的计数数组为:");
                SortHelpTool.PrintArray(countArray);

                Console.WriteLine("将计数数组中的值按顺序还原后的数组:");
                SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
            }
        }
    }
}

9.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

生成的计数数组:
0 1 1 1 1 1 1 1 1 1 1
减少计数后的计数数组为:
0 0 1 1 1 1 1 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 8 1 7 3 10 4 6 9
减少计数后的计数数组为:
0 0 0 1 1 1 1 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 8 1 7 3 10 4 6 9
减少计数后的计数数组为:
0 0 0 0 1 1 1 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 1 7 3 10 4 6 9
减少计数后的计数数组为:
0 0 0 0 0 1 1 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 7 3 10 4 6 9
减少计数后的计数数组为:
0 0 0 0 0 0 1 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 3 10 4 6 9
减少计数后的计数数组为:
0 0 0 0 0 0 0 1 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 6 10 4 6 9
减少计数后的计数数组为:
0 0 0 0 0 0 0 0 1 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 6 7 4 6 9
减少计数后的计数数组为:
0 0 0 0 0 0 0 0 0 1 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 6 7 8 6 9
减少计数后的计数数组为:
0 0 0 0 0 0 0 0 0 0 1
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 6 7 8 9 9
减少计数后的计数数组为:
0 0 0 0 0 0 0 0 0 0 0
将计数数组中的值按顺序还原后的数组:
1 2 3 4 5 6 7 8 9 10

排序后的数组:
1 2 3 4 5 6 7 8 9 10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com