桶排序演算法

桶排序演算法類似於計數排序演算法，因為它只是計數排序的廣義形式。桶排序假設輸入元素是從區間[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]