10.桶排序

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

10.桶排序

10.1 基础知识

核心思想

桶排序是一种排序算法，它将数据分割成有限数量的桶（或区间），每个桶内的元素再进行单独排序。最后，将各个桶中的元素合并成有序序列。

算法步骤

  • 划分桶: 将数据分割成若干个桶，每个桶对应一个特定的范围或区间。
  • 各桶排序: 对每个非空桶进行单独排序，可以使用其他排序算法如插入排序或快速排序。
  • 合并桶: 将所有桶的元素按照顺序合并，得到最终有序序列。

时间复杂度

桶排序的时间复杂度取决于桶的个数以及桶内排序的算法。在最均匀的情况下，时间复杂度为O(n + k)，其中n是元素个数，k是桶的数量。

空间复杂度

桶排序是一种原地排序算法，但需要额外的空间来存储桶。空间复杂度为O(n + k)，其中n是元素个数，k是桶的数量。

稳定性

桶排序可以是稳定的，具体取决于桶内排序算法的稳定性。

适用场景

  • 适用于元素均匀分布在一定范围内的情况，以确保桶的利用率高。
  • 对于大规模数据集，尤其在外部排序（外部存储）的场景中，桶排序表现优越。
  • 可以与其他排序算法结合使用，例如在每个桶内使用快速排序。

代码步骤

  1. 桶划分: 初始化桶集合，通过得到数组最大值和一定的规则，将元素根据范围分配到不同的桶中。
  2. 桶内排序: 对每个非空桶进行排序。
  3. 桶合并: 将所有桶按顺序合并成最终有序序列并返回。

总体说明

桶排序是一种高效的排序算法，特别适用于数据均匀分布的情况。尽管在某些特定场景下表现优秀，但在数据分布不均匀或桶划分不当的情况下，可能性能下降。在实际应用中，桶排序常作为辅助排序手段，与其他算法结合以提高性能。

10.2 思路框架

static void BucketSort(ref int[] array)
{
    计算数组中的最大值

    计算桶的数量，可以根据实际情况调整

    创建一个桶的集合，对每个桶初始化

    遍历数组，将每个元素按照一定规则放入对应的桶中

    对每个桶中的元素进行排序（例如，可以使用快速排序）

    将排序后的元素放回原始数组中
}

10.3 纯净代码

static void BucketSort(ref int[] array)
{
    int maxValue = SortHelpTool.FindMaxValue(array);
    int bucketCount = maxValue / 5 + 1;
    List<List<int>> buckets = new List<List<int>>(bucketCount);

    for (int i = 0; i < bucketCount; i++)
    {
        buckets.Add(new List<int>());
    }

    foreach (int num in array)
    {
        int bucketIndex = num / 5;
        buckets[bucketIndex].Add(num);
    }
    
    foreach (var bucket in buckets)
    {
        if (bucket.Count > 0)
        {
            bucket.Sort();
        }
    }

    int index = 0;
    foreach (var bucket in buckets)
    {
        foreach (int num in bucket)
        {
            array[index++] = num;
        }
    }
}

require("Lesson01_SortHelpTool")

-- 桶排序函数
function BucketSort(array)
    local maxValue = SortHelpTool.FindMaxValue(array)
    local bucketCount = math.floor(maxValue / 5) + 1
    local buckets = {}

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

    for _, num in pairs(array) do
        local bucketIndex = math.floor(num / 5) + 1
        table.insert(buckets[bucketIndex], num)
    end

    for _, bucket in pairs(buckets) do
        if #bucket > 0 then
            table.sort(bucket)
        end
    end

    local index = 1
    for _, bucket in pairs(buckets) do
        for _, num in pairs(bucket) do
            array[index] = num
            index = index + 1
        end
    end
end

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

10.4 带注释代码

using Lesson01_概述;

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

        // 调用桶排序函数
        BucketSort(ref SortHelpTool.arrayToSort);

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

    // 桶排序函数
    static void BucketSort(ref int[] array)
    {
        // 得到数组中的最大值
        int maxValue = SortHelpTool.FindMaxValue(array);

        // 计算桶的数量，可以根据实际情况调整
        int bucketCount = maxValue / 5 + 1;
        
        // 创建桶List 每一个List<int>是一个桶 传入桶的数量初始化桶List
        List<List<int>> buckets = new List<List<int>>(bucketCount);

        // 初始化桶
        for (int i = 0; i < bucketCount; i++)
        {
            buckets.Add(new List<int>());
        }

        // 将元素分配到对应的桶中
        foreach (int num in array)
        {
            // 元素通过一定的计算规则 看看放在哪个桶中 这里使用除法 假如商相同的说明再相近范围内 放在同一个桶
            int bucketIndex = num / 5; 
            
            // 对应桶添加对应元素
            buckets[bucketIndex].Add(num);
        }

        for (int i = 0; i < buckets.Count; i++)
        {
            Console.WriteLine($"索引为{i}的桶的元素：");
            SortHelpTool.PrintList(buckets[i]);
        }

        
        // 对每个非空桶进行排序，可以使用其他排序算法如插入排序或快速排序
        foreach (var bucket in buckets)
        {
            // 桶要非空
            if (bucket.Count > 0)
            {
                //对桶进行排序
                bucket.Sort();
            }
        }

        for (int i = 0; i < buckets.Count; i++)
        {
            Console.WriteLine($"排序后，索引为{i}的桶的元素：");
            SortHelpTool.PrintList(buckets[i]);
        }
        
        // 合并桶中的元素得到最终有序数组
        // 合并的最终数组索引
        int index = 0;
        //遍历桶List 逐个添加桶中元素添加到最终数组
        foreach (var bucket in buckets)
        {
            foreach (int num in bucket)
            {
                array[index++] = num;
                Console.WriteLine($"逐个添加桶中元素到最终数组：");
                SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
            }
        }
    }
}

10.5 运行结果

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

索引为0的桶的元素：
2 1 3 4
索引为1的桶的元素：
5 8 7 6 9
索引为2的桶的元素：
10
排序后，索引为0的桶的元素：
1 2 3 4
排序后，索引为1的桶的元素：
5 6 7 8 9
排序后，索引为2的桶的元素：
10
逐个添加桶中元素到最终数组：
1 2 8 1 7 3 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 8 1 7 3 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 1 7 3 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 4 7 3 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 4 5 3 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 4 5 6 10 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 4 5 6 7 4 6 9
逐个添加桶中元素到最终数组：
1 2 3 4 5 6 7 8 6 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

×

喜欢就点赞,疼爱就打赏