對序列進行排序：[521, 630, 31, 200, 100, 6150, 210, 0, 128, 100, 19]
- 基本思想：分配、收集
- 定義：有若干個桶，將關鍵字為k的記錄放入第k個桶里次询，然后按序號將非空的連接。
- 詳細步驟：
- 創(chuàng)建十個桶瓷叫，用于存放不同的數(shù)據(jù)
- 進行n次分配收集屯吊，n為列表中最大數(shù)的位數(shù)
- 每次分配時送巡，將列表中的數(shù)據(jù)分別放入10個桶中，
- 比如第一次將521這個個位數(shù)為1的放入桶1中雌芽。630這個個位數(shù)為0的放入桶0。31這個個位為1的放入桶1辨嗽。
- 分配完成后進行收集
- 重復步驟3
def digit_total(num): # 計算一個數(shù)的位數(shù) #輔助函數(shù) total = 0 if num == 0: return 1 while num != 0: num = num // 10 total += 1 return total def get_digit_number(number, digit): # 給定數(shù)據(jù)和分位世落，獲取分位上的數(shù)字 #輔助函數(shù) if digit == 0: return 0 if number < 10 ** (digit - 1): return 0 x = 1 while digit: x = number % 10 number = number // 10 digit = digit - 1 return x def bucket_sort(array): # 主函數(shù) max_digit = digit_total(max(array)) # 計算數(shù)組中最大數(shù)的位數(shù) bucket_list = [[] for i in range(10)] # 創(chuàng)建一個裝有10個桶的列表 # 分配收集 max_digit 次 for digit in range(1, max_digit + 1): # 1分配 for item in array: index = get_digit_number(item, digit) # 獲取分位上的數(shù)字,digi=1時表示獲取個位上的數(shù)字 bucket_list[index].append(item) # 將數(shù)據(jù)項存入到下標為index的桶中 # 2收集 array = [] for bucket in bucket_list: n = len(bucket) while n: array.append(bucket.pop(0)) # 將桶中數(shù)據(jù)收集到數(shù)組中 n -= 1 return array array = [521, 630, 31, 200, 100, 6150, 210, 0, 128, 100, 19] print(bucket_sort(array)) #[0, 19, 31, 100, 100, 128, 200, 210, 521, 630, 6150]
