C语言桶排序（附带源码和解析）
桶排序是一种分配式排序算法，它的工作原理是将待排序的元素分散到若干个“桶”中，然后对每个桶中的元素进行排序，最后将所有桶中的元素依次取出，即完成了对整个数据集的排序。
这种方法特别适用于待排序的元素分布在一个已知的区间内的情况。
桶排序的基本原理
桶排序的核心思想是将数据分散到有限数量的桶中，每个桶代表一个特定的区间范围。算法会遍历原始数据，将每个元素放入对应的桶中。放置完成后，我们对每个非空桶中的元素进行排序（可以使用任何排序算法）。最后，我们按照桶的顺序，将每个桶中的元素依次取出，就得到了完整的有序序列。
桶排序的效率很大程度上取决于数据的分布情况。如果数据分布比较均匀，桶排序的时间复杂度接近于 O(n)，这使得它在某些情况下比基于比较的排序算法（如快速排序）更加高效。
桶排序的步骤详解
- 确定桶的数量：根据待排序数据的范围和分布特征，选择合适的桶数量。
- 创建桶：通常使用数组或链表来表示桶。
- 将元素分配到桶中：遍历原始数据，根据某种映射函数将每个元素分配到对应的桶中。
- 对每个桶内的元素排序：可以使用任何排序算法，如插入排序或快速排序。
- 合并桶：按照桶的顺序，将各个桶中的元素依次取出，形成最终的有序序列。
C语言实现桶排序
下面是一个使用 C 语言实现桶排序的示例代码：
#include <stdio.h>
#include <stdlib.h>
#define BUCKET_SIZE 10
#define ARRAY_SIZE 100
// 链表节点结构
struct Node {
int data;
struct Node* next;
};
// 函数声明
void bucketSort(int arr[], int n);
void insertionSort(struct Node* list);
void printArray(int arr[], int n);
int main() {
int arr[ARRAY_SIZE];
int i;
// 生成随机数组
for (i = 0; i < ARRAY_SIZE; i++) {
arr[i] = rand() % 100;
}
printf("原始数组:\n");
printArray(arr, ARRAY_SIZE);
bucketSort(arr, ARRAY_SIZE);
printf("排序后的数组:\n");
printArray(arr, ARRAY_SIZE);
return 0;
}
// 桶排序函数
void bucketSort(int arr[], int n) {
int i, j;
struct Node* buckets[BUCKET_SIZE];
// 初始化桶
for (i = 0; i < BUCKET_SIZE; i++) {
buckets[i] = NULL;
}
// 将元素分配到桶中
for (i = 0; i < n; i++) {
int bucketIndex = arr[i] / 10; // 简单的映射函数
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = arr[i];
newNode->next = buckets[bucketIndex];
buckets[bucketIndex] = newNode;
}
// 对每个桶进行排序
for (i = 0; i < BUCKET_SIZE; i++) {
insertionSort(buckets[i]);
}
// 合并桶
int index = 0;
for (i = 0; i < BUCKET_SIZE; i++) {
struct Node* current = buckets[i];
while (current != NULL) {
arr[index++] = current->data;
current = current->next;
}
}
// 释放内存
for (i = 0; i < BUCKET_SIZE; i++) {
struct Node* current = buckets[i];
while (current != NULL) {
struct Node* temp = current;
current = current->next;
free(temp);
}
}
}
// 插入排序函数（用于桶内排序）
void insertionSort(struct Node* list) {
struct Node* sorted = NULL;
struct Node* current = list;
while (current != NULL) {
struct Node* next = current->next;
if (sorted == NULL || sorted->data >= current->data) {
current->next = sorted;
sorted = current;
} else {
struct Node* search = sorted;
while (search->next != NULL && search->next->data < current->data) {
search = search->next;
}
current->next = search->next;
search->next = current;
}
current = next;
}
}
// 打印数组函数
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
运行结果：
原始数组: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 30 62 23 67 35 29 2 22 58 69 67 93 56 11 42 29 73 21 19 84 37 98 24 15 70 13 26 91 80 56 73 62 70 96 81 5 25 84 27 36 5 46 29 13 57 24 95 82 45 14 67 34 64 43 50 87 8 76 78 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39 排序后的数组: 3 5 5 8 12 13 13 14 15 15 19 26 27 27 29 29 29 29 39 43 45 46 49 54 56 56 57 58 59 68 69 76 77 78 86 87 88 94 95 96 98 99 21 19 84 37 98 24 15 70 13 26 91 80 56 73 62 70 96 81 5 25 84 27 36 5 46 29 13 57 24 95 82 45 14 67 34 64 43 50 87 8 76 78 88 84 3 51 54 99 32 60 76 68 39 12 26 86 94 39
总结
桶排序是一种独特而强大的排序算法，它通过巧妙地利用数据分布特征来提高排序效率。
桶排序的时间复杂度分析较为复杂，因为它严重依赖于数据的分布情况和所使用的内部排序算法。在最佳情况下，当输入数据均匀分布时，桶排序的时间复杂度接近 O(n)。然而，在最坏情况下，如果所有元素都被分到同一个桶中，时间复杂度可能退化到 O(n^2)（假设使用比较排序作为桶内排序算法）。
桶排序的空间复杂度为 O(n+k)，其中 n 是待排序元素的数量，k 是桶的数量。这是因为除了原始数组外，我们还需要额外的空间来存储桶。
桶排序特别适用于以下情况：
- 待排序的数据分布在一个已知的区间内
- 数据分布相对均匀
- 有大量数据需要排序
- 内存空间充足
在处理浮点数排序、数据库中的外部排序等场景中，桶排序常常能发挥出色的性能。
你可能还想关注其它 9 种排序算法：
- C语言冒泡排序（附带源码和解析）
- C语言快速排序（附带源码和解析）
- C语言选择排序（附带源码和解析）
- C语言插入排序（附带源码和解析）
- C语言希尔排序（附带源码和解析）
- C语言归并排序（附带源码和解析）
- C语言堆排序（附带源码和解析）
- C语言计数排序（附带源码和解析）
- C语言基数排序（附带源码和解析）
声明：《算法系列教程》为本站“54笨鸟”官方原创，由国家机构和地方版权局所签发的权威证书所保护。
