十大经典排序算法6（Python版本）

旧城等待， 2022-12-15 11:07 165阅读 0赞

### 文章目录 ###

*   *   *  九、桶排序
         *  十、基数排序

### 九、桶排序 ###

**1、桶排序介绍**  
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量

使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

**2、桶排序最快与最慢**

*  最快的时候：当输入的数据可以均匀的分配到每一个桶中。
 *  最慢的时候：当输入的数据被分配到了同一个桶中。

**3、Python练习**

def bucket_sort(s):
        """桶排序"""
        min_num = min(s)
        max_num = max(s)
        # 桶的大小
        bucket_range = (max_num-min_num) / len(s)
        # 桶数组
        count_list = [ [] for i in range(len(s) + 1)]
        # 向桶数组填数
        for i in s:
            count_list[int((i-min_num)//bucket_range)].append(i)
        s.clear()
        # 回填，这里桶内部排序直接调用了sorted
        for i in count_list:
            for j in sorted(i):
                s.append(j)
    
    if __name__ == __main__ :
        a = [3.2,6,8,4,2,6,7,3]
        bucket_sort(a)
        print(a) # [2, 3, 3.2, 4, 6, 6, 7, 8]

### 十、基数排序 ###

**1、基数介绍**  
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

**2、基数排序、计数排序和桶排序的差异**  
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

*  基数排序：根据键值的每位数字来分配桶；
 *  计数排序：每个桶只存储单一键值；
 *  桶排序：每个桶存储一定范围的数值；

**3、动图演示**  
![01][]

**4、Python练习**

def RadixSort(list):
        i = 0                                    #初始为个位排序
        n = 1                                     #最小的位数置为1（包含0）
        max_num = max(list) #得到带排序数组中最大数
        while max_num > 10**n: #得到最大数是几位数
            n += 1
        while i < n:
            bucket = { } #用字典构建桶
            for x in range(10):
                bucket.setdefault(x, []) #将每个桶置空
            for x in list: #对每一位进行排序
                radix =int((x / (10**i)) % 10) #得到每位的基数
                bucket[radix].append(x) #将对应的数组元素加入到相 #应位基数的桶中
            j = 0
            for k in range(10):
                if len(bucket[k]) != 0: #若桶不为空
                    for y in bucket[k]: #将该桶中每个元素
                        list[j] = y #放回到数组中
                        j += 1
            i += 1
    return  list

文章转载于：  
[十大经典排序算法（Python）][Python]

[01]: /images/20221123/89dfa27bdf8343cbb9a279edbb49c1dc.png
[Python]: https://mp.weixin.qq.com/s?__biz=MzI0MzU2NzQ1OA==&mid=2247489169&idx=1&sn=5d4c64225010e4b6e333cf962412d239&chksm=e96a489cde1dc18a092840dd40e45251c705a8bddbcb1fbdf6791c754de75cc2ace439587180&mpshare=1&scene=23&srcid=09221Zfx2rypvHYFTttont6W&sharer_sharetime=1600761961411&sharer_shareid=b2a2e30106bb801eb92a67be762689dd#rd