在quicksort应用程序中这些交换代码行的目的是什么？

我试图理解quicksort的实现或应用程序来找到第k个最小元素这是我想要了解的代码

public int quicksort(int a[], int start, int end, int k) { if(start  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  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，因为pivot左边的元素小于pivot，而pivot的右边元素大于。 因此，如果你试图找到第4个最小元素，并且数据透视位于索引3，那么你可以返回它，因为你知道它是第4个最小元素，因为有3个元素比它小。

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

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

这个交换代码在分区内的目的是什么？ 任何人都可以举例说明为什么这些代码是必要的？ 这些如何相遇？

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

而且对于这个交换行（也在内部分区），为什么作者交换枢轴和j，而不是枢轴和我？ 这是武断的吗？

  swap(a,j, pivot); 

Answer 1

您可以使用以下分区算法： 快速排序分区算法

您使用的算法返回不正确的数据透视表