改进以后的伪代码实现

(darktemple)

　　我用伪代码实现了以上的算法题，首先使用递归来实现quicksort：

void main()
{
　　//已知extern real array[n]和extern int k
　　real knumber=foundk(array[],0,n-1);
　　//array[]数组下标从0开始，总共n个
　　print(knumber);
}//main()

real foundk(int a[],int head,int length1)
{
　　int tail=head+length1-1;
　　real pivot=a[head];

　　int i=head;
　　int j=tail;

　　while(true){
　　　do{
　　　　　i++;
　　　}while(a[i]<pivot);

　　　do{
　　　　j++;
　　　}while(a[j]>pivot);

　　　if (i>=j) break;//仅仅退出while循环

　　　swap(a[i],a[j])
　　}//while

　　a[head]=a[j];
　　//若标准快速排序需a[j]=pivot，这里只找第k大的;
　　if (k=j-head+1)
　　return pivot;
　　　　else if (k<j-head+1)
　　　　　　return foundk(a[],head,j-head);
　　　　　　else return foundk(a[],j+1,tail-j);
}//foundk()

　　递归方法会带来很多缺点，对于本题这种特殊的情况而言，用迭代的方式实现quicksort算法不仅效率更高，还可以使代码思路更加清晰，容易阅读：

void main()
{
　　//已知extern real array[n]和extern int k
　　boolean nofound=true;
　　real knumber;
　　int i=0;
　　int j=n-1;

　　while nofound{
　　　　int head=i;
　　　　int tail=j;
　　　　while(true){
　　　　　　do{
　　　　　　　　i++;
　　　　　　　}while(a[i]<pivot);

　　　　　　do{
　　　　　　　　j++;
　　　　　　　}while(a[j]>pivot);

　　　　　　if (i>=j) break;//仅仅退出while循环

　　　　　　swap(a[i],a[j])
　　　　}//里头的while

　　　　a[head]=a[j];
　　　　//若标准快速排序需a[j]=pivot，这里只找第k大的;

　　　　if (k-1=j){
　　　　　　knumber=pivot;
　　　　　　nofound=false;
　　　　};
　　　　　　else if (k-1<j){
　　　　　　　　i=head;
　　　　　　　　j=j-1;
　　　　　　};
　　　　　　else{
　　　　　　　　i=j+1;
　　　　　　　　j=tail;
　　　　　　};
　　}//外头的while
　　print(knumber);
}//main()

　　其实这个问题并不特别复杂，但真要实践起来，还是投入了不少精力。以上仅仅是伪代码实现，并没有经过上机检验，错误难以避免。希望大家给于指导，我们多交流，共同进步。

Index

一道算法题(Mar. 17, 2003, by joyfire ddcat)
-->改进以后的伪代码实现(Mar. 24, 2003, by darktemple)