数组的第K大值

二分查找和堆查找

一、二分查找是利用快速排序的二分特点
利用快排在排序时，把数组分成两部分，一部分小于一个值，另一部分大于这个值的特点
将数组用快排从大到小排序，取temp值为数组的第一个数a[start],那么经过一轮调整之后，数组左边的所有值大于或等于temp，数组右边的所有值都小于或等于temp，假设此时temp是数组第i个数。
如果i正好等于K，那么temp就是第K大值
如果i大于K，那么说明第K大值在数组左边，则继续在左边查找
如果i小于K，那么说明第K大值在数组的右边，继续在右边查找
每一轮排序都重复上述步骤，直到找到第K大值。

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        return quickSort(a, 0, n - 1, K);
    }

    private int quickSort(int[] a, int start, int end, int k) {
        int temp = a[start];
        int s = start, e = end;
        while (s < e) {
            while (s < e && temp >= a[e]) e --;
            a[s] = a[e];
            while (s < e && temp <= a[s]) s ++;
            a[e] = a[s];
        }
        a[s] = temp;
        if (s == k - 1) {
            return a[s];
        } else if (s > k - 1) {
            return quickSort(a, start, s - 1, k);
        } else {
            return quickSort(a, s + 1, end, k);
        }
    }
}

二、堆查找是利用堆排序的特点
比较直接，堆排序时，如果是从小到大排序则是先建立一个大顶堆，然后依次从大到小排列各值
第K个排到的值就是第K大值

import java.util.*;

public class Finder {
    public int findKth(int[] a, int n, int K) {
        // write code here
        // build heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(a, n, i);
        }
        // sort top K
        for (int i = n - 1; i >= n - K; i--) {
            swap(a, 0, i);
            heapify(a, i, 0);
        }
        return a[n-K];
    }

    private void heapify(int[] a, int n, int k) {
        int temp = a[k];
        int t = 2 * k + 1;
        while (t < n) {
            if (t + 1 < n && a[t] < a[t+1]) {
                t ++;
            }
            if (temp < a[t]) {
                a[k] = a[t];
                k = t;
                t = 2 * k + 1;
            } else {
                break;
            }
        }
        a[k] = temp;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}