本节您将系统学习桶排序算法,还会看到实现桶排序算法的 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