首页 > 代码库 > 快速排序、查第k大

快速排序、查第k大

参考这里,提到两种方法,并说第二种好:

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大