一筒__自摸
本节您将系统学习桶排序算法，还会看到实现桶排序算法的 C、Java 以及 Python 程序。
桶排序算法的核心思想是：将待排序序列中的元素根据规则分组，每一组采用快排、插入排序等算法完成排序，然后再将所有组进行合并，最终就可以得到一个有序序列。
也就是说，采用桶排序算法对目标序列进行排序，会经历下图所示的三个阶段：
桶排序算法的工作原理
我们以对如下序列进行升序排序为例，详细讲解桶排序算法的工作原理。
针对序列存储的元素的特点，这里采用的分组规则是：将各个元素乘以 10 然后取整，得到的值即为该元素的组号。由此，我们可以得到如下所示的几个分组：
接下来，选择适当的排序算法对各组元素分别进行升序排序，最终可以得到如下的各个组：
最后，通过逐个遍历各个组中的元素，即可得到我们想要的升序序列。
桶排序算法的具体实现
如下为实现桶排序算法的 C 语言程序：
#include <stdio.h>
#include <stdlib.h>
#define N 7 // 待排序序列中的元素个数
#define NBUCKET 6 // 桶的数量
#define INTERVAL 10 // 每个桶能存放的元素个数
//建立桶
struct Node {
float data;
struct Node *next;
};
void BucketSort(float arr[]);
struct Node *InsertionSort(struct Node *list);
void print(float arr[]);
int main() {
float array[N] = { 0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51 };
BucketSort(array);
print(array);
return 0;
}
// 桶排序，arr 为待排序序列
void BucketSort(float arr[]) {
int i, j;
struct Node **buckets;
// 创建所有桶
buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
// 设置每个桶为空桶
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = NULL;
}
// 根据规定，将 arr 中的每个元素分散存储到各个桶中
for (i = 0; i < N; ++i) {
struct Node *current;
int pos = arr[i] * 10; //根据规则，确定元素所在的桶
//创建存储该元素的存储块，并连接到指定的桶中
current = (struct Node *)malloc(sizeof(struct Node));
current->data = arr[i];
current->next = buckets[pos];
buckets[pos] = current;
}
// 调用自定义的排序算法，对各个桶进行排序
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = InsertionSort(buckets[i]);
}
// 合并所有桶内的元素
for (j = 0, i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while (node) {
arr[j++] = node->data;
node = node->next;
}
}
}
// 自定义的排序算法，用于对各个桶内元素进行排序
struct Node *InsertionSort(struct Node *list) {
struct Node *k, *nodeList;
if (list == NULL || list->next == NULL) {
return list;
}
nodeList = list;
k = list->next;
nodeList->next = NULL;
while (k != NULL) {
struct Node *ptr;
if (nodeList->data > k->data) {
struct Node *tmp;
tmp = k;
k = k->next;
tmp->next = nodeList;
nodeList = tmp;
continue;
}
for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) {
if (ptr->next->data > k->data)
break;
}
if (ptr->next != 0) {
struct Node *tmp;
tmp = k;
k = k->next;
tmp->next = ptr->next;
ptr->next = tmp;
continue;
}
else {
ptr->next = k;
k = k->next;
ptr->next->next = 0;
continue;
}
}
return nodeList;
}
void print(float ar[]) {
int i;
for (i = 0; i < N; ++i) {
printf("%.2f ", ar[i]);
}
}
如下为实现桶排序算法的 Java 程序：
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public static void bucketSort(float[] arr) {
int n = arr.length;
if (n <= 0)
return;
@SuppressWarnings("unchecked")
ArrayList<Float>[] bucket = new ArrayList[n];
// 创建空桶
for (int i = 0; i < n; i++)
bucket[i] = new ArrayList<Float>();
// 根据规则将序列中元素分散到桶中
for (int i = 0; i < n; i++) {
int bucketIndex = (int) arr[i] * n;
bucket[bucketIndex].add(arr[i]);
}
// 对各个桶内的元素进行排序
for (int i = 0; i < n; i++) {
Collections.sort((bucket[i]));
}
// 合并所有桶内的元素
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0, size = bucket[i].size(); j < size; j++) {
arr[index++] = bucket[i].get(j);
}
}
}
public static void main(String[] args) {
float[] arr = { (float) 0.42, (float) 0.32, (float) 0.23, (float) 0.52, (float) 0.25, (float) 0.47,
(float) 0.51 };
bucketSort(arr);
for (float i : arr)
System.out.print(i + " ");
}
}
如下为实现桶排序算法的 Python 程序：
格式化复制
#桶排序算法，array 为待排序序列 def bucketSort(array): bucket = [] # 创建空桶 for i in range(len(array)): bucket.append([]) # 根据规则将所有元素分散到各个桶中 for j in array: index_b = int(10 * j) bucket[index_b].append(j) # 分别对各个桶进行排序 for i in range(len(array)): bucket[i] = sorted(bucket[i]) # 合并所有桶内的元素 k = 0 for i in range(len(array)): for j in range(len(bucket[i])): array[k] = bucket[i][j] k += 1 return array array = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51] print(bucketSort(array))
以上各个程序的输出结果为：
0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52
