參考這里，提到兩種方法，并說第二種好：

http://www.cnblogs.com/qsort/archive/2011/05/09/2041653.html

?

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

開始時，ptrLeft，ptrRight分別指向數組兩端；

*ptrLeft小于pivot時，向右走；*ptrRight大于pivot時，向左走；

ptrLeft和ptrRight都走不動的時候，交換對應的元素，繼續。

ptrLeft和ptrRight相遇的時候，結束這一趟，然后二分的對兩邊繼續qsort。

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

partition的時候，思路是：

1，將pivot放到序列末尾；

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

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

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

?

查找第k小的數，可以利用qsort中的partition來一次去掉大概一半。

思想如下：Find(k, Left, Right)的時候，先選擇一個pivot，來Partition(Pivot, Left, Right)

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

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

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

?

總結

以上是生活随笔為你收集整理的快速排序、查第k大的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。