Java 實作 堆排序 快速排序 以及 TopK問題(二)

接上文

已知快速排序可以将一個數組分成兩部分，一部分大于某個值，一部分小于某個值，那麼由這點可以推出取TopK值的方法如下：

假設快排每一趟的分割值的點為p,數組長度為n,那麼需要比較n-p與k,如果恰好K==n-p，那麼隻需要取p點之後的所有值就行了。

如果k<n-p,那麼遞歸右邊至下一趟，k不變

如果k>n-p,先輸出右邊的n-p個值，再遞歸左邊尋找Top(k-n+p)值

代碼如下

public class quickSort {


	 public static void main(String[] args)  {
	     int[] arr={5,62,81,63,13,43,34,5,8,9,6,44};
	     int k=5;
	     
	     quickSor(arr,0,arr.length-1,k);
	     
	 }


	private static void quickSor(int[] arr, int i, int j, int k) {
		if(i<j){
			int pos=partition(arr, i, j);
//			print(arr,i,j);
//			System.out.println(pos);
			int temp=j-pos;
			if(temp==k){
				print(arr,pos+1,j);
				return;
			}
			else if(temp<k){
				print(arr,pos+1,j);
				quickSor(arr,i,pos,k-temp);
			}
			else if(temp>k){
				quickSor(arr,pos+1,j,k);
			}
		}
	}
	
	private static void print(int[] arr, int i, int j) {
		for(int x=i;x<=j;x++)
			System.out.print(arr[x]+" ");
	}


	private static int partition(int n[], int left, int right) { 
        int pivot = n[left]; 
        while (left < right) { 
            while (left < right && n[right] >= pivot) 
                right--; 
            if (left < right) 
                n[left++] = n[right]; 
            while (left < right && n[left] <= pivot) 
                left++; 
            if (left < right) 
                n[right--] = n[left]; 
        } 
        n[left] = pivot; 
        return left; 
    } 
}
           

輸出為63 81 62 43 44  省去了給TOPK排序的消耗，我認為這種方式是最高效率的