数据结构与算法-算法篇：排序—桶排序（九）

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

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

图解桶排序：

拿一组计数排序啃不掉的数据 [ 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;
            }
        }
    }
}