【数据结构】排序算法系列——桶排序（附源码+图解）

2025/12/14 15:17:45 来源：https://blog.csdn.net/Skrrapper/article/details/142771725 浏览: 次关键词：【数据结构】排序算法系列——桶排序（附源码+图解）

桶排序

算法思想

桶排序（BucketSort)，也被叫做箱排序，它将整个数据组分为n个相同大小的子区间，这类子区间或称为桶。输入数据是均匀、独立分布的，所以一般不会出现一个桶中装有过多数据的情况。作为一种排序算法，它会对每个桶中的数进行排序，然后直接遍历桶，最终就可以按照次序输出数据。
它的算法步骤大概如下所示：

设置定量数组作为每个桶的容量大小
遍历数据组，并将数据一个一个放到对应桶中
对非空桶中的数据进行排序
最后将数据按照大体排序放回原来序列中

图解

在这里插入图片描述

C语言代码解析

#define CRT_SECURE_NO_WARNINGS 1
//桶排序
#include <stdio.h>
#include <stdlib.h>	#define MAX 1000
#define BUCKET_NUM 10//建桶中节点
struct BNode
{int data;struct Node* next;
};//建桶
struct BNode* CreateNode(int data)
{struct BNode* newNode = (struct BNode*)mlooc(sizeof(struct BNode));newNode->data = data;newNode->next = NULL;return newNode;
}//插入节点到链表中
void insertNode(struct BNode* head, struct BNode* newNode)
{struct BNode* p = head;while (p->next != NULL){p = p->next;}p->next = newNode;
}//桶排序
void BucketSort(int arr[], int n)
{struct BNode* bucket[BUCKET_NUM];for (int i = 0; i < BUCKET_NUM; i++){bucket[i] = CreateNode(0);//创建多个桶}for (int i = 0; i < n; i++){int index = arr[i] / BUCKET_NUM;//确定元素所在桶的位置struct BNode* newNode = CreateNode(arr[i]);insertNode(bucket[index], newNode);//插入节点到链表中}for (int i = 0; i < BUCKET_NUM; i++)//对每个桶进行排序{struct BNode* p = bucket[i]->next;while (p != NULL){printf("%d ", p->data);p = p->next;}}
}

时间复杂度

桶排序的时间复杂度取决于以下几个因素：

将数据分配到桶的时间
对每个桶内的数据进行排序的时间
合并所有桶中的数据的时间

假设我们有 n 个元素需要排序，并且我们使用了 k 个桶。

1. 将数据分配到桶的时间复杂度

将每个元素放入对应的桶中的操作通常是一个线性的操作。对于每一个元素，确定它所属的桶位置的时间是 O(1) 的，总的时间复杂度为 O(n)。

2. 对每个桶内的数据进行排序的时间复杂度

每个桶中的数据数量决定了桶内排序的复杂度。如果所有元素均匀分布到 k 个桶中，那么每个桶中的元素大约是 n/k 个。通常，我们会在每个桶内使用一种常规的排序算法（如快速排序或插入排序）来对桶内的元素排序。

如果使用插入排序或其他 O((n/k)^2) 的排序算法来对每个桶排序，那么对所有桶排序的时间复杂度为 O(k * (n/k)^2) = O(n^2/k)。
如果使用更高效的排序算法（如快速排序，时间复杂度为 O((n/k) * log(n/k))），那么对每个桶排序的时间复杂度为 O(n/k * log(n/k))，所有桶的总排序时间复杂度为 O(n * log(n/k))。