排序算法-桶排序-蒲公英云

排序算法-桶排序

一、桶排序

它同样是一种线性时间的排序算法，它类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。

每一个桶（bucket）代表一个区间范围，里面可以承载一个或多个元素。

如果有一个非整数数列如: 4.5，0.84，3.25，2.18，0.5

第1步，创建这些桶，并确定每一个桶的区间范围。

需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外，前面各个桶的区间按照比例来确定。

区间跨度=(最大值-最小值)/（桶的数量-1)

第2步，遍历原始数列，把元素对号入座放入各个桶中。

第3步，对每个桶内部的元素分别进行排序（只有第1个桶需要排序)。

第4步，遍历所有的桶，输出所有元素。

def bucketSort(ll):
    # 1.得到数列的最大值,最小值
    max = ll[0]
    min = ll[0]
    for i in range(1, len(ll)):
        if ll[i] > max:
            max = ll[i]
        if ll[i] < min:
            min = ll[i]
    # 差值
    diff = max - min
    # print(diff)
    # 2.初始化桶
    bucket = []
    for i in range(len(ll)):
        bucket.append([]) #添加每个列表
    print(bucket)
    #3.遍历原数列，将每个元素放入桶中
    for i in range(len(ll)):
        #桶的索引
        num=int((ll[i]-min)*(len(ll)-1)/diff)
        #每个桶数列
        bt=bucket[num]
        # 将数据放入桶
        bt.append(ll[i])
        print(num,bt)
    #4.每个桶内部排序
    for i in range(len(bucket)):
        bucket[i].sort()
    print(bucket)
    #5.排序
    sort_list=[]
    #循环输出排序的元素
    for i in bucket:
        for j in i:
            sort_list.append(j)
    return sort_list
if __name__ == '__main__':
    ll=[4.5,0.84,3.25,2.18,0.5]
    print(ll)
    print(bucketSort(ll))

假设原始数列有n个元素，分成n个桶。

下面逐步来分析一下算法复杂度。

第1步，求数列最大值、最小值，运算量为n。

第2步，创建空桶，运算量为n。

第3步，把原始数列的元素分配到各个桶中，运算量为n。

第4步，在每个桶内部做排序，在元素分布相对均匀的情况下，所有桶的运算量之和为n。

第5步，输出排序数列，运算量为n。

因此，桶排序的总体时间复杂度为O (n)。至于空间复杂度同样是O（n)。