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

Question

我试图了解quicksort的实现或应用程序以找到第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个最小元素，因此要使用quicksort，因为枢轴左侧的元素将小于枢轴，而枢轴右侧的元素将大于。这样，如果您要查找第4个最小元素，并且枢轴位于索引3处，则可以返回它，因为您知道它是第4个最小元素，因为它比第3个元素小3个元素。

我在理解分区方法中的两个交换时遇到麻烦。

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

分区内此交换代码的目的是什么？谁能举例说明为什么需要此代码？这些将如何相遇？

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

而且对于此交换行（也在分区内），为什么作者交换数据透视表和j，而不是数据透视表和i？它是任意的吗？

        swap(a,j, pivot);

Answer 1

您可以使用存在于以下位置的分区算法：快速排序分区算法

您使用的算法返回错误的数据透视