上篇文章我們學(xué)習(xí)了算法入門——歸并排序集侯、希爾排序被啼，這篇文章我們學(xué)習(xí)算法入門——計數(shù)排序、桶排序棠枉、基數(shù)排序浓体。

計數(shù)排序

計數(shù)排序是已知列表元素的范圍，統(tǒng)計列表元素出現(xiàn)的頻次辈讶，再進行排序命浴，例如：

li=[2,5,2,7,7,7,8]

在上面的列表中，元素2出現(xiàn)了兩次贱除，5出現(xiàn)了一次生闲，7出現(xiàn)了三次，8出現(xiàn)了一次月幌，再通過元素出現(xiàn)的次數(shù)來輸出列表碍讯，示例代碼如下：

def count_sort(li,max_count):
    print('排序前：',li)
    count=[0 for _ in range(max_count+1)]       # 長度為max_count，值全為0的列表
    for val in li:                              # 遍歷列表的值
        count[val]+=1                           # 計數(shù)
    li.clear()                                  # 清空列表
    print('統(tǒng)計列表元素出現(xiàn)的次數(shù)',count)           # 輸出count列表
    for index,val in enumerate(count):          # 遍歷列表的
        for i in range(val):                    # 根據(jù)count列表的值來遍歷幾次
            li.append(index)                    # 添加元素

li=[3,5,2,5,1,1,6,10,9,8]
count_sort(li,10)
print('排序后',li)

運行結(jié)果如下圖所示：

因為列表的下標是從0開始的扯躺，所以統(tǒng)計列表元素出現(xiàn)的次數(shù)為0出現(xiàn)了0次捉兴，1出現(xiàn)了2次蝎困，2出現(xiàn)了一次，3出現(xiàn)了1次等等倍啥。

計數(shù)排序的缺點：

• 消耗大量內(nèi)存禾乘；
• 需要知道要排序的列表最大值；

桶排序

桶排序算是計數(shù)排序的升級版逗栽，桶排序首先把元素分在不同的桶中盖袭，再對每個桶中元素排序。如下圖所示：

其實每個桶表示一個空列表彼宠，示例代碼如下：

def bucket_sort(li, n=4, max_num=40):
    buckets = [[] for _ in range(n)]           # 創(chuàng)建桶
    for var in li:
        i = min(var // (max_num // n), n - 1)  # i 表示元素放在哪個桶
        buckets[i].append(var)                 # 把元素放在桶里
        # 桶內(nèi)排序
        for j in range(len(buckets[i]) - 1, 0, -1):     # 從桶的后面往前面比較元素大小
            if buckets[i][j] < buckets[i][j - 1]:
                buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
            else:
                break
    sorted_li = []                          
    for buc in buckets:             
        sorted_li.extend(buc)                   # 合并桶
    return sorted_li

li=[35,22,12,19,20,5,10,15]
print(bucket_sort(li))

運行結(jié)果如下：

基數(shù)排序

基數(shù)排序是根據(jù)元素位數(shù)進行排序鳄虱，例如，先按照元素的個位數(shù)來排序凭峡，按照元素的十位數(shù)來排序拙已，再按照百位、千位等等摧冀。如下圖所示：

示例代碼如下：

def radix_sort(li):
    max_num = max(li)  # 獲取列表最大值
    it = 0
    # 根據(jù)最大值來判斷進行元素的個位倍踪、百位、千位索昂、萬位來排序
    while 10 ** it <= max_num:
        buckets=[[] for _ in range(10)]     # 創(chuàng)建空列表
        for var in li:
            digit=(var//10**it)%10
            buckets[digit].append(var)      # 插入空列表中
        li.clear()
        for buc in buckets:
            li.extend(buc)          # 合并
        it += 1
        print(li)
li=[22,54,28,32,14,33,56,12]
radix_sort(li)

運行結(jié)果如下：

好了建车，關(guān)于算法入門——計數(shù)排、桶排序椒惨、基數(shù)排序就學(xué)到這里了缤至，下篇文章學(xué)習(xí)算法入門的其他知識。

公眾號：白巧克力LIN

該公眾號發(fā)布Python康谆、數(shù)據(jù)庫领斥、Linux、Flask沃暗、自動化測試月洛、Git、算法等相關(guān)文章孽锥！