题解 | #寻找第K大#

package org.example.test;

/**
 * 采用快速排序，每次以当前表中第一个元素为轴来对表进行划分，将表中比枢轴大的元素向左移，
 * 比表中小的元素向右移，使得下一趟partition操作后，表中的元素备枢轴一份为二。
 * 每次partition可以确定一个第N(N=low+1)大元素，如果N==K，则是第K大元素。
 */
public class TopKTest {
    public static void main(String[] args) {
        int[] nums = {1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663};
        System.out.println(findKth(nums, 49, 24));
    }

    public static int findKth(int[] a, int n, int K) {
        // write code here
        quickSort(a, 0, n - 1, K);
        return a[K-1];
    }

    public static void quickSort(int[] a, int low, int high, int k) {
        if (low >= high) {
            return;
        }
        int p = partition(a, low, high);
        if (p + 1 == k) {
            return;
        }
        if(p+1>k) {
            quickSort(a, low, p - 1, k);
        } else {
            quickSort(a, p + 1, high, k);
        }
    }

    private static int partition(int[] a, int low, int high) {
        int tmp = a[low];
        while (low < high) {
            while (low < high && a[high] <= tmp) {
                --high;
            }
            a[low] = a[high];
            while (low < high && a[low] >= tmp) {
                ++low;
            }
            a[high] = a[low];
        }
        a[low] = tmp;
        return low;
    }