HDOJ 1280查找前k大的數字

Problem Description 還記得Gardon給小希布置的那個作業麼？（上次比賽的1005）其實小希已經找回了原來的那張數表，現在她想确認一下她的答案是否正确，但是整個的答案是很龐大的表，小希隻想讓你把答案中最大的M個數告訴她就可以了。 

給定一個包含N(N<=3000)個正整數的序列，每個數不超過5000，對它們兩兩相加得到的N*(N-1)/2個和，求出其中前M大的數(M<=1000)并按從大到小的順序排列。  

Input 輸入可能包含多組資料，其中每組資料包括兩行： 

第一行兩個數N和M， 

第二行N個數，表示該序列。

Output 對于輸入的每組資料，輸出M個數，表示結果。輸出應當按照從大到小的順序排列。  

Sample Input

4 4
1 2 3 4
           

Sample Output

7 6 5 5
           

這就是題目，開始我利用快速排序找第K大的元素，然後将前面的元素再快速排序，以為這樣會快。。。感覺直接排序會慢很多。。。代碼是：

import java.util.Arrays;
import java.util.Scanner;

public class HDOJ1280 {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		
		
		while(scan.hasNext()){
			int n = scan.nextInt();
			int k = scan.nextInt();
			int a[] = new int [n+1];
			int b[] = new int [k+1];
			int x = n*(n-1)/2;
			int c [] = new int [x+1];
			for(int i = 1;i<=n;i++){
				a[i] = scan.nextInt();
			}
			int location = 1;
			for(int i = 1 ; i<=n;i++){
				for(int j = i+1 ; j<=n;j++){
					c[location] = a[i] + a[j];	
					location++;
				}
			}

			new HDOJ1280().findKth(c, b, k, 1, x);
			new HDOJ1280().quick(c, 1, k);
			
			for(int i = 1 ; i<= k  ; i ++){
				System.out.print(c[i]+" ");
			}
			System.out.println();
			
		}


		

	}

	public int partition(int a[], int f, int r) {

		int point = f;
		int i = f + 1;
		int j = r;
		int p = a[point];
		while (true) {
			while (i <=r && a[i] > p) {
				i++;
			}
			while (j > 0 && a[j] < p) {
				j--;
			}

			if (j <= i) {
				break;
			} else {
				int x = a[j];
				a[j] = a[i];
				a[i] = x;
			}
		}

		a[point] = a[j];
		a[j] = p;

		return j;

	}
	
	public void quick(int a[] , int f, int r){//快速排序
		if(f<r){
			int p = partition(a,f,r);
			quick(a,f,p-1);
			quick(a,p+1,r);
		}
	}

	public void findKth(int a[], int b[], int k, int f, int r) {//查找第K大的元素後傳回，就是前面是前K大元素

		if (f < r) {
			int p = partition(a, f, r);
			if (p == k) {
				return ;
			} else {
				if (p < k) {
					findKth(a, b, k, p + 1, r);
				} else {
					findKth(a, b, k, f, p - 1);
				}

			}

		}
		return ;
	}
}
           

但是送出後 Time Limit Exceeded, 後來改用Java裡面Arrays.sort，通過了，而且代碼僅用了1/3，

import java.util.Arrays;
import java.util.Scanner;

public class test {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		while (scan.hasNext()) {
			int n = scan.nextInt();
			int k = scan.nextInt();
			int a[] = new int[n];
			int x = n * (n - 1) / 2;
			int c[] = new int[x];
			for (int i = 0; i < n; i++) {
				a[i] = scan.nextInt();
			}
			int location = 0;
			for (int i = 0; i <n; i++) {
				for (int j = i + 1; j < n; j++) {
					c[location] = a[i] + a[j];
					location++;
				}
			}
			Arrays.sort(c);
			for (int i = x-1; i>x-1-k; i--) {
				System.out.print(c[i]);
				if(i!=x-k)
					System.out.print(" ");
			}
			System.out.println();
		}
	}
}
           

感覺奇怪，看了Java API才發現，原來sort方法就是利用快速排序的。應該是資料<=3000,我的算法不能展現優點，當資料非常多時，感覺我的就會比Arrays.sort快了。緊緊是感覺，我也不能輸入幾千個數來測試。。，