פייתון/פייתון גרסה 3/מיון בסיס

מיון בסיס (Radix Sort) היא שיטה איטרטיבית שממיינת רשימה במיון לא תוך מקומי (out-of-place) כלומר מייצרת רשימה חדשה ממוינת.

מהלך האלגוריתם

הדוגמה הבאה מתייחסת למספרים המיוצגים בבסיס 10, כך שכל ספרה קטנה מ-10. ניתן להכליל זאת בקלות לבסיס d כלשהו:

1. מיון כל המספרים לקבוצות על פי ספרת האחדות שלהם. כאשר המספרים עם ספרת האחדות הקטנה ביותר מצד שמאל.
2. מיון המספרים על פי ספרת העשרות.
3. המשך מיון המספרים על פי הספרה החשובה יותר (מאות, ואז אלפים, ואז עשרות אלפים וכן הלאה), תוך שמירת סדר המספרים בכל קבוצה לפי המיון של השלב הקודם לשלב הנוכחי.

דוגמת הרצה

נביט ברשימה הלא ממויינת הבאה:

170, 45, 75, 90, 802, 2, 24, 66

נמיין את הרשימה לפי הסיבית הכי פחות משמעותית, האחדות:

170, 90, 802, 2, 24, 45, 75, 66

כדאי לשים לב ש-802 בא לפני 2, מכיוון ש-802 הופיע לפני 2 ברשימה המקורית. אותו דבר קורה גם עבור הזוגות 170, 90 ו-45, 75.

נמיין את הרשימה לפי הסיבית הבאה, העשרות:

802, 2, 24, 45, 66, 170, 75, 90

שימו לב ששוב 802 בא לפני 2 מכיוון ש-802 בא לפני 2 ברשימה הקודמת.

לבסוף, נמיין את הרשימה לפי הסיבית המשמעותית ביותר:

2, 24, 45, 66, 75, 90, 170, 802

חשוב להבין שכל אחד מהצעדים המופיעים מעלה מצריכים רק מעבר אחד על הנתונים, מכיוון שכל פריט יכול להיות ממוקם בסל הנכון מבלי להיות מושווה עם פריטים אחרים.

קידוד

#!/usr/bin/env python
#encoding=utf-8

import math
def sort(a, radix=10):
    """a为整数列表， radix为基数"""
    K = int(math.ceil(math.log(max(a)+1, radix))) # 用K位数可表示任意整数
    for i in range(1, K+1): # K次循环
        bucket = [[] for i in range(radix)] # 不能用 [[]]*radix，否则相当于开了radix个完全相同的list对象
        for val in a:
            bucket[val%(radix**i)//(radix**(i-1))].append(val) # 獲得整數第K位數字 （從低到高）
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并