快排法求第k大

快排法求第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  i && a[j] > spliter) j--;
        if (j == i) break;
        a[i] = a[j];
        a[j] = spliter;
        i++;
        while (j > i && a[i]  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();
}
}