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