[經典算法] 快速排序

題目說明：

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序n 個項目要

(n log n)次比較。在最壞狀況下則需要

(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他

(n log n) 算法更快，因為它的内部循環（inner loop）可以在大部分的架構上很有效率地被實作出來。

題目解析：

快速排序使用分治法（Divide and conquer）政策來把一個串行（list）分為兩個子串行（sub-lists）。

算法步驟：

1、從數列中挑出一個元素，稱為 “基準”（pivot），

2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。

3、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。

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

僞代碼：

QUICK_SORT(A,p,r)
    if(p<r)
        then q <—— PARTITION(A,p,r)
             QUICK_SORT(A,p,q-1)
             QUICK_SORT(A,q+1,r)
 
//核心函數，對數組A[p,r]進行就地重排，将小于A[r]的數移到數組前半部分，将大于A[r]的數移到數組後半部分。
PARTITION(A,p,r)
    pivot <—— A[r]
    i <—— p-1
    for j <—— p to r-1
        do if A[j] < pivot
            i <—— i+1
            exchange A[i]<——>A[j]
    exchange A[i+1]<——>A[r]
return i+1

程式代碼：

#include <gtest/gtest.h>
#include <algorithm>
using namespace std;

template<typename T>
int Partition(T* data, int low, int high)
{
    T pivot = data[high];
    int i = low - 1;
    int tmp;
    for (int j = low; j < high; j++)
    {
        if (data[j] < pivot)
        {
            tmp = data[++i];
            data[i] = data[j];
            data[j] = tmp;
        }
    }

    tmp = data[i+1];
    data[i+1] = data[high];
    data[high] = tmp;
    return i+1;
}

template<typename T>
void QSort(T* data, int low, int high)
{
    if (low < high)
    {
        int mid = Partition(data, low, high);
        QSort(data, low, mid - 1);
        QSort(data, mid + 1, high);
    }
}

// Helper function
template<typename T>
void ShowElem(T& val)
{
    cout << val << " ";
}

template<typename T>
bool Validate(T* data, int low, int high)
{
    for (int i=low; i < high; ++i)
    {
        if (data[i] > data[i+1])
        {
            return false;
        }
    }

    return true;
}

TEST(Algo, tQSort)
{
    int d1[] = {2,8,7,1,3,5,6,4};
    QSort(d1, 0, 7);
    for_each(d1, d1+8, ShowElem<int>);    
    ASSERT_TRUE(Validate(d1,0,7));    
    cout << endl;

    int d2[] = {2};
    QSort(d2, 0, 0);
    for_each(d2, d2+1, ShowElem<int>);
    ASSERT_TRUE(Validate(d2,0,0));
    cout << endl;

    int d3[] = {2,4,5,6,7,5,2,3,5,7,10,111,2,4,5,6,3,4,5};
    QSort(d3, 0, 18);
    for_each(d3, d3+19, ShowElem<int>);
    ASSERT_TRUE(Validate(d3,0,18));
    cout << endl;    
}

運作結果:

參考引用：

http://www.cricode.com/2001.html

  [經典算法] 快速排序             
  看書、學習、寫代碼