快速排序应用程序中这些交换代码行的目的是什么？

Question

我正在尝试了解快速排序的实现或应用程序以找到第 k 个最小元素这是我试图理解的代码

public int quicksort(int a[], int start, int end, int k) {
    if(start < end) {
        int pivot = partition(a, start, end);
        if(pivot == k -1) {
            return pivot;
        } else if(pivot > k - 1){
            return quicksort(a, start, pivot, k);
        } else {
            return quicksort(a, pivot + 1, end, k);
        }
    } else if(start == end) {
        return k==1?start:-1;
    } else {
        return -1;
    }
}
public int partition(int a[], int start, int end) {
    int pivot = start;
    int i = pivot + 1;
    int j = end;
    while(a[i] < a[pivot] && i < end) {
        i ++;
    } 
    while(a[j] > a[pivot] && j >= 0) {
        j --;
    } 
    if(i < j) {
        swap(a, start, end);
    }
    swap(a,j, pivot);
    return pivot;
}
private void swap(int a[], int swap1, int swap2) {
    int temp = a[swap1];
    a[swap1] = a[swap2];
    a[swap2] = temp;
}

我了解到，为了尝试找到第 k 个最小的元素，您想使用快速排序，因为主元左侧的元素将小于主元，而主元右侧的元素将大于。这样一来，如果你试图找到第 4 个最小的元素，并且枢轴位于索引 3 处，你可以 return 它因为你知道它是第 4 个最小的元素，因为有 3 个元素比它小。

我无法理解分区方法中的两个交换。

在第一个 while 循环结束时，索引 i 将位于所有小于主元的元素都在 i 左侧的位置。索引 j 将位于所有大于主元的元素都位于 j 右侧的位置。

分区内的这个交换代码的目的是什么？任何人都可以举例说明为什么需要这段代码吗？他们将如何相遇？

if(i < j) {
        swap(a, i, j);
}

而且对于这个交换线（也在分区内），为什么作者交换了 pivot 和 j，而不是 pivot 和 i？是不是很随意？

        swap(a,j, pivot);

Answer 1

您可以使用目前的分区算法：Quick sort partition algorithm

您使用的算法returns 不正确的主元

快速排序应用程序中这些交换代码行的目的是什么？

What is the purpose of these lines of swap code in quicksort application?

java

arrays

algorithm

sorting

quicksort