快速选择的正确条件

Question

我正在实现快速选择算法来获取数组中的第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的数组可能没有排序，因为我在上面的条件下返回。但是我找不到合适的条件，我只对数组中的前k个元素进行排序，而忽略了其余的元素，所以我不需要做任何额外的工作。我已经在线查看了一些实现，并在上面花了一些时间，但无法弄清楚，所以请联系我们寻求帮助。

Answer 1

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

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