目录
一、桶排序思想
1.1 什么是桶排序
1.2 桶排序的步骤
二、基数排序思想
2.1 什么是基数排序
2.2 实现方式
2.3 图解
三、代码思路
3.1 前置工作
3.2 映射
3.3 排序
四、C语言源码
一、桶排序思想
1.1 什么是桶排序
桶排序(Bucket sort)是一种排序算法，它将要排序的数据分到有限数量的桶中，然后对每个桶进行单独排序，最后将所有的桶合并在一起得到排好序的数据。
简而言之，就是把待排序序列（数组）中的数据根据某种函数映射方法分配到若干个桶中，在分别对各个桶进行排序，最后依次按顺序取出桶中的数据。
本文介绍的基数排序就是函数映射的方法之一。
1.2 桶排序的步骤
- 首先确定桶的数量和范围，然后将数据分配到对应的桶中。
- 对每个桶中的数据进行排序，可以使用其他排序算法比如插入排序或者快速排序。
- 最后将所有桶中的数据按照顺序合并，就得到了排好序的数据。
二、基数排序思想
2.1 什么是基数排序
基数排序是一种分配式排序算法，它根据数据的每一位数字来排序，从最低位开始，依次对位数进行排序。基数排序的具体步骤如下：
- 根据待排序的数据确定最大位数，用来确定排序的轮数。
- 将所有待排序的数据统一为同样的位数，不足位数的在前面补0。
- 从最低位开始，将数据分配到0-9的10个桶中，根据当前位的数字进行分配。
- 将数据按照桶的顺序依次合并，然后增加一位进行下一轮分配和合并，直至所有位均排完，得到排好序的数据。
2.2 实现方式
- 最低位优先法(LSD)：从最低位排到最高位
- 最高位优先法(MSD)：从最高位排到最低位
2.3 图解
三、代码思路
3.1 前置工作
- 求解最高位数
//获取最大位数
int _GetMaxBit(int* array, int size)
{
int bit = 1;
int max = 10;
for (int i = 0; i < size; ++i)
{
while (array[i] >= max)
{
max *= 10;
bit++;
}
}
return bit;
}- 开辟拷贝数组
//创建桶数组
int* bucket = (int*)malloc(sizeof(int) * size);
if (bucket == NULL)
{
perror("malloc");
exit(1);
}
memset(bucket, 0, sizeof(int) * size);3.2 映射
类似于计数排序的思想，将每一位出现的次数都映射到数组中。
与计数排序不同的点是，需要存入当前的值，也是实现的难点。介绍两个思路
- 直接存入
- 采用二维数组：行数为10，对应0~9；列数为数组大小，存有符合当前位数的值。缺点是空间浪费巨大。
- 采用队列：数组存的元素是队列，直接压入队列就可以。解决了二维数组空间浪费太多的问题，缺点是C语言需要自己编写队列的底层代码
- 获取在桶数组的位置
本方法是本文推荐实现的代码。通过两个数组存储每个值在桶数组的索引位置。这样可以将数据最后都存到一个数组中，可以极大简化后序遍历的操作。
//计数数组
int count[10] = { 0 };
//位置索引数组
int index[10] = { 0 };- 计数数组：类似于基数排序，计算每一位出现多少次
// 确定对应位桶数据的个数 for (int i = 0; i < size; ++i) { //取出某一位 int k = (array[i] / radix) % 10; //对应索引位++ count[k]++; } - 索引数组：记录的是每一位第一次出现的数据在桶数组中的下标。因为总体的数据是一定的，所以获取后序数组的位置只需要加一。
桶数组中的第一个数下标一定是0
某一位的第一个元素就是 索引数组的前一个值 加上 计数数组对应位的值
// 确定在桶中的位置 for (int i = 1; i < 10; ++i) { index[i] = index[i - 1] + count[i - 1]; }
3.3 排序
- 单次
- 创建索引
- 把数据按照下标索引重新排序到桶数组中
- 将桶数组的数据拷贝回原数组
- 循环（以LSD为例）
- 位数从个位开始每次增加直到退出循环
- 每次进入新循环，两个数组的值都需要置零
四、C语言源码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>
//获取最大位数
int _GetMaxBit(int* array, int size)
{
int bit = 1;
int max = 10;
for (int i = 0; i < size; ++i)
{
while (array[i] >= max)
{
max *= 10;
bit++;
}
}
return bit;
}
//基数排序-LSD
void RadixSort_LSD(int* array, int size)
{
//获取最高位数
int maxBit = _GetMaxBit(array, size);
//创建桶数组
int* bucket = (int*)malloc(sizeof(int) * size);
if (bucket == NULL)
{
perror("malloc");
exit(1);
}
memset(bucket, 0, sizeof(int) * size);
//计数数组
int count[10] = { 0 };
//位置索引数组
int index[10] = { 0 };
int radix = 1;
for (int bit = 1; bit <= maxBit; ++bit)
{
memset(count, 0, sizeof(int) * 10);
memset(index, 0, sizeof(int) * 10);
// 确定对应位桶数据的个数
for (int i = 0; i < size; ++i)
{
//取出某一位
int k = (array[i] / radix) % 10;
//对应索引位++
count[k]++;
}
// 确定在桶中的位置
for (int i = 1; i < 10; ++i)
{
index[i] = index[i - 1] + count[i - 1];
}
// 将数据放到对应的桶中
for (int i = 0; i < size; ++i)
{
//取出某一位
int k = (array[i] / radix) % 10;
//放入桶中
bucket[index[k]++] = array[i];
}
// 将桶中排后数据拷贝回原数组
memcpy(array, bucket, sizeof(int) * size);
radix *= 10;
}
free(bucket);
bucket = NULL;
}
