在程序設計實踐上看到這個簡單的快速排序，用模板重新寫了一遍，加深一下印象。平均算法復雜度為O(nlogn)。

其中尋找支點元素pivot有多種方法，不同的方法會導致快速排序的不同性能。根據分治法平衡子問題的思想，希望支點元素可以使p[m..n]盡量平均地分為兩部分，但實際上很難做到。下面給出幾種尋找pivot的方法。

1.選擇p[m..n]的第一個元素p[m]的值作為pivot；
2.選擇p[m..n]的最后一個元素p[n]的值作為pivot；
3.選擇p[m..n]中間位置的元素p[k]的值作為pivot；
4.選擇p[m..n]的某一個隨機位置上的值p[random(n-m)+m]的值作為pivot；
　　按照第4種方法隨機選擇pivot的快速排序法又稱隨機化版本的快速排序法，在實際應用中該方法的性能也是最好的。本程序使用第4種方法。要求節點類型支持比較運算符。

template<typename T>
void quicksort(T* v, int n)
{
    if (n<=1)
        return;
    int last = 0;
    int pivot = rand()%n;
    swap(v, 0, pivot);
    for (int i = 1; i < n; i++)
    {
        if (v[i]<v[0])
            swap(v, ++last, i);
    }
    swap(v, last, 0);
    quicksort(v, last);
    quicksort(v+last+1, n-last-1);
}

template<typename T>
void swap(T* v, int i, int j)
{
    T tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;    
}

struct str
{
    str(const char* a)
    {
        assert(a);
        v = new char[strlen(a)+1];
        strcpy(v, a);
    }
    str(const str& a)
    {
        assert(a.v);
        v = new char[strlen(a.v)+1];
        strcpy(v, a.v);
    }
    ~str()
    {
        delete [] v;
    }
    void operator = (const str& a)
    {
        if (this == &a)
            return;
        assert(a.v);
        delete [] v;
        v = new char[strlen(a.v)+1];
        strcpy(v, a.v);
    }
    bool operator == (const str& a) const
    {
        return (strcmp(v, a.v)==0);
    }
    bool operator > (const str& a) const 
    {
        return (strcmp(v, a.v)>0);
    }
    bool operator < (const str& a) const
    {
        return (strcmp(v, a.v)<0);
    }
    char* v;
};


int main(int argc, char* argv[])
{
    int* array = new int [10];
    for(int i = 0; i < 10; i++)
        array[i] = rand();
    quicksort(array, 10);
    for(i = 0; i < 10; i++)
    {
        cout<<array[i]<<endl;
    }

    str s[] = {"bd", "e", "ba", "a"};
    quicksort(s, 4);
    for(i = 0; i < 4; i++)
    {
        cout<<s[i].v<<endl;
    }
    return 0;
}