演算法 - 基數排序法 (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() + " ");
    }
}

回首頁

演算法 - 堆積排序法 (heap sort )

堆積排序（Heapsort）是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法。堆積樹是一個近似完全二元樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

時間複雜度：O(n logn)
空間複雜度：O(1)

通常堆積樹(heap)是通過一維陣列來實現的。在起始陣列為 0 的情形中：

堆積樹的根節點（即堆積樹的最大值）存放在陣列位置 1 的地方;

　　注意：不使用位置 0，否則左子樹永遠為 0[2]

父節點i的左子節點在位置 (2*i);
父節點i的右子節點在位置 (2*i+1);
子節點i的父節點在位置 floor(i/2);

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

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

class Heap
{
    public int[] s;
    public int size;

    public Heap(int n, int[] s)
    {
        this.s = new int[n];
        for (int i = 0; i < n; i++)
            this.s[i] = s[i];
    }
}

class HeapSort
{
    public Heap h;

    public HeapSort(int n, int[] s)
    {
        h = new Heap(n, s);
    }

    public void sort(int n)
    {
        makeheap(n, h);
        removeKeys(n, h, h.s);
    }

    void siftdown(Heap tp, int i)
    {
        int parentIndex, lChildIndex, key;
        bool bFound;

        key = tp.s[i];
        parentIndex = i;

        bFound = false;
        
        while (leftNode(parentIndex) <= tp.size && !bFound)
        {
            if (leftNode(parentIndex) < tp.size &&
                tp.s[leftNode(parentIndex)] < tp.s[rightNode(parentIndex)])
                lChildIndex = rightNode(parentIndex);
            else
                lChildIndex = leftNode(parentIndex);

            if (key < tp.s[lChildIndex])
            {
                tp.s[parentIndex] = tp.s[lChildIndex];
                parentIndex = lChildIndex;
            }
            else
                bFound = true;
        }
        tp.s[parentIndex] = key;
    }

    int root(Heap tp)
    {
        int keyout;
        keyout = tp.s[0];
        tp.s[0] = tp.s[tp.size];
        tp.size = tp.size - 1;
        siftdown(tp ,0);
        return keyout;
    }

    void removeKeys(int n, Heap tp, int[] s)
    {
        int i;
        for (i = n - 1; i >= 0; i--)
            s[i] = root(tp);
    }

    void makeheap(int n, Heap tp)
    {
        int i;
        tp.size = (n - 1);
        for (i = (n - 1) / 2; i >= 0; i--)
            siftdown(tp, i);
    }

    int parentNode(int i)
    {
        return Convert.ToInt32(Math.Floor((i - 1) / 2.0));
    }

    int leftNode(int i)
    {
        return (2 * i + 1);
    }

    int rightNode(int i)
    {
        return (2 * i + 2);
    }
}

回首頁

演算法 - 快速排序法 (quick sort )

快速排序是一種排序演算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n2)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。

時間複雜度：最佳 - O(n logn)、最差 - O(n²)
空間複雜度：O(n logn)

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：

1.從數列中挑出一個元素，稱為 "基準"（pivot），
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
3.遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

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

public void sort(int l, int h, int[] s)
{
    int pivotIndex = 0;

    if (h > l)
    {
        quick(l, h, ref pivotIndex, s);
        sort(l, pivotIndex, s);
        sort(pivotIndex + 1, h, s);
    }
}

void quick(int l, int h, ref int pivotIndex, int[] s)
{
    int i, j, pivotItem;

    pivotItem = s[l];
    j = l;
    for (i = l + 1; i < h; i++)
    {
        if (s[i] < pivotItem)
        {
            j++;
            swap(ref s[i], ref s[j]);
        }
    }
    pivotIndex = j;
    swap(ref s[l], ref s[pivotIndex]);
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}

回首頁