桶排序算法

桶排序算法类似于计数排序算法，它是计数排序的广义形式。桶排序假设输入元素是从区间 [0, 1) 的均匀分布中抽取的。

因此，桶排序算法将区间 [0, 1) 划分为 n 个等份，并将输入元素添加到基于 (n 元素) 值下界的索引 buckets 中。由于算法假设值是均匀分布在小范围内的独立数字，因此不会有很多元素落入同一个 bucket。

例如，来看一个输入元素列表：0.08, 0.01, 0.19, 0.89, 0.34, 0.07, 0.30, 0.82, 0.39, 0.45, 0.36。桶排序会像下面这样：

桶排序算法

让我们看看这个算法如何进一步进行：

步骤 1 − 将区间划分为 n 个等份，每份称为一个 bucket。例如，如果 n 是 10，则有 10 个 buckets；否则更多。

步骤 2 − 从输入数组 A 中取出输入元素，并根据计算公式 B[i]= $\lfloor$n.A[i]$\rfloor$ 将它们添加到输出 buckets B 中。

步骤 3 − 如果有元素被添加到已占用的 buckets 中，则通过对应的 bucket 创建一个 linked list。

步骤 4 − 然后对每个 bucket 中的所有元素应用 insertion sort 进行排序。

步骤 5 − 将这些 buckets 连接在一起，从而得到输出。

伪代码

BUCKET-SORT(A)
let B[0  n  1] be a new array
n = A.length
for i = 0 to n  1
   make B[i] an empty list
for i = 1 to n
   insert A[i] into list B[$\lfloor$.[]$\rfloor$]
for i = 0 to n  1
   sort list B[i] with insertion sort
concatenate the lists B[0], B[1];  ; B[n  1] together in order

分析

桶排序算法假设输入的均匀分布，因此算法的平均情况时间复杂度为 O(n)。

示例

考虑一个输入元素列表：0.78, 0.17, 0.93, 0.39, 0.26, 0.72, 0.21, 0.12, 0.33, 0.28，使用桶排序对这些元素进行排序：

解决方案

步骤 1

从输入数组的索引 0 开始线性插入所有元素。即，先插入 0.78，然后依次插入其他元素。插入元素的位置使用公式获得：B[i]= $\lfloor$n.A[i]$\rfloor$，即 $\lfloor$10 * 0.78$\rfloor$=7。

现在，将 0.17 插入到索引 $\lfloor$10 * 0.17$\rfloor$=1。

步骤 3

将下一个元素 0.93 插入到输出 buckets 的 $\lfloor$10 * 0.93$\rfloor$=9。

步骤 4

使用公式 $\lfloor$10 * 0.39$\rfloor$=3 将 0.39 插入到索引 3。

步骤 5

将输入数组中的下一个元素 0.26 插入到位置 $\lfloor$10 * 0.26$\rfloor$=2。

步骤 6

这里开始变得复杂。现在，输入列表中的下一个元素是 0.72，需要使用公式 $\lfloor$10 * 0.72$\rfloor$=7 插入到索引 7。但第 7^th bucket 中已经有一个数字。因此，从第 7^th 索引创建一个链接，像 linked list 一样存储新数字，如下所示：

步骤 7

以类似方式将剩余数字添加到 buckets 中，通过从所需 buckets 创建 linked lists。但在将这些元素作为列表插入时，我们应用 insertion sort，即比较两个元素并将最小值添加到前面，如下所示：

步骤 8

现在，为了得到输出，将所有 buckets 连接在一起。

0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93

实现

桶排序算法的实现首先获取数组的最大元素，并决定输出桶的大小。元素基于少量计算插入到这些桶中。

在本教程中，我们在四种编程语言中执行桶排序。

#include <stdio.h>
void bucketsort(int a[], int n){ // 实现桶排序的函数
   int max = a[0]; // 获取数组中的最大元素
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   int b[max], i;
   for (int i = 0; i <= max; i++) {
      b[i] = 0;
   }
   for (int i = 0; i < n; i++) {
      b[a[i]]++;
   }
   for (int i = 0, j = 0; i <= max; i++) {
      while (b[i] > 0) {
         a[j++] = i;
         b[i]--;
      }
   }
}
int main(){
   int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
   int n = sizeof(a) / sizeof(a[0]); // n 是数组的大小
   printf("Before sorting array elements are: \n");
   for (int i = 0; i < n; ++i)
      printf("%d ", a[i]);
   bucketsort(a, n);
   printf("\nAfter sorting array elements are: \n");
   for (int i = 0; i < n; ++i)
      printf("%d ", a[i]);
}

Before sorting array elements are: 
12 45 33 87 56 9 11 7 67 
After sorting array elements are: 
7 9 11 12 33 45 56 67 87

#include <iostream>
using namespace std;
void bucketsort(int a[], int n){ // 实现桶排序的函数
   int max = a[0]; // 获取数组中的最大元素
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   int b[max], i;
   for (int i = 0; i <= max; i++) {
      b[i] = 0;
   }
   for (int i = 0; i < n; i++) {
      b[a[i]]++;
   }
   for (int i = 0, j = 0; i <= max; i++) {
      while (b[i] > 0) {
         a[j++] = i;
         b[i]--;
      }
   }
}
int main(){
   int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
   int n = sizeof(a) / sizeof(a[0]); // n 是数组的大小
   cout << "Before sorting array elements are: \n";
   for (int i = 0; i < n; ++i)
      cout << a[i] << " ";
   bucketsort(a, n);
   cout << "\nAfter sorting array elements are: \n";
   for (int i = 0; i < n; ++i)
      cout << a[i] << " ";
}

Before sorting array elements are: 
12 45 33 87 56 9 11 7 67 
After sorting array elements are: 
7 9 11 12 33 45 56 67 87

import java.io.*;
import java.util.*;
public class BucketSort {
   static void bucketsort(int a[], int n) { // 实现桶排序的函数
      int max = a[0]; // 获取数组中的最大元素
      for (int i = 1; i < n; i++)
         if (a[i] > max)
            max = a[i];
      int b[] = new int[max+1];
      for (int i = 0; i <= max; i++) {
         b[i] = 0;
      }
      for (int i = 0; i < n; i++) {
         b[a[i]]++;
      }
      for (int i = 0, j = 0; i <= max; i++) {
         while (b[i] > 0) {
            a[j++] = i;
            b[i]--;
         }
      }
   }
   public static void main(String args[]) {
      int n = 9;
      int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67};
      System.out.println("Before sorting array elements are: ");
      for (int i = 0; i < n; ++i)
         System.out.print(a[i] + " ");
      bucketsort(a, n);
      System.out.println("\nAfter sorting array elements are: ");
      for (int i = 0; i < n; ++i)
         System.out.print(a[i] + " ");
   }
}

Before sorting array elements are: 
12 45 33 87 56 9 11 7 67 
After sorting array elements are: 
7 9 11 12 33 45 56 67 87 

def bucketsort(a, n):
    max_val = max(a)
    b = [0] * (max_val + 1)
    for i in range(n):
        b[a[i]] += 1
    j = 0
    for i in range(max_val + 1):
        while b[i] > 0:
            a[j] = i
            j += 1
            b[i] -= 1
a = [12, 45, 33, 87, 56, 9, 11, 7, 67]
n = len(a)
print("Before sorting array elements are: ")
print(a)
bucketsort(a, n)
print("\nAfter sorting array elements are: ")
print(a)

Before sorting array elements are: 
[12, 45, 33, 87, 56, 9, 11, 7, 67]

After sorting array elements are: 
[7, 9, 11, 12, 33, 45, 56, 67, 87]