基于快排的partition實作TOPK問題

類似于快速排序，首先選擇一個劃分元，如果這個劃分元的序号index剛好等于k，那麼這個劃分元以及左邊的數，剛好組成了top-k small data;如果index>k, 那top-k small data在index的左邊，那麼就繼續遞歸從index-1和數中選取top-k.如果index < k,那麼說明還要從index的右邊，選取top-(k-index) small data.

1. public class TopK_Quick {
2. public static int Partition(int a[],int low,int high)
3. {
4. a[0]=a[low];
5. int pivokey = a[low];
6. while(low<high)
7. {
8. while(low<high && a[high]>=pivokey) --high;
9. a[low] = a[high];
10. while(low<high && a[low]<=pivokey) ++low;
11. a[high]= a[low];
12. }
13. a[low]=a[0];
14. return low;
15. }
16. public static void display(int a[],int k)
17. {
18. for(int i=1;i<=k;i++)
19. {
20. System.out.print(a[i]+" ");
21. }
22. }
23. public static int selectK(int a[],int start,int end,int k)
24. {
25. int index = 0;
26. if(start<end)
27. {
28. index = Partition(a,start,end);
29. if(index == k)//正好找到第k大的數
30. {
31. index = k;
32. }else if(index < k)//還要從index的右邊找k-index個數
33. {
34. index = selectK(a,index+1,end,k-index);
35. }else if(index > k)//k個數都在Index的左邊
36. {
37. index = selectK(a,start,index-1,k);
38. }
39. }
40. return index;
41. }
42. public static void main(String args[])
43. {
44. int k=0;
45. int a[]={0,49,38,29,65,97,76,13,27,49,22,19};
46. if(k>0&&k<=a.length-1)
47. {
48. selectK(a,1,a.length-1,k);
49. display(a,k);
50. }else{
51. System.out.println("Are You Kidding Me?");
52. }
53. }
54. }