快速算法實現----挖坑填數

快速排序作為時間復雜度為o(nlogn)的算法，在實際中經常用到。下面簡單的講解一下快速排序算法的實現思路。

看看 http://www.linuxidc.com/Linux/2014-09/107317.htm 思路寫的非常好。挖坑填數，非常形象。下面簡單的介紹一下。

快速排序用到時分治法的思想。主要可以分為以下的三步。

1、選定一個數作為基數

2、將大於這個的基數的數全放在右邊，小於這個基數的數全部放在左邊

3、對左右區間中的數重復1、2步驟，直到區間中只有一個數。

這樣描述可能有一點難以理解，我們可以用挖坑+填數的方式來很好的理解

1、對於數組a，實現l到r的排序，首先挖坑key=a[l]，令i=l，j=r，此時形成第一個坑a[i]

2、j--直到a[j]小於key的地方，令a[i]=a[j]，此時a[j]形成一個新的坑，i++

3、i++直到a[i]大於key的地方，令a[j]=a[i]，填上坑a[j],此時a[i]形成新的坑，j--

4、再重復執行2，3二步，直到i==j，將key填入a[i]中

進經過上面的一番講解，突然一下子變得清晰明了了。

代碼實現就很簡單了。

//一次劃分
int partion(int a[],int left,int right)
{
//先將第一個數設置成一個坑a[left]
int i=left，j=right;
int key=a[left];
while(i<j)
{
//從最右端開始尋找小於key的數，如果大於，則j--
while(i<j&&a[j]>=key)
j--;
//如找到且i<j,將a[i]這個坑填上，形成一個新坑a[j]，i++
if(i<j)
{
a[i]=a[j];
i++;
}
//從左邊的i開始找，如果小於key，i++
while(i<j&&a[i]<key)
i++;
//如找到，並且i<j，將a[j]這個坑填上，形成新坑a[i],j--
if(i<j)
{
a[j]=a[i];
j--;
}
}
//將key填回坑a[i]
a[i]=key;
//返回軸值
return i;

}

void QuickSort(int a[],int left,int right)
{
//當left<right時
if(left<right)
{
//形成軸值
int mid=partion(a,left,right);
//遞歸左半部分
QuickSort(a,left,mid-1);
//遞歸右半部分
QuickSort(a,mid+1,right);
}
}

int main()
{

int a[]={1,3,2,5,2,4};
QuickSort(a,0,5);
for(int i=0;i<6;i++)
{
cout<<a[i]<<" ";
}
return 0;
}