雖然簡(jiǎn)易二字，因人而異。不過(guò)，寫一個(gè)快排確實(shí)并不需要過(guò)20行，超過(guò)幾分鐘時(shí)間的代碼。面試的時(shí)候，面試官確實(shí)會(huì)經(jīng)常問(wèn)起快排什么的。但是，大家上的入門課基本是使用嚴(yán)蔚敏老奶奶的教材，上面對(duì)于快排的講解我是不敢恭維的。至少上面關(guān)于快排的寫法，我是寫過(guò)好幾次之后都是沒(méi)掌握好的。后面，應(yīng)該是看K&R的c語(yǔ)言程序設(shè)計(jì)時(shí)候，發(fā)現(xiàn)一種更簡(jiǎn)便的partion方法，但是當(dāng)時(shí)我也沒(méi)怎么掌握。這一切直到，寒假認(rèn)真閱讀算法導(dǎo)論的時(shí)候。
不用算法牛人，算法學(xué)得好或者對(duì)快排理解深刻的，不用把這篇文章看完了，相信你們都能在10分鐘之內(nèi)寫一個(gè)正確的快排了。
廢話少說(shuō)，還是來(lái)講講如何保證10分鐘之內(nèi)寫一個(gè)正確的快排，而且以后都能10分鐘之內(nèi)寫出來(lái)，而不是此刻看了我說(shuō)的這些胡言之后。
快排的主函數(shù)大家都會(huì)，現(xiàn)在我給個(gè)簡(jiǎn)易點(diǎn)的樣子：
void QuickSort(int* pnA, int nLen)
{
if (nLen > 1)
{
int nP = Partion(pnA, nLen);
QuickSort(pnA, nP);//排序第nP+1個(gè)元素前面的nP個(gè)元素
QuickSort(pnA + nP + 1, nLen - nP - 1);//排序第nP+1個(gè)元素后面的元素
}
}
那么現(xiàn)在就剩下Partion函數(shù)了。
我記得嚴(yán)蔚敏書上的寫法中Partion 函數(shù)里面是有幾個(gè)循環(huán)的。而且即使大概寫出來(lái)了，也很難處理正確邊界。
現(xiàn)在，我要說(shuō)的就是算法導(dǎo)論上，作為教材內(nèi)容出現(xiàn)的Partion函數(shù)。還是看代碼吧。
int Partion(int* pnA, int nLen)
{
//這里選擇最后一個(gè)元素作為軸元素
int i, j;
for (i = j = 0; i < nLen - 1; ++i)
{
if (pnA[i] < pnA[nLen - 1])
{
swap(pnA[i], pnA[j];//交換2個(gè)數(shù)的函數(shù)，大家都能寫吧，stl中也有
++j;
}
}
swap(pnA[j], pnA[nLen - 1]);
return j;
}
為了公平起見(jiàn)，上面的代碼我都是在blog上面直接敲的，寫這10多行代碼是絕對(duì)用不了10分鐘的。主遞歸函數(shù)大家都會(huì)寫，Partion函數(shù)里面只有一個(gè)for循環(huán)，所以只要明確了for循環(huán)的意思，快排的速寫就迎刃而解了。其實(shí)，按照算導(dǎo)的說(shuō)法，
這個(gè)for一直在劃分區(qū)間。區(qū)間[0,j-1]是小于最后一個(gè)元素的區(qū)間，[j,nLen - 2]是大于等于最后一個(gè)元素的區(qū)間，所以最后將第nLen-1個(gè)元素與第j個(gè)元素交換即可，Partion應(yīng)該返回的值也應(yīng)該是j。
我不知道大家理解上面那句黑體字的話沒(méi)，如果理解了，隨便寫個(gè)快排是沒(méi)問(wèn)題了。至少，可能的下次面試時(shí)候，可以瀟灑地寫個(gè)快排給面試官看看了，雖然這也許并不是什么值得慶幸的事情。
算法導(dǎo)論里面的快速排序那章后面還有思考題，其中第一個(gè)思考題，提出的另外一種叫做Hoare劃分的partion寫法，意思就和嚴(yán)蔚敏書上的partion函數(shù)一致的。理解的關(guān)鍵是，
軸元素一直處于被交換中。只要發(fā)現(xiàn)了這點(diǎn)，寫一兩次后，這種partion方法也能掌握好了，不過(guò)寫起來(lái)是循環(huán)嵌循環(huán)了，沒(méi)那么舒服。