Quicksort geben StackOverFlow-Fehler

Question

Ich versuche, Quicksort-Algorithmus zu schreiben. Ich folgte einem Online-Tutorial, das ziemlich genau das Gleiche gemacht hat, aber ich bekomme einen StackOverFlow-Fehler.

public void mysort(int[] g) { 
    quickSort(g, 0, g.length - 1); 

    System.out.println(Arrays.toString(g)); 
} 

public void quickSort(int[] nums, int low, int high) { 
    int i = low; 
    int j = high; 

    int pivot = nums[(low + (high - low))/2]; 

    while (i <= j) { 

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

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

     while (i <= j) { 
      int temp = nums[i]; 
      nums[i] = nums[j]; 
      nums[j] = temp; 
      i++; 
      j--; 
     } 
    } 

    System.out.println(Arrays.toString(nums)); 

    if (low < j) { 
     quickSort(nums, low, j); 
    } 

    if (i < high) { 
     quickSort(nums, i, high); 
    } 
} 

Das Array I als Argument übergeben habe, ist [1, 2, 3, 4, 5, 5, 4, 3, 2, 1].

In der Quicksort-Methode gibt die println-Anweisung dies nach der ersten Schleife aus, [1, 4, 3, 2, 1, 2, 3, 4, 5, 5].

Was geht hier vor?

Answer 1

Sie die Pivot falsch berechnet wird, ist es nicht:

int pivot = nums[(low + (high - low))/2]; 

Es ist:

int pivot = nums[low + ((high - low)/2)]; 

Division in Mathematik hat eine höhere Priorität als sum und sub

Mit anderen Worten, Sie können es wie folgt schreiben:

int pivot = nums[low + (high - low)/2]; 

Ein weiteres Problem, finden Sie in Ihrem whiles ist, sind Sie für den Dreh nicht fragen, Sie sind für die Nummer in der Position des Dreh fragen nums[pivot], sollte es sein:

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

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

Schließlich ist nicht der Austausch while i<=j es ist:

if (i <= j) { 
    int temp = nums[i]; 
    nums[i] = nums[j]; 
    nums[j] = temp; 
    i++; 
    j--; 
    }