为什么在快速排序应用中需要这种排序

Question

我试图理解快速排序应用程序中用于查找第 k 个最小元素的代码。

这里是作者写的代码

public class KthSmallest {
    public static void main(String[] args) {
        int[] test = {2,3,1,5,7,6,9};
        System.out.println("4th smallest is " + quick_select(test, 4, 0, test.length - 1));
    }
    private static int quick_select(int[] a, int k, int left, int right) {
         int pivot=findpivot(a,left,right);
         if(pivot==k-1){
              return a[pivot];
         }
         if(k-1<pivot){
              return quick_select(a, k, left, pivot-1);
          }
          else {
              return quick_select(a, k, pivot+1, right);
          }
        }
        private static int findpivot(int[] a, int left, int right) {
            int pivot = a[(left+right)/2];
            while(left<right){
                while(a[left]<pivot){
                    left++;
                }
                while(a[right]>pivot){
                    right--;
                }

                if(left<=right){
                    swap(a,left,right);
                    left++;
                    right--;
                }

            }
            return left;
        }

        private static void swap(int[] a, int i, int j) {
            int temp=a[i];
            a[i]=a[j];
            a[j]=temp;

        }


}

我正在尝试了解此代码段在查找数据透视表中的意义

     if(left<=right){
                    swap(a,left,right);
                    left++;
                    right--;
        }

这是你所知道的。 left 左边的所有元素都小于 pivot。 right of right of right 的所有元素都大于 pivot。任何人都可以凭直觉解释为什么如果右 >= 左则有必要交换？

Answer 1

第一个循环向右移动 left，直到它找到一个大于主元的元素。第二个循环将 right 向左移动，直到找到小于主元的元素。此时 a[left] 应该在枢轴之后移动，a[right] 应该在枢轴之前移动，if 会处理这个问题。

Answer 2

Can anyone explain with that intuition why it is necessary to swap if right>= left?

right 和 left 是索引 - 而不是项目本身（这可能是您混淆的根源）。如果枢轴 "right" 的数字小于枢轴，则应将其移至枢轴左侧。

相应地，如果枢轴左侧的数字大于枢轴 - 它应该移动到（枢轴的）右侧。

一旦我们运行进入两个这样的项目，我们使用 if 条件来确保我们没有在之前的循环中进入 "too far" 并且那些数字是发现确实应该交换，此检查 - 测试索引 left <= right 否则没有理由进行交换（或继续运行ning...）。

注意：最后一段的解释表明我们实际上不必检查if(left<=right)——检查if(left<right)就足够了

为什么在快速排序应用中需要这种排序

Why is this sort necessary in quick sort application

java

sorting

algorithm

quicksort