演算法 - 基數排序法 (radix sort )

基數排序(Radix sort)是一種排序演算法，它是這樣實現的：
將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零. 然後, 從最低位開始, 依次進行一次排序.這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列.
基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

時間複雜度：O(n log(r)m)( r 為基數， m 為堆數 )
空間複雜度：O(n * r)

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

以下利用 C# 程式碼示範：

Queue[] qDigits;
public void sort(int[] s)
{
    int digit = 10, i;
    init(s);
    i = Convert.ToInt32(Math.Log10((s.Max() / 1.0)));

    i--; 
    while (i-- != 0)
        radix(ref digit);
}

public void init(int[] s)
{
    resetQueue();
    foreach (int i in s)
        qDigits[i % 10].Enqueue(i);
}

public void radix(ref int digit)
{
    Queue[] qTmp = qDigits;
    int digitTen = digit * 10;
    resetQueue();
    
    foreach (Queue q in qTmp)
    {
        while (q.Count != 0)
        {
            int i = Convert.ToInt32(q.Dequeue());
            qDigits[i % digitTen / digit].Enqueue(i);
        }
    }
    digit *= 10;
}

public void resetQueue()
{
    qDigits = new Queue[10];
    for (int i = 0; i < 10; i++)
        qDigits[i] = new Queue();
}

public void print()
{
    Console.Write("content: ");
    foreach (Queue q in qDigits)
    {
        while (q.Count != 0)
            Console.Write(q.Dequeue() + " ");
    }
}

回首頁