前言

一种将无序数组进行排序的方法。

桶排序，wiki参考：
https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F
需要引入额外的临时数组。

这个排序算法比较特殊。
个人理解：

1. 当数据在一定范围内（小）波动，每一个桶对应一种数据，利用桶排序是极其简单快速的。
2. 当数据波动较大时，每一个桶均对应一个数据段，有点类似归并排序算法。

举个例子：

1. 若原数组是[4, 2, 2, 0]
2. 将桶数组（临时引入的数组）初始为 [0, 0, 0, 0, 0],桶的索引对应了原数组的数据区间
3. 当遍历原数组第一个元素4时，则桶数组[4] 加1，桶数组变为 [0, 0, 0, 0, 1]。用映射替代了比较，实现排序。
4. 当遍历完原数组，则桶数组变成[1, 0, 2, 0, 1]。代表了 1个0， 0个1， 2个2， 0个3， 1个4。并且只要遍历桶数组即可获得合适的排序结果。无需任何的比较。

在这里，只会讨论数据范围小，使用桶排序的情况。当范围大时，我十分可能不会考虑桶排序。

这里举例 0 - 99 范围内随机数进行排序的一种桶排序算法。再次强调一下，这种情况下，桶排序是十分简单而快速的算法。

环境

编辑器：vs2019
文件：.c类型

正文

参考代码：

#include <stdio.h>

// 桶排序
// 用映射关系替代两数之间的比较。

// 这里讨论小范围内（0-99随机数）的桶排序算法实现。
// 扩充为大范围的桶排序算法，大多数做法为链表。并且此时的桶排序，总体看来有些归并算法的意味。

// 主要思路
// 1. 实现100个桶，分别对应 0 - 99。
// 2. 每遍历到一个数，对应的桶值自增。
// 3. 最后利用桶本身的顺序，直接输出即可。


//注意，这个函数需要输入的数组值在 0 - 99范围内波动
void bucket_sort_normal(int source_array[], int source_array_length)
{
    int i, j, k;

    // 1. 创建100个桶，并初始化为 0。
    int tmp_bucket[100] = {0};

    // 2. 将桶索引视为数组的“元素”，桶索引对应的值就是数组“该元素的个数”。
    for (i = 0; i < source_array_length; i++)
    {
        // 比如， 若原数组是[4, 2, 1, 0]
        // 桶数组初始为 [0, 0, 0, 0, 0],桶的索引对应了原数组的数据区间
        // 当遍历原数组第一个元素4时，则桶数组[4] 加1，桶数组变为 [0, 0, 0, 0, 1]。用映射替代了比较，实现排序。
        tmp_bucket[source_array[i]]++;
    }

    // 遍历桶数组(桶数组长度100)，改变原数组
    j = 0;
    for (i = 0; i < 100; i++)
    {
        for (k = 0; k < tmp_bucket[i]; k++)
        {
            source_array[j] = i;
            j++;
        }

    }
}




int main()
{
    // 生成随机测试列表 0-99
    int test_list[20];
    int test_list_length = sizeof(test_list) / sizeof(int);

    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 普通桶排序
    bucket_sort_normal(test_list, test_list_length);
    printf("普通桶排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    return 0;
}

执行结果参考：

image.png

扩展

桶排序的扩展：一个桶对应多个数据。在下一篇的 基数排序 中会有体现。