桶排序

桶排序

桶排序（Bucket sort）或所谓的箱排序，是一种类似于计数排序所创建的统计数组的线性时间排序算法。桶排序需要创建若干个桶来协助排序。 原理：将数组分到有限个数量的桶子里。每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间$O(n)$。但桶排序不是比较排序，它不受$O(nlogn)$下限的影响。 桶排序中的每一个桶实际上代表着一个区间范围，里面可以承载一个或多个元素。假设有一个非整数数列如下：[4.5,0.5,3.5,2.2,0.8]，下面来看下具体的实现：

创建桶，并确定每一个桶的区间范围；具体需要建立多少个桶，如何确定桶区间范围，有多种方式可以实现，这里创建的桶数量等于原始数列的元素，除了最后一个桶只包含数列最大值外，前面的各个桶区间都按照比例来确定 $区间范围=（最大值-最小值）/（桶数量-1）$遍历原始数列，把元素对号入座放入各个桶中。对每个桶内部的元素分别进行排序遍历所有桶，输出所有元素

代码实现

def BucketSort(arr): #得到最大值，最小值以及最大值最小值的差值 max_num = max(arr) min_num = min(arr) D_value = max_num - min_num #初始化桶 bucketNum = len(arr) - 1 #数列长度即为桶的数量 bucketSize = ((max_num - min_num) // bucketNum) #根据桶的数量找到每个桶的取值范围 buckets = [[] for i in range(bucketNum)] #创建bucketNum个桶 # 将原数组的元素放入每个桶中 for i in range(len(arr)): bucket_index = int((arr[i] - min_num) * bucketNum // D_value) buckets[bucket_index].append(arr[i]) result = [] #桶中元素排序 for unsorted_bucket in buckets: #插入排序 sorted_bucket = insert_sort(unsorted_bucket) result += sorted_bucket return result #插入排序 def insert_sort(arr): length = len(arr) #第一个元素默认已经排好序 for i in range(1,length): #如果前一个元素大于当前元素，交换位置 while i > 0 and arr[i-1] > arr[i]: arr[i-1],arr[i] = arr[i],arr[i-1] i -= 1 return arr if __name__ == "__main__": arr = [3,4,1.2,5.6,9,2.8,7] result = BucketSort(arr) print(result)

复杂度分析

时间复杂度：$O(n)$，第一步，求数列最大、最小值，运算量为$n$；第二步，创建空桶，运算量为$n$；第三步，把原始数列的元素分配到各个桶中，运算量为$n$；第四步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为$n$，第五步，输出排序好的数列，运算量为$n$。因此，桶排序的总体时间复杂度为$O(n)$。空间复杂度：$O(n)$。

注意：桶排序适用于数据元素分布比较均匀的情况，如果元素分布极不均匀，会导致绝大多数元素都分在了一个桶里，其余的桶就白白创建了。这种情况下，时间复杂度在一定程度上是会增加的。这也验证了一点，没有绝对好的算法，当然也没有绝对不好的算法，关键是要看具体的使用场景。