qsort的每一趟中，選定pivot以后，partition的過(guò)程如下：

開始時(shí)，ptrLeft，ptrRight分別指向數(shù)組兩端；

*ptrLeft小于pivot時(shí)，向右走；*ptrRight大于pivot時(shí)，向左走；

ptrLeft和ptrRight都走不動(dòng)的時(shí)候，交換對(duì)應(yīng)的元素，繼續(xù)。

ptrLeft和ptrRight相遇的時(shí)候，結(jié)束這一趟，然后二分的對(duì)兩邊繼續(xù)qsort。

更新：這樣的做法需要處理各種特殊情況（略），因此更好的思路是：

partition 的時(shí)候，思路是：

1 ，將 pivot 放到序列末尾；

2 ，兩個(gè)指針 ptr_old_curr 、 ptr_new_curr 從左向右掃描，如果 *ptr_old_curr <= pivot ，就交換到 ptr_new_curr 位置；換言之， ptr_new_curr 一直指向下一個(gè)位置；

3 ， ptr_old_curr 到達(dá)末尾后， ptr_new_curr 指向第一個(gè)大于 pivot 的位置，將 pivot 放回這個(gè)位置即可。

這樣的好處是：完全不需要判斷各種異常情況。 一個(gè)實(shí)現(xiàn)參見(jiàn) http://www.cnblogs.com/qsort/archive/2011/08/30/2155923.html

?

查找第k小的數(shù)，可以利用qsort中的partition來(lái)一次去掉大概一半。

思想如下：Find(k, Left, Right)的時(shí)候，先選擇一個(gè)pivot，來(lái)Partition(Pivot, Left, Right)

之后，設(shè)Pivot所在位置為Middle，可知Pivot左側(cè)都比Pivot小，右側(cè)都比Pivot大。

如果左側(cè)有大于k個(gè)數(shù)，那么第k小的數(shù)肯定在左側(cè)，可以繼續(xù)Find(k, Left, Middle)

如果左側(cè)數(shù)字小于k個(gè)，那么第k小的數(shù)肯定在右側(cè)，而且是右側(cè)的第 (k - (Middle - Left + 1) )個(gè)數(shù)，可以繼續(xù)Find([k - (Middle - Left + 1)], Middle, Right)了。