11.基数排序

算法 > 排序算法 算法 排序算法
发布时间 :
字数:2.2k 阅读 : 评论:
  1. 11.基数排序
    1. 11.1 基础知识
      1. 核心思想
      2. 算法步骤
      3. 时间复杂度
      4. 空间复杂度
      5. 稳定性
      6. 适用场景
      7. 代码步骤
      8. 总结说明
    2. 11.2 思路框架
    3. 11.3 纯净代码
    4. 11.4 带注释代码
    5. 11.5 运行结果

11.基数排序

11.1 基础知识

核心思想

基数排序是一种非比较型排序算法，它将整数按位数切割成不同的数字，然后按每个位数分别比较。通过先低位后高位的排序，实现对整数序列的排序。通俗理解就是先根据个位值的分桶，桶内排序后丢出去。再对十位的值进行分桶，桶内排序再丢出去，以此推类。

算法步骤

  • 确定排序的位数： 找到最大的数，确定其位数作为排序的轮数。
  • 按位分配： 从最低位开始，将数字按照当前位的值分配到相应的桶中。
  • 桶内排序： 对每个桶中的数字进行排序，可以使用其他排序算法，也可以递归地使用基数排序。
  • 合并桶： 将各个桶中的数字按顺序合并得到排序结果。

时间复杂度

基数排序的时间复杂度为O(d * (n + k))，其中d是最大数字的位数，n是数字个数，k是基数（桶的数量）。

空间复杂度

基数排序是稳定的排序算法，其空间复杂度为O(n + k)，主要消耗在桶的数量和桶内排序所需的空间。

稳定性

基数排序是一种稳定的排序算法，因为在分配到桶和桶内排序时，相同数值的元素相对位置不发生变化。

适用场景

基数排序适用于对整数或字符串等具有线性关系的数据进行排序，特别是当数据位数不太大的情况下，效果较好。

代码步骤

  1. RadixSort 函数，接收一个整数数组进行基数排序。调用 RadixSortInternal 函数传入数组和数组的位数，作为递归入口。
  2. RadixSortInternal 函数，接收数组和当前位数。按照当前位数的值进行分桶，并递归调用自身对每个桶进行排序。
  3. BucketSort 函数，用于对桶内元素进行排序，可以选择其他排序算法，如计数排序或插入排序。

总结说明

基数排序是一种非常有效的排序算法，尤其在位数不大的情况下表现出色。其稳定性和适用于具有线性关系的数据特点使得它在某些场景下比较优越。但需要注意的是，对于浮点数等不适用于线性关系的数据，基数排序可能不是最佳选择。

11.2 思路框架

RadixSort(ref int[] array)
{
    获取数组中最大值
    获取最大值的位数

    循环对每一位进行桶排序
}

BucketSort(ref int[] array, int digit)
{
    定义基数为10的桶列表

    将数组中的元素按当前位数分配到对应的桶中

    将排序好的桶中的元素依次放回原数组中
}

11.3 纯净代码

static void RadixSort(ref int[] array)
{
    int maxNumber = SortHelpTool.FindMaxValue(array);
    int maxDigitCount = SortHelpTool.CountDigits(maxNumber);


    for (int digit = 1; digit <= maxDigitCount; digit++)
    {
        BucketSort(ref array, digit);
    }
}


static void BucketSort(ref int[] array, int digit)
{
    const int radix = 10;
    
    List<List<int>> buckets = new List<List<int>>(radix);
    for (int i = 0; i < radix; i++)
    {
        buckets.Add(new List<int>());
    }
    
    foreach (int num in array)
    {
        int bucketIndex = SortHelpTool.GetDigit(num, digit);
        buckets[bucketIndex].Add(num);
    }
    
    int index = 0;
    foreach (var bucket in buckets)
    {
        foreach (int num in bucket)
        {
            array[index++] = num;
        }
    }
}

require("Lesson01_SortHelpTool")

-- 基数排序函数
function RadixSort(array)
    local maxNumber = SortHelpTool.FindMaxValue(array)
    local maxDigitCount = SortHelpTool.CountDigits(maxNumber)

    for digit = 1, maxDigitCount do
        BucketSort(array, digit)
    end
end

