# 桶排序算法 > 原文： [https://www.programiz.com/dsa/bucket-sort](https://www.programiz.com/dsa/bucket-sort) #### 在本教程中，您將學習存儲桶排序的工作方式。 此外，您還將找到使用 C，C++ ，Java 和 Python 進行存儲桶排序的工作示例。 存儲桶排序是一種排序技術，它通過首先將元素劃分為幾個稱為**存儲桶**的組來對元素進行排序。 每個**存儲桶**內部的元素都可以使用任何合適的排序算法進行排序，也可以遞歸調用同一算法。 創建了幾個存儲桶。 每個存儲桶都填充有特定范圍的元素。 存儲桶中的元素使用任何其他算法進行排序。 最后，收集存儲桶中的元素以獲取排序后的數組。 桶排序的過程可以理解為**，分散收集**方法。 首先將元素分散到存儲桶中，然后對存儲桶的元素進行排序。 最后，元素按順序收集。  桶排序工作 * * * ## 桶排序如何工作？ 1. 假設輸入數組為：  輸入數組 創建一個大小為 10 的數組。此數組的每個插槽用作存儲元素的存儲桶。  每個位置是一個存儲區的數組 2. 將元素插入數組中的存儲桶。 根據鏟斗的范圍插入元素。 在我們的示例代碼中，我們有每個范圍從 0 到 1、1 到 2、2 到 3，...（`n-1`）到`n`的存儲桶。 假設輸入元素為`.23`。 它乘以`size = 10`（即`.23*10=2.3`）。 然后，將其轉換為整數（即??`2.3≈2`）。 最后，將`.23`插入桶 2 中。  將元素從數組 插入到存儲桶中。同樣，`.25`也插入到同一存儲桶中。 每次都采用浮點數的下限值。 **如果我們使用整數作為輸入，則必須將其除以間隔（此處為 10）以獲得下限值。** 同樣，其他元素也插入各自的存儲桶中。  將所有元素從數組 插入存儲桶中 3. 使用任何穩定的排序算法對每個存儲桶的元素進行排序。 在這里，我們使用了`quicksort`（內置函數）。  對每個存儲區中的元素進行排序 4. 收集每個存儲桶中的元素。 通過遍歷存儲桶并在每個循環中將單個元素插入原始數組來完成。 一旦將存儲桶中的元素復制到原始數組中，該元素將被擦除。  從每個存儲桶中收集元素 * * * ## 桶排序算法 ``` bucketSort() create N buckets each of which can hold a range of values for all the buckets initialize each bucket with 0 values for all the buckets put elements into buckets matching the range for all the buckets sort elements in each bucket gather elements from each bucket end bucketSort ``` * * * ## Python，Java 和 C/C++ 示例 ```py # 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; } ``` ```cpp // 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); } ``` * * * ## 復雜度 * **最壞情況的復雜度**： `O(n^2)` 當數組中有近距離的元素時，它們很可能放在同一存儲桶中。 這可能會導致某些存儲桶中的元素數量比其他存儲桶更多。 它使復雜度取決于用于對存儲區元素進行排序的排序算法。 當元素的順序相反時，復雜度將變得更加糟糕。 如果使用插入排序對存儲桶中的元素進行排序，則時間復雜度變為`O(n^2)`。 * **最佳情況復雜度**： `O(n+k)` 當元素在桶中均勻分布且每個桶中元素數量幾乎相等時，會發生這種情況。 如果存儲桶中的元素已經被排序，那么復雜度就會變得更好。 如果使用插入排序對存儲桶中的元素進行排序，則最佳情況下的總體復雜度將是線性的，即。`O(n+k)`。`O(n)`是制造存儲桶的復雜度，`O(k)`是使用在最佳情況下具有線性時間復雜度的算法對存儲桶的元素進行排序的復雜度。 * **平均情況復雜度**： `O(n)` 當元素在數組中隨機分布時發生。 即使元素分布不均勻，存儲桶排序也會在線性時間內運行。 直到鏟斗大小的平方和在元素總數中呈線性關系時，它才成立。 * * * ## 桶排序應用 在以下情況下使用存儲桶排序： * 輸入均勻地分布在一個范圍內。 * 有浮點值