基數排序是按照低位先排序，然后收集; 再按照高位排序，然后再收集; 依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。基數排序基于分別排序， 分別收集，所以是穩定的。

?

?

?

?

?

import randomclass phone_num(object):num = ""def __init__(self, num=""):self.num = numdef get_bit(self, bit):return int(self.num[bit-1:bit])def __str__(self):return self.numdef __repr__(self):return self.numdef radix_sort(data_list):radix = 11for i in range(radix, 0, -1):counting_sort(data_list, i)def counting_sort(data_list, radix):length = len(data_list)# 定義桶bucket = []max = data_list[0].get_bit(radix)for i in range(length):if data_list[i].get_bit(radix) > max:max = data_list[i].get_bit(radix)# 初始化for i in range(max + 1):bucket.append(0)# 計數for i in range(length):bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] + 1# 累加for i in range(1, max+1):bucket[i] = bucket[i] + bucket[i-1]# 計數排序，定義結果數組并初始化result = [0 for _ in range(length)]# 從尾到頭查找分數在result的插入位置，如果從頭到尾的話就不是穩定的排序算法for i in range(length - 1, -1, -1):result[bucket[data_list[i].get_bit(radix)] - 1] = data_list[i]bucket[data_list[i].get_bit(radix)] = bucket[data_list[i].get_bit(radix)] - 1# 將結果復制到原來的數組中，達到修改數組的效果for i in range(length):data_list[i] = result[i]def create_phone_num():prelist = ["130", "131", "132", "133", "134", "135", "136", "137", "138","153", "155", "156", "157", "158", "159", "186", "187", "188"]randomPre = random.choice(prelist)Number = "".join(random.choice("0123456789") for i in range(8))phoneNum = randomPre + Numberreturn phoneNumif __name__ == "__main__":data_list = [phone_num(create_phone_num()) for _ in range(10)]print('排序前')for i in data_list:print(i)radix_sort(data_list)print("排序后")for i in data_list:print(i)排序前 13102509815 15639884219 13736715037 15658464512 13335663937 15944723954 13498377631 13570582918 15640689458 15949340088 排序后 13102509815 13335663937 13498377631 13570582918 13736715037 15639884219 15640689458 15658464512 15944723954 15949340088Process finished with exit code 0

基數排序的適用場景

基數排序對要排序的數據是有要求的，需要可以分割出獨立的“位”來比較，而且位之間有遞進的關系，如果 a 數據的高位比 b 數據大，那剩下的低位就不用比較了。除此之外，每一位 的數據范圍不能太大，要可以用線性排序算法來排序，否則，基數排序的時間復雜度就無法做 到 O(n) 了。
在實際應用中，字符串之間排序就可以使用基數排序，如果待排序的字符串位數不一致，可以通過在字符串尾部補 0 來使他們位數一致，這與小數轉整數后再排序的道理是一致的。

總結

以上是生活随笔為你收集整理的排序算法-基数排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。