-- 桶排序辅助函数，用于基数排序中的每一轮
function BucketSort(array, digit)
    local radix = 10
    local buckets = {}

    for i = 1, radix do
        buckets[i] = {}
    end

    for _, num in ipairs(array) do
        local bucketIndex = SortHelpTool.GetDigit(num, digit)+1
        table.insert(buckets[bucketIndex], num)
    end

    local index = 1
    for i = 1, radix do
        for _, num in ipairs(buckets[i]) do
            array[index] = num
            index = index + 1
        end
    end
end

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

11.4 带注释代码

using System;
using System.Collections.Generic;
using Lesson01_概述;

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

        // 调用基数排序函数
        RadixSort(ref SortHelpTool.arrayToSort);

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

    // 基数排序函数
    static void RadixSort(ref int[] array)
    {
        // 获取数组中的最大值，以确定最大位数
        int maxNumber = SortHelpTool.FindMaxValue(array);//最大值
        int maxDigitCount = SortHelpTool.CountDigits(maxNumber);//最大位数

        // 使用桶排序进行每一位的排序,从个位到最高有效位
        for (int digit = 1; digit <= maxDigitCount; digit++)
        {
            BucketSort(ref array, digit);
        }
    }
    
    // 桶排序辅助函数，按照指定位数进行排序
    static void BucketSort(ref int[] array, int digit)
    {
        const int radix = 10; // 基数为10，因为使用十进制

        // 创建桶List 每一个List<int>是一个桶 传入桶的基数初始化桶List
        List<List<int>> buckets = new List<List<int>>(radix);
        for (int i = 0; i < radix; i++)
        {
            buckets.Add(new List<int>());
        }

        // 将元素分配到对应的桶中
        foreach (int num in array)
        {
            int bucketIndex = SortHelpTool.GetDigit(num, digit);//获取数字的指定位数的值
            buckets[bucketIndex].Add(num);//对应值的桶添加改元素
        }

        // 进行排序后，该位有序。比如传进来digit是1，那么个位就是有序的。
        for (int i = 0; i < buckets.Count; i++)
        {
            Console.WriteLine($"排序位数{digit}，索引为{i}的桶的元素：");
            SortHelpTool.PrintList(buckets[i]);
        }
        
        // 合并桶中的元素得到最终有序数组
        int index = 0;
        foreach (var bucket in buckets)
        {
            foreach (int num in bucket)
            {
                array[index++] = num;
                
                Console.WriteLine($"逐个添加桶中元素到结果数组：");
                SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
            }
        }
    }
}

11.5 运行结果

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

排序位数1，索引为0的桶的元素：
10
排序位数1，索引为1的桶的元素：
1
排序位数1，索引为2的桶的元素：
2
排序位数1，索引为3的桶的元素：
3
排序位数1，索引为4的桶的元素：
4
排序位数1，索引为5的桶的元素：
5
排序位数1，索引为6的桶的元素：
6
排序位数1，索引为7的桶的元素：
7
排序位数1，索引为8的桶的元素：
8
排序位数1，索引为9的桶的元素：
9
逐个添加桶中元素到结果数组：
10 2 8 1 7 3 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 8 1 7 3 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 1 7 3 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 7 3 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 3 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 5 10 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 5 6 4 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 5 6 7 6 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 5 6 7 8 9
逐个添加桶中元素到结果数组：
10 1 2 3 4 5 6 7 8 9
排序位数2，索引为0的桶的元素：
1 2 3 4 5 6 7 8 9
排序位数2，索引为1的桶的元素：
10
排序位数2，索引为2的桶的元素：

排序位数2，索引为3的桶的元素：

排序位数2，索引为4的桶的元素：

排序位数2，索引为5的桶的元素：

排序位数2，索引为6的桶的元素：

排序位数2，索引为7的桶的元素：

排序位数2，索引为8的桶的元素：

排序位数2，索引为9的桶的元素：

逐个添加桶中元素到结果数组：
1 1 2 3 4 5 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 2 3 4 5 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 3 4 5 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 4 5 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 5 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 6 6 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 6 7 7 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 6 7 8 8 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 6 7 8 9 9
逐个添加桶中元素到结果数组：
1 2 3 4 5 6 7 8 9 10

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

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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