桶排序

桶排序（Bucket Sort）是一種非比較型排序算法，其工作原理是將待排序的數據分到有限數量的桶中，然後對每個桶中的數據進行排序，最後將各個桶中的數據依次合併，得到有序序列。桶排序的性能取決於數據的分布和桶的數量。當數據分布均勻時，桶排序可以達到線性時間複雜度O(n)。桶排序不是比較排序，因此不受O(n log n)下限的影響。

桶排序的步驟包括：

設定一個定量的數組當作空桶。

遍歷輸入數據，並且把數據一個一個放到對應的桶里去。

對每個不是空的桶進行排序。

從不是空的桶里把排好序的數據拼接起來。

為了使桶排序更加高效，需要做到以下兩點：

在額外空間充足的情況下，儘量增大桶的數量。

使用的映射函式能夠將輸入的N個數據均勻的分配到K個桶中。

同時，對於桶中元素的排序，選擇何種比較排序算法對於性能的影響至關重要。例如，可以使用快速排序或歸併排序等算法對桶中的元素進行排序。

桶排序的變種包括計數排序和基數排序，這些變種適用於特定類型的數據，如實數或具有特定屬性的數據。計數排序適用於非負整數的排序，而基數排序適用於具有相同數字位數的整數排序。