Почему это необходимо для быстрого сортировки приложений

Question

Я пытаюсь понять код в приложении quicksort, чтобы найти 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--; 
     } 

Вот то, что вы знаете. Все элементы слева от них меньше, чем точка поворота. Все элементы справа от права справа больше, чем ось. Может ли кто-нибудь объяснить с этой интуицией, почему необходимо поменять местами, если right> = left?

Answer 1

Может ли кто-нибудь объяснить с этой интуицией, почему это необходимо для обмена, если right> = left?

right и left являются индексы - не сами предметы (которые, вероятно, является источником вашей путаницы). Если число справа от оси вращения меньше, чем точка поворота, его следует перемещать влево от поворота.

Соответственно, если число слева от оси вращения больше, чем точка поворота - его следует перемещать вправо (от оси вращения).

Как только мы сталкиваемся с двумя такими элементами, мы используем условие if, чтобы убедиться, что мы не зашли слишком далеко в предыдущие циклы и что числа, которые были найдены действительно, должны быть заменены, эта проверка - тесты что индексы left <= right в противном случае нет причин делать обмен (или продолжать работать ...).

Примечание: Объяснение в последнем абзаце, показывают, что мы на самом деле не должны проверить if(left<=right) - это достаточно хорошо, чтобы проверить, что if(left<right)

Answer 2

Первый цикл перемещает left вправо, пока не найдет элемент, который больше, чем ось поворота. Второй цикл перемещает right влево, пока не найдет элемент, меньший, чем точка поворота. На этом этапе a[left] должен перемещаться после поворота, а a[right] должен двигаться до поворота, если это позаботится об этом.