/************************************************************************/ /***************** Author:Qian Guo Zheng ****************************/ /***************** Time: 2011.4.14 ****************************/ /************************************************************************/ #include <stdio.h> #include <stdlib.h> typedef int type; //realize the function as template type a[10]={5,2,7,9,8,5,87,6,4,1}; void interchange(type &a,type &b) //change the two number { a=a+b; b=a-b; a=a-b; } int partition(int m,int p) //quick part the number according to the a[m] { int i=m; //int pp=p-1; type v=a[m]; //p=p-1; while(1) { while(a[i]<=v) i=i+1; //while a[i] is less than v ,then i++ while(a[p]>=v) p=p-1; //while a[p] is more than v ,then p--; if (i<p) //if i is less than p means: i is in the left of the p , //then change value,else break the repeat! { interchange(a[i],a[p]); }else { break; } } a[m]=a[p]; //move a[m] to a[p] ,so before a[m] all the value is less than the a[m] a[p]=v; //while others are more than a[m]; return p; /*for(i=0;i<=9;i++) //here is used to test the error in programming! { printf("%d ",a[i]); } printf("/n");*/ } int select_the_k(type a[],int n,int k) { int l,r,j; l=0; r=n; while(1) { j=r; j=partition(l,j); //continue to partition if (k==j) return a[j]; //return the j th min number else if(k<j) r=j; else l=j+1; } } int main(int argc,char *argv[]) { int i=0,k=0; k=select_the_k(a,9,6); //int temp=8; //interchange(temp,k); //printf("%d ,%d ",temp,k); printf("the num 6th small is :%d/n",k); for(i=0;i<=9;i++) { printf("%d ",a[i]); } printf("/n"); return 0; }
