分治---快速排序

   1、未優化的快速排序 

      快速排序的基本思想是通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。

見點選打開連結

2、随機标記元素後的快速排序

   未随機化處理的快速排序最壞情況發生在劃分過程産生的兩個區域分别包含n-1個元素和1個元素的時候。由于函數Partition的計算時間為O(n),是以如果算法Partition的每一步都出現這種不對稱劃分，則T(n)=O(n^2)。

   在最好情況下，每次劃分所取的基準都恰好為中值，即每次劃分都産生兩個大小為n/2的區域。此時T(n)=O(nlogn)。

   是以，快速排序算法的性能取決于劃分的對稱性。修改Partition，可以設計出采用随機選擇政策的快速排序算法。在快速排序算法的每一步中，當數組還沒有被劃分時，可以在a[p:r]中随機選擇一個元素作為劃分基準。

#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <ctime>
using namespace std;

void Swap(int &x,int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

inline int Random(int x, int y)
{
     srand((unsigned)time(0));
     int ran_num = rand() % (y - x) + x;
     return ran_num;
}

int Partition(int r[],int s,int t)
{
    int x=r[s];//選r[s]為基準
    int i=s,j=t;
    while(i<j)
    {
        while(i<j&&r[j]>=x) j--;
        if(i<j) r[i]=r[j];
        while(i<j&&r[i]<=x) i++;
        if(i<j) r[j]=r[i];
    }
    r[i]=x;//基準放到正确位置
    for(int i=s;i<=t;i++) cout<<r[i]<<' ';
    cout<<endl;
    return i;//基準位置
}

int RandomizedPartion(int a[],int s,int t)
{
    int i=Random(s,t);
    Swap(a[i],a[s]);
    return Partition(a,s,t);
}

void RandomizedQuickSort(int r[],int first,int end)
{
    if(first<end)
    {
        int pivot=RandomizedPartion(r,first,end);
        RandomizedQuickSort(r,first,pivot-1);
        RandomizedQuickSort(r,pivot+1,end);
    }
}
int main()
{
    int input[]={49,38,65,97,76,13,27,49};
    int length=sizeof(input)/sizeof(int);
    cout<<"原數組："<<endl;
    for(int i=0;i<length;i++)
    {
        cout<<input[i]<<' ';
    }
    cout<<endl<<"排序過程："<<endl;
    RandomizedQuickSort(input,0,length-1);
    return 0;
}