快速选择的正确条件

Question

我正在实现快速选择算法来获取数组中的第1个CCD_元素，但我被困在了一个不知道如何解决的地方。这是我不起作用的代码：

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);