桶排序
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序是将未排序的数组元素分成称为桶的若干组。，然后通过使用任意合适的排序算法或递归应用相同的存储桶算法对每个存储桶进行排序，最后，将排序后的桶组合起来形成最终的排序数组。
桶排序的过程可以理解为一种分散-聚集的方法。首先将元素分散到桶中，然后对每个桶中的元素进行排序，最后按顺序收集元素。 
要使桶排序更加高效，应尽可能做到这两点：
- 在额外空间充足的情况下，尽量增大桶的数量；
- 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中；
当输入的数据可以均匀的分配到每一个桶中时排序的速度最快；当输入的数据被分配到了同一个桶中排序的速度最慢。
桶排序的工作流程
-
这里假设有以下1个输入数组，并创建一个大小为10的数组，它的每个槽都用作存储元素的桶。
-
根据桶的范围将元素从数组插入到桶中。例如要插入元素为
0.23，把它乘上size=10，然后再把它转换成整形.23*10=2.3 ~ 2，这样就确定了把.23插入到第2个桶中。
类似的将其他元素也按同样的方式插入到桶中。 
-
对每个桶中的元素使用任意一种稳定的排序方法排后序。
-
最后聚集每个桶中的所有元素即可。
复杂度
|Time Complexity|| |—|—| |Best | O(n+k) | |Worst | O(n^2) | |Average | O(n) | |Space Complexity | O(n+k) | |Stability | Yes |
代码实现
Swift实现
// 桶排序的原理是：把原数组的值规格化成桶的索引
import Foundation
//n表示桶的个数
func bucketSort(array:inout [Float], n:Int) {
if(n <= 0){
return;
}
//创建一个大小为n的桶数组
var bucket = [[Float]](https://luowei.github.io/list/repeating: [Float](), count: n)
let min = array.min() ?? 0
let max = array.max() ?? 0
let rang = max - min //数组的值域区间
//向每个桶中添加元素
for i in 0 ..< n {
//获得 array[i] 所在的桶的索引
var bucketIndex = Int((array[i] - min) * (Float(n) / rang))
if bucketIndex == n {
bucketIndex = n - 1
}else if bucketIndex <= 0 {
bucketIndex = 0
}
// //把array中的数据规格化到 0 ..< n 之间，以适配桶的索引
// let bucketIndex = Int( array[i] * Float(n)) //索引
bucket[bucketIndex].append(array[i]) //值
}
//对每个桶中的元素集进行排序
for i in 0 ..< n {
bucket[i].sort()
}
//从桶中取出排序好的数组
var index = 0
for i in 0 ..< n { //遍历每个桶
let size = bucket[i].count
for j in 0 ..< size { //遍历每个桶中的元素
array[index] = bucket[i][j]
index += 1
}
}
}
//打印
func printBucketSort(){
var array:[Float] = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51]
//var array:[Float] = [3, 2, 5, 7, 1, 5, 4, 8, 11, 0]
bucketSort(array: &array, n: array.count)
print(array)
}
printBucketSort()
Python 实现
# Bucket Sort in Python
def bucketSort(array):
bucket = []
# Create empty buckets
for i in range(len(array)):
bucket.append([])
# Insert elements into their respective buckets
for j in array:
index_b = int(10 * j)
bucket[index_b].append(j)
# Sort the elements of each bucket
for i in range(len(array)):
bucket[i] = sorted(bucket[i])
# Get the sorted elements
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 = [.42, .32, .33, .52, .37, .47, .51]
print("Sorted Array in descending order is")
print(bucketSort(array))
Java 实现
// Bucket sort in Java
import java.util.ArrayList;
import java.util.Collections;
public class BucketSort {
public void bucketSort(float[] arr, int n) {
if (n <= 0)
return;
@SuppressWarnings("unchecked")
ArrayList<Float>[] bucket = new ArrayList[n];
// Create empty buckets
for (int i = 0; i < n; i++)
bucket[i] = new ArrayList<Float>();
// Add elements into the buckets
for (int i = 0; i < n; i++) {
int bucketIndex = (int) arr[i] * n;
bucket[bucketIndex].add(arr[i]);
}
// Sort the elements of each bucket
for (int i = 0; i < n; i++) {
Collections.sort((bucket[i]));
}
// Get the sorted array
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);
}
}
}
// Driver code
public static void main(String[] args) {
BucketSort b = new BucketSort();
float[] arr = { (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47,
(float) 0.51 };
b.bucketSort(arr, 7);
for (float i : arr)
System.out.print(i + " ");
}
}
C 实现
// Bucket sort in C
#include <stdio.h>
#include <stdlib.h>
#define NARRAY 7 // Array size
#define NBUCKET 6 // Number of buckets
#define INTERVAL 10 // Each bucket capacity
struct Node {
int data;
struct Node *next;
};
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);
// Sorting function
void BucketSort(int arr[]) {
int i, j;
struct Node **buckets;
// Create buckets and allocate memory size
buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
// Initialize empty buckets
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = NULL;
}
// Fill the buckets with respective elements
for (i = 0; i < NARRAY; ++i) {
struct Node *current;
int pos = getBucketIndex(arr[i]);
current = (struct Node *)malloc(sizeof(struct Node));
current->data = arr[i];
current->next = buckets[pos];
buckets[pos] = current;
}
// Print the buckets along with their elements
for (i = 0; i < NBUCKET; i++) {
printf("Bucket[%d]: ", i);
printBuckets(buckets[i]);
printf("\n");
}
// Sort the elements of each bucket
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = InsertionSort(buckets[i]);
}
printf("-------------\n");
printf("Bucktets after sorting\n");
for (i = 0; i < NBUCKET; i++) {
printf("Bucket[%d]: ", i);
printBuckets(buckets[i]);
printf("\n");
}
// Put sorted elements on arr
for (j = 0, i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while (node) {
arr[j++] = node->data;
node = node->next;
}
}
return;
}
// Function to sort the elements of each bucket
struct Node *InsertionSort(struct Node *list) {
struct Node *k, *nodeList;
if (list == 0 || list->next == 0) {
return list;
}
nodeList = list;
k = list->next;
nodeList->next = 0;
while (k != 0) {
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;
}
int getBucketIndex(int value) {
return value / INTERVAL;
}
void print(int ar[]) {
int i;
for (i = 0; i < NARRAY; ++i) {
printf("%d ", ar[i]);
}
printf("\n");
}
// Print buckets
void printBuckets(struct Node *list) {
struct Node *cur = list;
while (cur) {
printf("%d ", cur->data);
cur = cur->next;
}
}
// Driver code
int main(void) {
int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};
printf("Initial array: ");
print(array);
printf("-------------\n");
BucketSort(array);
printf("-------------\n");
printf("Sorted array: ");
print(array);
return 0;
}
C++ 实现
// Bucket sort in C++
#include <iomanip>
#include <iostream>
using namespace std;
#define NARRAY 7 // Array size
#define NBUCKET 6 // Number of buckets
#define INTERVAL 10 // Each bucket capacity
struct Node {
int data;
struct Node *next;
};
void BucketSort(int arr[]);
struct Node *InsertionSort(struct Node *list);
void print(int arr[]);
void printBuckets(struct Node *list);
int getBucketIndex(int value);
// Sorting function
void BucketSort(int arr[]) {
int i, j;
struct Node **buckets;
// Create buckets and allocate memory size
buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET);
// Initialize empty buckets
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = NULL;
}
// Fill the buckets with respective elements
for (i = 0; i < NARRAY; ++i) {
struct Node *current;
int pos = getBucketIndex(arr[i]);
current = (struct Node *)malloc(sizeof(struct Node));
current->data = arr[i];
current->next = buckets[pos];
buckets[pos] = current;
}
// Print the buckets along with their elements
for (i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}
// Sort the elements of each bucket
for (i = 0; i < NBUCKET; ++i) {
buckets[i] = InsertionSort(buckets[i]);
}
cout << "-------------" << endl;
cout << "Bucktets after sorted" << endl;
for (i = 0; i < NBUCKET; i++) {
cout << "Bucket[" << i << "] : ";
printBuckets(buckets[i]);
cout << endl;
}
// Put sorted elements on arr
for (j = 0, i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while (node) {
arr[j++] = node->data;
node = node->next;
}
}
for (i = 0; i < NBUCKET; ++i) {
struct Node *node;
node = buckets[i];
while (node) {
struct Node *tmp;
tmp = node;
node = node->next;
free(tmp);
}
}
free(buckets);
return;
}
// Function to sort the elements of each bucket
struct Node *InsertionSort(struct Node *list) {
struct Node *k, *nodeList;
if (list == 0 || list->next == 0) {
return list;
}
nodeList = list;
k = list->next;
nodeList->next = 0;
while (k != 0) {
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;
}
int getBucketIndex(int value) {
return value / INTERVAL;
}
// Print buckets
void print(int ar[]) {
int i;
for (i = 0; i < NARRAY; ++i) {
cout << setw(3) << ar[i];
}
cout << endl;
}
void printBuckets(struct Node *list) {
struct Node *cur = list;
while (cur) {
cout << setw(3) << cur->data;
cur = cur->next;
}
}
// Driver code
int main(void) {
int array[NARRAY] = {42, 32, 33, 52, 37, 47, 51};
cout << "Initial array: " << endl;
print(array);
cout << "-------------" << endl;
BucketSort(array);
cout << "-------------" << endl;
cout << "Sorted array: " << endl;
print(array);
}