桶排序算法

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

因此，桶排序算法将区间[0, 1)分成'n'个相等的部分，输入元素被添加到索引为桶的索引中，其中索引基于(n × 元素)值的较低边界。由于该算法假设值为在较小范围内均匀分布的独立数字，因此不会有很多元素只落入一个桶中。

例如，让我们来看一个输入元素列表：0.08, 0.01, 0.19, 0.89, 0.34, 0.07, 0.30, 0.82, 0.39, 0.45, 0.36。桶排序将如下所示：

桶排序算法

让我们看看下面这个算法将如何继续进行：

步骤1 - 将区间分成'n'个相等的部分，每个部分称为一个桶。如果n为10，则有10个桶；否则更多。

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

步骤3 - 如果有任何元素被添加到已经占用的桶中，则通过相应的桶创建一个链表。

步骤4 - 然后我们应用插入排序对每个桶中的所有元素进行排序。

步骤5 - 这些桶被连接在一起，最终得到输出。

伪代码

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

分析

桶排序算法假设输入的独立性，因此该算法的平均时间复杂度为Θ(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插入到$\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'的桶中已经存在一个数字。因此，从索引'7'创建一个链接来存储新的数字，就像一个链表一样，如下所示：

步骤7

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

步骤8

现在，要获得输出，将所有桶连接在一起。

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){ // function to implement bucket sort
   int max = a[0]; // get the maximum element in the array
   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 is the size of array
   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){ // function to implement bucket sort
   int max = a[0]; // get the maximum element in the array
   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 is the size of array
   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) { // function to implement bucket sort
      int max = a[0]; // get the maximum element in the array
      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]