реализация QuickSort ниже равна

Question

Я посмотрел на реализацию QuickSort, и я видел, что все веб-сайты имеют такое определение:

private void quickSort(int [] array, int low, int high) {   
    int i = low; int j = high; 
    int pivot = array[low+(high-low)/2]; 
    while (i <= j) { 
     while (array[i] < pivot) { i++; } 
     while (array[j] > pivot) { j--; } 
     if (i <= j) { 
      int temp = arr[i]; 
      arr[i]=arr[j]; 
      arr[j]=temp; 
      i++; j--; 
     } 
    } 
    if (low < j) quickSort(array, low, j); 
    if (i < high) quickSort(array, i, high); 
} 

Я хочу спросить вас о время (я < = J), почему может 't это просто while (i < j), потому что он сравнивает тот же элемент массива, я провел несколько тестов и работает без равных. Учитывая тот факт, что все реализации одинаковы, он должен иметь смысл, но я не знаю, какой из них действителен.

Answer 1

Я бы начал с указания на ошибку в коде, которую вы пытаетесь переключить элементы массива в несуществующий массив (я предполагаю, что это просто неправильная копия). см. мой фиксированный код ниже.

Чтобы ответить на ваш вопрос, код в конечном итоге попадет в нужный отсортированный массив, но он будет запускать несколько ненужных итераций, когда он достигнет точки, где i = j. т.е. если первоначальный список массив был {24,2,1,31,45} с while(i<=j) он будет работать через QuickSort рекурсивно только 3 раза:

Выход будет:

[24, 2, 1, 31, 45] 
[1, 2, 24, 31, 45] 
[1, 2, 24, 31, 45] 

Как при запуске его с while(i<j) он будет работать в 4 раза рекурсивно :

[24, 2, 1, 31, 45] 
[1, 2, 24, 31, 45] 
[1, 2, 24, 31, 45] 
[1, 2, 24, 31, 45] 

3-й раз, не было необходимости, и единственная причина, он побежал снова, потому что я = у и вместо перехода оба курсора к следующему элементу он просто гр снова повторил метод с теми же низкими и высокими значениями.

import java.util.Arrays; 
public class HisQuickSort { 

private void quickSort(int [] array, int low, int high) { 

    int i = low; int j = high; 
    int pivot = array[low+(high-low)/2]; 
    while (i <= j) { 
     while (array[i] < pivot) { i++; } 
     while (array[j] > pivot) { j--; } 
     if (i <= j) { 
      int temp = array[i]; 
      array[i]=array[j]; 
      array[j]=temp; 
      i++; j--; 
     } 
    } 
    if (low < j) quickSort(array, low, j); 
    if (i < high) quickSort(array, i, high); 
    System.out.println(Arrays.toString(array)); 

} 

public static void main(String a[]){ 

    HisQuickSort sorter = new HisQuickSort(); 
    //int[] array2 = new int[1000]; 
    //array2 = randomizeArray(array2); 
    int[] input = {24,2,1,45,31}; 
    System.out.println(Arrays.toString(input)); 

    sorter.quickSort(input, 0, input.length-1); 

} 
}