桶排序（Bucket Sort）

一、基本思想

Bucket sort works by dividing an array into a finite number of buckets.Each bucket is sorted individually,The sorting of buckets may be to use another sorting algorithm or continue to use bucket sort to sort recursively.Finally, the records in each bucket are listed in turn to obtain an ordered sequence.

二、实现逻辑

Bucket sort is a divide and conquer idea,It is assumed that the set of numbers to be sorted is uniformly and independently distributed in a range,And divide this range into several ranges（桶）,然后基于某种映射函数 $fun$,将待排序列的关键字 $value$ 映射到第 $i$ 个桶中（即桶数组 $Bucket$ 的下标 $i$）,那么该关键字 $value$ 作为 $Bucket[i]$ 中的元素.每个桶 $Bucket[i]$ 都是一组大小为 $N/M$ 的序列.

将各个桶中的数据有序的合并起来,对每个桶 $Bucket[i]$ 中的所有元素进行比较排序,然后依次枚举输出 $Bucket[0]...Bucket[M]$ 中的全部内容即是一个有序序列.

为了使桶排序更加高效,First, if there is enough extra space,尽量增大桶的数量,And try to use what can be input $N$ 个数据均匀的分配到 $K$ mapping function in buckets;对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要.

算法步骤：

1. 设置一个定量的数组当作空桶;
2. 遍历序列：Place the element in the corresponding bucket;
3. Do internal sorting for each non-empty bucket;
4. Return the elements from each non-empty bucket to the original sequence in turn.

三、时间复杂度的分析

First after establishing a reasonable mapping,The algorithm needs to traverse the number of elements at a time $n$ 的数据,Store each element into the corresponding bucket,此时产生了 $\Omega (n)$、$\Theta (n)$的时间复杂度,After that, all buckets need to be traversed once,产生了 $\Omega (k)$、$\Theta (k)$的时间复杂度,The constant will be done at the end $c$ 个元素的排序,故时间复杂度为：$\Omega (n+k)$、$\Theta (n+k)$.最坏情况下,Each bucket has at most one element,所以 $k=n$,Then the time complexity is ：$O(n^2)$.

四、空间复杂度的分析

As extra opened upk = capacitybucket storage space,But the worst case is that there is at most one data per bucket,即此时 $k=n$.So the space time complexity is ：$O(n)$.

五、算法实现

Reasonable mapping

def bucket_sort(array: List[float]) -> None:
    ''' Numeric data is supported,Such as mixing integer and floating point;Data with type string is not supported. '''
    if not array:
        return None
    arrmin = min(array)
    arrmax = max(array)
    length = len(array)
    capacity = int(arrmax - arrmin + 1) // length + 1
    bucket = [[] for _ in range(capacity)] # Construct buckets
    for value in array:
        bucket[int(value - arrmin) // length].append(value)
    array.clear()
    for index in bucket:
        if index:
            for value in sorted(index): # TimSort
                array.append(value)

Optimize cardinality

def bucket_sort(array: List[float], base: int=5) -> None:
    ''' Numeric data is supported,Such as mixing integer and floating point;Data with type string is not supported. base: Adjust as needed,base 越小,The larger the number of barrels. '''
    if not array:
        return None
    assert base > 0
    arrmin = min(array)
    arrmax = max(array)
    capacity = int(arrmax - arrmin + 1) // base + 1
    bucket = [[] for _ in range(capacity)]
    for value in array:
        bucket[int(value - arrmin) // base].append(value)
    array.clear()
    for index in bucket:
        if index:
            for value in sorted(index): # TimSort
                array.append(value)