在程序設(shè)計(jì)實(shí)踐上看到這個(gè)簡(jiǎn)單的快速排序，用模板重新寫(xiě)了一遍，加深一下印象。平均算法復(fù)雜度為O(nlogn)。

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

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

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;
}