当前位置：首页 > news >正文

桶排序【算法 14】

news 2025/7/2 12:55:18

桶排序算法详解

请添加图片描述

桶排序（Bucket Sort）是一种基于分配的排序算法，适用于均匀分布在特定范围内的数据。其核心思想是将输入数据分到若干个桶（Bucket）中，每个桶分别进行排序，最后合并桶内的元素形成有序序列。桶排序的时间复杂度在最优情况下可以达到 O(n)，在处理特定类型的数值时表现良好，特别是当数据较为均匀分布时。

一、算法思想

桶排序的基本步骤如下：

创建桶：初始化若干个空桶。
分配数据到桶：根据数据值，将数据分配到对应的桶中。
对桶内数据进行排序：对每个桶中的数据使用适当的排序算法（通常是插入排序或快速排序）。
合并结果：将各个桶内的有序数据依次合并，形成最终的有序数组。

二、适用场景

桶排序的最佳场景是数据在一个均匀范围内均匀分布的情况。它广泛应用于诸如排序浮点数、计分系统、甚至某些字符串处理等任务。桶排序的高效性在于它将排序问题划分为多个局部问题（即桶内排序），然后进行较小范围的排序。

三、算法实现

我们来看桶排序的C语言实现：

#include <stdio.h>
#include <stdlib.h>#define BUCKET_SIZE 10  // 假设数据范围为 0-99，因此桶的数量为10// 定义链表节点
struct Node {int data;struct Node* next;
};// 插入排序，用于桶内排序
struct Node* insertSorted(struct Node* head, int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = value;newNode->next = NULL;// 如果链表为空或新节点小于头节点if (!head || head->data >= value) {newNode->next = head;return newNode;}// 插入节点到合适的位置struct Node* current = head;while (current->next && current->next->data < value) {current = current->next;}newNode->next = current->next;current->next = newNode;return head;
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 桶排序实现
void bucketSort(int arr[], int size) {struct Node* buckets[BUCKET_SIZE] = {NULL};// 将数据分配到桶中for (int i = 0; i < size; i++) {int index = arr[i] / BUCKET_SIZE;buckets[index] = insertSorted(buckets[index], arr[i]);}// 依次合并桶中的数据int idx = 0;for (int i = 0; i < BUCKET_SIZE; i++) {struct Node* current = buckets[i];while (current) {arr[idx++] = current->data;current = current->next;}}
}int main() {int arr[] = {29, 25, 3, 49, 9, 37, 21, 43};int size = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, size);bucketSort(arr, size);printf("排序后数组: \n");printArray(arr, size);return 0;
}

四、代码详解

创建桶数组：我们创建一个大小为 BUCKET_SIZE 的桶数组，每个桶是一个链表，目的是能够动态插入和排序数据。
插入排序桶内排序：insertSorted 函数对链表中的元素进行插入排序。在将数据放入桶的同时，它们会被有序插入到链表中。
分配数据到桶中：根据元素值的范围，将数据分配到对应的桶中。例如，假设数据范围为 0-99 且桶数量为10，数据 29 将会分配到第 2 号桶（29 / 10 = 2）。
合并桶内数据：最后，遍历每个桶并将桶内数据依次放入原数组。