java - 我不确定我的快速选择方法有什么问题

Question

因此，我尝试编写一段代码，使用快速排序在给定输入整数数组中选择第k个最小元素，但由于某种原因，正如您在代码中看到的那样下面，

public static int partition(int[] input, int first, int end) {
    int pivot = input[(first + end)/2];
    int i = first - 1;
    int j = end + 1;

    while (true) {

      do {
        i++;
      } while (input[i] < pivot);

      do {
        j--;
      } while (input[j] > pivot);

      if (i < j)
        swap(input, i, j);
      else
        return j;
    }
  }

  public static void swap(int[] input, int i, int j){
    int temp = input[i];
    input[i] = input[j];
    input[j] = temp;
  }

  public static int select(int[] input, int k){
    return mySelect(input, 0, input.length-1, k);
  }

  public static int mySelect(int[] input, int left, int right, int k){ 
    // If k is smaller than number of elements in array 
    if (k > 0 && k <= right - left + 1) { 

      int pos = partition(input, left, right); 

      if (pos - left == k - 1) 
        return input[pos]; 

      // If position is larger, recursive call on the left subarray 
      if (pos - left > k - 1)  
        return mySelect(input, left, pos-1, k); 

      // if smaller, recursive call on the right subarray 
      return mySelect(input, pos+1, right, k-pos+left-1); 
    } 

    System.out.println("Invalid k value");
    return Integer.MAX_VALUE; 
  }

public static void main(String[] args){
    test2 = new int[]{99, 44, 77, 22, 55, 66, 11, 88, 33};
    int[] test2 = new int[]{99, 44, 77, 22, 55, 66, 11, 88, 33};
    //testing for selecting kth min 
    System.out.println("The 1st smallest : " + select(test2, 1));
    System.out.println("The 2nd smallest : " + select(test2, 2));
    System.out.println("The 3rd smallest : " + select(test2, 3));
    System.out.println("The 4th smallest : " + select(test2, 4));
    System.out.println("The 6th smallest : " + select(test2, 6));
    System.out.println("The 9th smallest : " + select(test2, 9)); 
    }

但是我的第一个最小元素出现22，第二个最小元素返回11，而其他值是正常的。有人可以帮我找出我犯了什么错误吗？

Answer 1

您的代码中的问题出在分区中。 do while 是这里的罪魁祸首。您在检查条件之前更新了位置，这导致了 last 交换操作出现问题。

将你的方法更新为此，你就可以开始了

public static int partition(int[] input, int first, int end) {
    int pivot = input[(first + end)/2];
    int i = first;
    int j = end;

    while (true) {

      while (input[i] < pivot) {
        i++;
      }

      while (input[j] > pivot) {
        j--;
      }

      if (i < j)
        swap(input, i, j);
      else
        return j;
    }
}