美文网首页
数据结构与算法-算法篇:排序—桶排序(九)

数据结构与算法-算法篇:排序—桶排序(九)

作者: 洒一地阳光_217d | 来源:发表于2020-10-12 10:21 被阅读0次

数据结构与算法系列文章:数据结构与算法目录

桶排序是计数排序的升级版,它将要排的数据分到多个有序的桶里,每个桶里的数据再单独排序,再把每个桶的数据依次取出,即可完成排序。

图解桶排序:

拿一组计数排序啃不掉的数据 [ 500,6123,1700,10,9999 ] 来举例。

第一步,我们创建 10 个桶,分别来装 0-1000 、1000-2000 、 2000-3000 、 3000-4000 、 4000-5000 、5000-6000、 6000-7000 、7000-8000 、8000-9000 区间的数据。


桶排序1.png

第二步,遍历原数组,对号入桶。


桶排序2.png

第三步,对桶中的数据进行单独排序,只有第一个桶中的数量大于 1 ,显然只需要排第一个桶。


桶排序3.png

最后,依次将桶中的数据取出,排序完成。


桶排序4.png

桶排序需要考虑2个问题:
1、怎么确定桶的数量?
2、桶内排序用什么方法排?

实现:
/// <summary>
/// 桶排序
/// </summary>
/// <param name="arr"></param>
public void BucketSort(int[] arr)
{
    if (arr == null || arr.Length <= 0)
    {
        return;
    }

    // 找到数组内的最大值和最小值
    int minValue = arr[0];
    int maxValue = arr[0];
    int arrLength = arr.Length;
    int arrValue;
    for (int i = 0; i < arrLength; i++)
    {
        arrValue = arr[i];
        if (arrValue < minValue)
        {
            minValue = arrValue;
        }
        else if (arrValue > maxValue)
        {
            maxValue = arrValue;
        }
    }

    // 最大和最小间差值
    int offsetValue = maxValue - minValue;

    // 初始化桶列表,桶的数量设置为原数组的长度
    List<List<int>> buckets = new List<List<int>>();
    for (int i = 0; i < arrLength; i++)
    {
        buckets.Add(new List<int>());
    }

    // 每个桶的存数区间
    float section = (float)offsetValue / (arrLength - 1);

    // 数据入桶
    for (int i = 0; i < arrLength; i++)
    {
        arrValue = arr[i];
        // 当前数除以区间得出桶的位置,减一后得出桶的下标
        int bucketIndex = Mathf.FloorToInt(arrValue / section) - 1;
        if (bucketIndex < 0)
        {
            bucketIndex = 0;
        }
        buckets[bucketIndex].Add(arrValue);
    }

    List<int> newList = new List<int>();
    // 对每个桶进行排序,这里使用插入排序
    for (int i = 0; i < buckets.Count; i++)
    {
        InsertSort(buckets[i]);
    }

    // 写入原数组
    int index = 0;
    for (int i = 0; i < buckets.Count; i++)
    {
        for (int j = 0; j < buckets[i].Count; j++)
        {
            arr[index] = buckets[i][j];
            index++;
        }
    }
}


/// <summary>
/// 插入排序
/// </summary>
/// <param name="list"></param>
public void InsertSort(List<int> list)
{
    if (list == null || list.Count <= 0)
    {
        return;
    }

    int len = list.Count;
    for (int i = 1; i < len; i++)
    {
        int temp = list[i];

        // 在已经排序好的元素中,从后往前比较
        for (int j = i - 1; j >= 0; j--)
        {
            if (list[j] > temp)
            {
                // 交换元素
                list[j + 1] = list[j];
                list[j] = temp;
            }
            else
            {
                // 有序元素未比较的元素中,没有比此元素大的了
                break;
            }
        }
    }
}

相关文章

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • 算法与数据结构路线图

    学习算法与数据结构,深刻理解计算机科学 排序算法:插入、冒泡、选择、希尔、快速、归并、堆排序、计数排序、桶排序、基...

  • Python 算法大全

    这个库涵盖了多种算法和数据结构的介绍,比如: 排序算法(冒泡排序、希尔排序、插入排序、桶排序、合并排序、快速排序、...

  • 排序算法-堆排序

    参考: Java排序算法(五):堆排序 【算法与数据结构】图说堆排序 【数据结构】排序算法:希尔、归并、快速、堆排...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 数据结构与算法-算法篇:排序—桶排序(九)

    数据结构与算法系列文章:数据结构与算法目录[https://www.jianshu.com/p/9c7afc571...

  • 10分钟看懂10大经典算法(Swift代码实现)

    排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进...

  • 排序算法

    排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序。 内部排序是数据记录在内存中...

  • Python实现十大经典排序算法

    排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进...

网友评论

      本文标题:数据结构与算法-算法篇:排序—桶排序(九)

      本文链接:https://www.haomeiwen.com/subject/yedupktx.html