快排法求第k大，复杂度为O(n)

import com.sun.media.sound.SoftTuning;

import java.util.Arrays;

import java.util.Random;

public class Main {

int[] generate(int n) {

    Random random = new Random();

    int[] a = new int[n];

    for (int i = 0; i < a.length; i++) {

        a[i] = random.nextInt(20);

    }

    return a;

}

int stupid(int[] a) {

    Arrays.sort(a);

    return a[a.length / 2];

}

int go(int a[], int left, int right, int k) {

    if (left == right) return a[left];

    int i = left, j = right;

    int spliter = a[left];

    while (true) {

        while (j > i && a[j] > spliter) j--;

        if (j == i) break;

        a[i] = a[j];

        a[j] = spliter;

        i++;

        while (j > i && a[i] < spliter) i++;

        if (j == i) break;

        a[j] = a[i];

        a[i] = spliter;

        j--;

    }

    if (i - left == k) return a[i];

    else if (i - left > k) {

        return go(a, left, i - 1, k);

    } else {

        return go(a, i + 1, right, k - (i + 1 - left));

    }

}

int fast(int[] a) {

    return go(a, 0, a.length - 1, a.length / 2);

}

Main() {

    Random random = new Random();

    for (int i = 0; i < 100; i++) {

        int[] a = generate(random.nextInt(100) + 31);

        int[] b = Arrays.copyOfRange(a, 0, a.length);

        int mine = fast(b);

        b = Arrays.copyOfRange(a, 0, a.length);

        int ans = stupid(b);

        if (mine != ans) {

            throw new RuntimeException("error");

        }

    }

}

public static void main(String[] args) {

    new Main();

}

}