JAVA:实现使用快速排序算法获取给定数组中的第 k 个最大或第 k 个最小元素算法(附完整源码)

package com.thealgorithms.maths;
import java.util.Arrays;
import java.util.Random;
public class FindKthNumber {
    private static final Random random = new Random();

    public static void main(String[] args) {
        /* generate array with random size and random elements */
        int[] nums = generateArray(100);

        /* get 3th largest element */
        int kth = 3;
        int kthMaxIndex = nums.length - kth;
        int targetMax = findKthMax(nums, kthMaxIndex);

        /* get 3th smallest element */
        int kthMinIndex = kth - 1;
        int targetMin = findKthMax(nums, kthMinIndex);

        Arrays.sort(nums);
        assert nums[kthMaxIndex] == targetMax;
        assert nums[kthMinIndex] == targetMin;
    }

    private static int[] generateArray(int capacity) {
        int size = random.nextInt(capacity) + 1;
        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt() % 100;
        }
        return array;
    }

    private static int findKthMax(int[] nums, int k) {
        int start = 0, end = nums.length;
        while (start < end) {
            int pivot = partition(nums, start, end);
            if (k == pivot) {
                return nums[pivot];
            } else if (k > pivot) {
                start = pivot + 1;
            } else {
                end = pivot;
            }
        }
        return -1;
    }

    private static int partition(int[] nums, int start, int end) {
        int pivot = nums[start];
        int j = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[i] < pivot) {
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, start, j);
        return j;
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69