快速排序?qū)W習(xí)：
今天我學(xué)習(xí)了快速排序，顧名思義，快速排序的速度是很快的，平均復(fù)雜度是nlogn，我也不知道是怎么算出來的，反正T(n) = 2T(n/2) + o(n) 這樣怎么怎么推到就成了nLogn了，呵呵，有空去學(xué)習(xí)一下。希望會(huì)的人可以教我，我數(shù)學(xué)太爛了。廢話少說，記錄一下快速排序的思路：
1.分治的思想，把數(shù)組分成兩份，兩份分成4分，這樣分到足夠小，就能很好排序咯，然后把他們合起來，排序完成。
2.該分治思想和合并排序思想一樣，但是處理上更搞一籌，他是把小的和大的分成兩份，這樣在最后合并的時(shí)候，就不會(huì)像合并排序那樣還要檢查，因?yàn)楸緛砭褪亲筮叡扔疫呅?，所以可以做到原地排序（就是不用申?qǐng)多余的空間）。
3.如何做好把小和大的分開時(shí)關(guān)鍵，我們做的就是以一個(gè)數(shù)位基準(zhǔn)，然后找到這個(gè)數(shù)的位置。把比他小的放在他的左邊，比他大的放在他的右邊，這樣不就分開了嘛。
4.具體怎么分時(shí)一個(gè)最關(guān)鍵的地方，本來想用圖說明一下，但是自己不會(huì)畫：作罷，試著語言整理一下，呵呵：
例如，開始把最后一個(gè)作為標(biāo)準(zhǔn)，用一個(gè)循環(huán)j = nBegin j < nEnd一一比較，這樣就能判斷到底誰比他大，誰比他小咯。
注意：為了能清楚知道區(qū)域，所以要用一個(gè)變量i來保存它的標(biāo)志，i的左邊是比他小的，i的右邊是比他大的。有了這個(gè)標(biāo)志我們就好處理了。比較就好處理咯。
遇到小的，要把他方在i的左邊，所以我們把他和i+1的元素交換，因?yàn)閕+1得元素是大于x的，交換之后i+1就小于x了，這樣我們把i也加1，不就有保證了i的左邊都比x小，右邊都比x大了嘛。呵呵。
遇到大的，不用管他。I也不用變。
比較完了，這時(shí)情況就是i的左邊都比x小，i的右邊都比x大,x在最后面。怎么處理呢？還不簡單，有重復(fù)一下i + 1與 x交換，這樣處理之后,i + 1就是保存的x值，i + 1的右邊都比x大，i+1的左邊都比x小，哈哈，i+1就是分割點(diǎn)咯。搞定。。
找出分割點(diǎn)后還不分而治之。。分而治之的時(shí)候發(fā)現(xiàn)分割點(diǎn)是排好的，只需排序nBegin - 分割點(diǎn)-1， 分割點(diǎn)+1 - nEnd 就可以咯。
最后還是截張《算法導(dǎo)論》書中的圖：
呵呵，我就是學(xué)的這本書。還不錯(cuò)啦。附上下載地址分享一下：
http://download.csdn.net/source/1199909
奉上自己的源代碼：
#include <stdio.h>
#include <stdlib.h>
//化分區(qū)間,找到最后元素的排序位置。并返回分隔的點(diǎn)（即最后一數(shù)據(jù)排序的位置）。
//劃分的區(qū)間是[nBegin, nEnd). pData是保存數(shù)據(jù)的指針
int Partition(int* pData, int nBeging, int nEnd)
{
int i = nBeging - 1; //分隔符號(hào)，最后nD保存在這里
--nEnd;
int nD = pData[nEnd]; //比較的數(shù)據(jù)。
int nTemp; // 交換用的臨時(shí)數(shù)據(jù)
//遍歷數(shù)據(jù)比較，找到nD的位置，這里注意，比較結(jié)果是,
//如果i的左邊是小于等于nD的，i的右邊是大于nD的
for (int j = nBeging; j < nEnd; ++j)
{
if (pData[j] <= nD) //如果數(shù)據(jù)比要比較的小，則在該數(shù)據(jù)的左邊，與i+1交換
{
++i; //小于nD的數(shù)據(jù)多一個(gè)，所以要加1，i的左邊數(shù)據(jù)都比nD小
nTemp = pData[i]; //交換數(shù)據(jù)
pData[i] = pData[j];
pData[j] = nTemp;
}
}
//最后不要忘了吧nD和i+1交換，因?yàn)檫@里就是nD的位置咯。
++i;
pData[nEnd] = pData[i];
pData[i] = nD;
return i; //返回nD的位置，就是分割的位置。
}
//排序的遞歸調(diào)用。
int QuickSortRecursion(int* pData, int nBeging, int nEnd)
{
if (nBeging >= nEnd -1) //如果區(qū)域不存在或只有一個(gè)數(shù)據(jù)則不遞歸排序
{
return 1;
}
//這里因?yàn)榉指畹臅r(shí)候，分割點(diǎn)處的數(shù)據(jù)就是排序中他的位置。
//也就是說他的左邊的數(shù)據(jù)都小于等于他，他右邊的數(shù)據(jù)都大于他。
//所以他不在遞歸調(diào)用的數(shù)據(jù)中。
int i = Partition(pData, nBeging, nEnd); //找到分割點(diǎn)
QuickSortRecursion(pData, nBeging, i); //遞歸左邊的排序
QuickSortRecursion(pData, i + 1, nEnd); //遞歸右邊的排序
return 1;
}
//快速排序
int QuickSort(int* pData, int nLen)
{
//遞歸調(diào)用，快速排序。
QuickSortRecursion(pData, 0, nLen);
return 1;
}
int main()
{
int nData[10] = {5,9,3,2,1,6,20,45,88,75}; //測試數(shù)據(jù)
QuickSort(nData, 10); //調(diào)用快速排序
for (int i = 0; i < 10; ++i) //輸出結(jié)果
{
printf("%d ", nData[i]);
}
printf("\n");
system("pause");
return 0;
}