Top K問題概述

• 在非海量數(shù)據(jù)的情況下，Top K問題的首推解法就是快排中的Parition算法。不僅平均時間復(fù)雜度優(yōu)越，可以達(dá)到O(n)，并且相比于基于堆的算法（包括：min_heapify、build_heap、insert等一系列過程），編碼更簡潔。
• 在海量數(shù)據(jù)的情況下，還是老老實(shí)實(shí)選擇基于堆的這一數(shù)據(jù)結(jié)構(gòu)的算法吧。時間復(fù)雜度為O(nlogk)。并且大多數(shù)高級編程語言中都應(yīng)該內(nèi)置了基于堆的API，所以編寫起來也沒有那么麻煩，例如JDK中的：java.util.PriorityQueue<>。

基于Partition算法

• 選擇一個Position（稱為基準(zhǔn)），基于該算法的Top k算法，非常受Position好壞的影響，所謂的壞，有可能使時間復(fù)雜度達(dá)到O(n*n)。
• 然后利用Partition算法進(jìn)行劃分，如果Partition得到的p小于K，則繼續(xù)劃分p的右邊，如果p大于K，則繼續(xù)劃分p的左邊，如果p等于K，則算法結(jié)束。

Code

import java.util.Scanner;

/**
 * 利用快排中parition算法，找到第k大數(shù)，平均時間復(fù)雜度為O(n)
 */
public class FindK
{
    //測試
    public static void main(String[] args)
    {
        int k = 0;
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        scanner.close();

        int[] a = {2, 6, 3, 10, 45, 12, 5, 6, 5, 6};
        if (k >= 0 && k < a.length) {
            findMaxK(a, 0, a.length - 1, k);
            System.out.println("第"+ (k+1) +"大數(shù)為：" + a[k]);
        } else
            System.out.println("are you kidding me ?");
    }
    
    //遞歸劃分
    private static void findMaxK(int[] a, int low, int high, int k)
    {
        int p = partition(a, low, high);
        if (p == k)
        {
            return;
        }
        if (p < k)
        {
            findMaxK(a, p + 1, high, k);
        }else{
            findMaxK(a, low, p - 1, k);
        }
    }

    //核心算法：劃分
    private static int partition(int[] a, int low, int high)
    {
        int position = a[high];
        int i = low - 1;
        for (int j = low; j < high; ++j)
        {
            if (a[j] <= position)
            {
                ++i;
                exchange(a, i, j);
            }
        }
        exchange(a, i + 1, high);
        return i + 1;
    }

    static void exchange(int[] a, int i, int j)
    {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}