排序算法 之 桶排序（Bucket Sort）

排序算法 之 桶排序（Bucket Sort）

1. 基础概念

1.1 定义

桶排序是一种线性时间排序算法，通过将数据分配到有限数量的桶中进行分治，然后对每个桶内的元素进行单独排序。最终将排序后的桶按顺序合并得到整体有序的数据。

1.2 特点

• 平均时间复杂度为 O(n)，但依赖于数据分布的均匀性。
• 需要额外的空间来存储桶。
• 适合处理小范围的实数数据。

1.3 使用场景

桶排序适用于以下场景：

• 输入数据范围有限，分布较为均匀。
• 需要对浮点数、分数或特定区间内的数据进行排序。
• 适用于实时性要求较高的应用场景。

2. 实现与操作

2.1 核心操作实现

以下是使用 C 语言实现桶排序的代码。

#include <stdio.h> #include <stdlib.h> // 定义每个桶的容量 #define BUCKET_CAPACITY 10 // 定义链表节点，用于处理桶中的数据 typedef struct Node { float value; struct Node* next; } Node; // 函数声明 void bucketSort(float arr[], int n); Node* insertNode(Node* head, float value); void printArray(float arr[], int n); // 桶排序主函数 void bucketSort(float arr[], int n) { // 创建桶数组 Node* buckets[n]; for (int i = 0; i < n; i++) { buckets[i] = NULL; } // 将数据分配到桶中 for (int i = 0; i < n; i++) { int index = arr[i] * n; // 桶索引 buckets[index] = insertNode(buckets[index], arr[i]); } // 合并每个桶的数据 int index = 0; for (int i = 0; i < n; i++) { Node* current = buckets[i]; while (current) { arr[index++] = current->value; current = current->next; } } } // 插入数据到链表（升序插入） Node* insertNode(Node* head, float value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->value = value; newNode->next = NULL; if (!head || head->value >= value) { newNode->next = head; return newNode; } Node* current = head; while (current->next && current->next->value < value) { current = current->next; } newNode->next = current->next; current->next = newNode; return head; } // 打印数组 void printArray(float arr[], int n) { for (int i = 0; i < n; i++) { printf("%.2f ", arr[i]); } printf("\n"); } // 测试桶排序 int main() { float arr[] = {0.42, 0.32, 0.23, 0.52, 0.73, 0.25, 0.12}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前:\n"); printArray(arr, n); bucketSort(arr, n); printf("排序后:\n"); printArray(arr, n); return 0; } </stdlib.h></stdio.h>

2.2 代码详解

上述代码的关键步骤如下：

• 分配 n 个桶，每个桶为一个链表。
• 将每个元素映射到相应的桶中。
• 对每个桶进行插入排序（链表实现）。
• 将所有桶中的数据依次合并到原数组。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 平均时间复杂度：O(n)，取决于数据分布的均匀性和桶内排序效率。
• 最差时间复杂度：O(n^2)，当所有数据集中到同一个桶时。

3.2 空间复杂度

需要额外的 O(n) 空间来存储桶，具体取决于输入数据的范围和分布。

4. 优缺点与局限性

4.1 优点

• 对于特定分布的输入数据效率极高。
• 可以处理浮点数和非整数数据。

4.2 缺点与局限性

• 适用范围有限，仅适用于数据分布均匀且范围已知的情况。
• 需要额外的空间来存储桶。

5. 常见应用场景

桶排序适用于以下场景：

• 对浮点数数组进行排序。
• 数据分布均匀且已知范围。

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc -o bucket_sort bucket_sort.c

6.2 测试用例

运行测试用例后输出如下：

排序前:
0.42 0.32 0.23 0.52 0.73 0.25 0.12 
排序后:
0.12 0.23 0.25 0.32 0.42 0.52 0.73