QuickSort geben Ausnahme im Thread "Haupt" java.lang.StackOverflowError

Question

Ich habe Quick-Code wie folgt geschrieben. Die Sortierung nimmt die mittlere Zahl als Pivot:

import java.util.Arrays; 

public class QuickSort { 

    public static void main(String[] args) { 

     int[] numbers = {3, 6, 9, 1, 34}; 

     int low = 0; 

     int high = numbers.length - 1; 

     quicksort(numbers, low, high); 

    } 

    static void quicksort(int[] arr, int low, int high) { 

     int i = low; 
     int j = high; 

     int middle = arr[(low + high)/2]; 

     while(i < j) {  
      while(arr[i] < middle) { 
       i++; 
      } 

      while(arr[j] > middle) { 
       j--; 
      } 

      if(i <= j) { 
       int temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 


     } 

     if(low < j) { 
      quicksort(arr, low, j);   
     } 

     if(i < high) { 
      quicksort(arr, i, high); 
     } 

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

    } 

} 

Allerdings, nach dem Ausführen des Codes bekomme ich stackoverflow Ausnahme. Es sagt Exception in thread "main" java.lang.StackOverflowError

Exception in thread "main" java.lang.StackOverflowError 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 
    at QuickSort.quicksort(QuickSort.java:47) 

Bitte helfen Sie mir herauszufinden, was beim Betrieb des obigen Code falsch sein könnte.

Answer 1

Der Wert von i und j muss entsprechend inkrementiert und dekrementiert werden. Bitte beachten Sie den folgenden Code:

import java.util.Arrays; 

public class QuickSort { 

    public static void main(String[] args) { 

     int[] numbers = {3, 9, 6, 1, 34}; 

     int low = 0; 

     int high = numbers.length - 1; 

     quicksort(numbers, low, high); 

    } 

    static void quicksort(int[] arr, int low, int high) { 

     int i = low; 
     int j = high; 

     int middle = arr[(low + high)/2]; 

     while(i <= j) {  
      while(arr[i] < middle) { 
       i++; 
      } 

      while(arr[j] > middle) { 
       j--; 
      } 

      if(i <= j) { 
       int temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 

       i++; 
       j--; 
      } 


     } 

     if(low < j) { 
      quicksort(arr, low, j);   
     } 

     if(i < high) { 
      quicksort(arr, i, high); 
     } 

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

    } 

} 

Hoffe, das hilft!

Answer 2

Sie können diese link zum besseren Verständnis der schnellen Sortierung betrachten, wie es funktioniert.

public static void quickSort (int [] arr, int niedrig, int hoch) { if (arr == null || arr.length == 0) return;

 if (low >= high) 
      return; 


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


     int i = low, j = high; 
     while (i <= j) { 
      while (arr[i] < pivot) { 
       i++; 
      } 

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

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

     // recursively sort two sub parts 
     if (low < j) 
      quickSort(arr, low, j); 

     if (high > i) 
      quickSort(arr, i, high); 
    }