快速选择的正确条件

Question

我正在执行 quick-select 算法来获取数组中的第 k 个元素，我被困在一个我不知道如何解决的地方。这是我的代码不起作用：

public static void main (String[] args) {
    int[] arr = new int[]{7,6,5,4,3,2,1}; 
    int k = 4;
    quickSort(arr, 0, arr.length - 1, k);
    return arr[k];
}

private static void quickSelect(int[] nums, int start, int end, int k) {
    if (start < end) {
        int partitionIndex = getPartitionIndex(nums, start, end);
        if (partitionIndex == k) {
            return;
        }
        quickSelect(nums, start, partitionIndex - 1, k);
        quickSelect(nums, partitionIndex + 1, end, k);
    }
}

private int getPartitionIndex(int[] nums, int start, int end) {
    int pivot = nums[end];
    int index = start;
    for (int i = start; i <= end; i++) {
        int current = nums[i];
        if (current < pivot) {
            swap(nums, index, i);
            index++;
        }
    }
    swap(nums, index, end);
    return index;
}

private void swap(int[] nums, int i, int j) {
    if (i == j) {
        return;
    }
    nums[i] = nums[i] ^ nums[j];
    nums[j] = nums[i] ^ nums[j];
    nums[i] = nums[i] ^ nums[j];
}

当然，如果我删除这些行：

        if (partitionIndex == k) {
            return;
        }

它变成了快速排序并且工作正常。我明白为什么它不起作用，因为在上述条件下，我从 0 到 k 得到的数组可能不会像我 return 那样排序。但是我无法找到正确的条件，我只对数组中的前 k 个元素进行排序而忽略其余的元素，这样我就不会做任何额外的工作。我在网上看了一些实现并在上面花了一些时间，但无法弄清楚，所以寻求帮助。

Answer 1

如果k < partitionIndex，只检查左分区，否则只检查右分区。

        if (k < partitionIndex)
            quickSelect(nums, start, partitionIndex - 1, k);
        else
            quickSelect(nums, partitionIndex + 1, end, k);

快速选择的正确条件

Correct conditions for quickselect

java

quicksort

quickselect