QuickSort Implementierung niedriger gleich

Question

Ich schaute über QuickSort Implementierung und ich habe gesehen, dass alle Websites haben diese Definition:

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); 
} 

Ich möchte Sie während fragen (i < = j), warum kann Es ist nur während (i < j), weil es das gleiche Array-Element vergleicht, habe ich einige Tests gemacht und es funktioniert ohne gleich. Die Tatsache, dass alle Implementierungen gleich sind, muss eine Bedeutung haben, aber ich weiß nicht, welcher der gültige Fall ist.

Answer 1

Ich würde anfangen, indem Sie einen Fehler in Ihrem Code zeigen Sie versuchen, die Array-Elemente in einem nicht vorhandenen Array (ich denke nur eine falsche Kopie einfügen). Siehe meinen festen Code unten.

Um Ihre Frage zu beantworten, wird der Code schließlich nach rechts sortieren Array, aber es wird ein paar unnötige Iterationen ausführen, wenn es zu dem Punkt kommt, wo i = j. dh wenn die ursprüngliche Array-Liste {24,2,1,31,45} mit den while(i<=j) war es durch QuickSort rekursiv nur 3-mal ausgeführt werden:

Der Ausgang wäre:

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

Wie, wenn es mit while(i<j) läuft wird es 4 mal laufen rekursiv :

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

das 3. Mal war unnötig, und der einzige Grund, warum es wieder ran war, weil i = j und stattdessen beide Cursor auf das nächste Element der Verschiebung es nur c die Methode rekursiv erneut mit den gleichen niedrigen und hohen Werten.

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); 

} 
}