Быстрая сортировка в Java-неправильном выходе

Question

Я пытаюсь реализовать быструю сортировку с использованием Java. Функция разбиения делает то, что она должна делать. То есть, разделите массив вокруг точки поворота (я выбрал элемент как ось поворота) , Но конечный результат не в отсортированном порядке. Я не могу понять ошибку. Может кто-то помочь?

public class Quick_sort { 


    public static int arr[] = {11, 2, 7, 1, 5, 4, 12, 65, 23}; 
    public static int temp = 0; 

    public static void main(String args[]) { 
     int p=0; 
     int r=arr.length; 

     quick_sort(p,r);   

     for(int i: arr) 
      System.out.println(i); 
    } 


    public static int partition(int p, int r) { 
     if(p < r) { 
      int pivot=arr[p]; 
      int i=1; 

      for(int j=1;j<r;j++) { 
       if(arr[j]<pivot) { 
        temp=arr[j]; 
        arr[j]=arr[i]; 
        arr[i]=temp; 
        i++; 
       } 
      } 

      temp=arr[i-1]; 
      arr[i-1]=arr[p]; 
      arr[p]=temp; 
      for(int m=0;m<r;m++) { 
       if(arr[m]==pivot) { 
        temp=m; 
       } 
      } 
     } 
     return temp;  
    } 

    public static void quick_sort(int p,int r) { 
     if(p>=r) return; 
     int index=partition(p,r); 
     quick_sort(p,index-1); 
     quick_sort(index+1,r-1); 

    } 
} 

Answer 1

Это полный пример реализации QuickSort:

public class QuickSort { 
    public static void main(String[] args) { 
     int[] x = { 9, 2, 4, 7, 3, 7, 10 }; 
     System.out.println(Arrays.toString(x)); 

     int low = 0; 
     int high = x.length - 1; 

     quickSort(x, low, high); 
     System.out.println(Arrays.toString(x)); 
    } 

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

     if (low >= high) 
      return; 

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

     // make left < pivot and right > pivot 
     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); 
    } 
} 

вы можете найти более here.

Answer 2

В последней строке

quick_sort(index+1,r-1); 

Вы пропустить последний элемент массива. Но последний элемент также должен быть отсортирован. Попробуйте его с:

quick_sort(index+1,r); 

И лучше приспособить переменные I и J в методе разбиения на текущую обрабатываемую часть массива.

Answer 3

Так что я попытался исправить это. Попробуйте с (основной функцией):

int r=arr.length-1; 

и изменить функцию секционирования на:

public static int partition(int p, int r) { 
    if(p < r) { 
     int pivot=arr[p]; 
     int i= p ; 

     for(int j=(p+1);j<=r;j++) { 
      if(arr[j]<pivot) { 
       temp=arr[j]; 
       arr[j]=arr[i + 1]; 
       arr[i + 1] = arr[i]; 
       arr[i] = temp; 
       i++; 
      } 
     } 
     temp = i; 
    } 
    return temp;  
} 

, а также в быстрой сортировке метод:

quick_sort(p,index-1); 
quick_sort(index+1,r); 

вы видите твоя проблема? Основная проблема заключалась в том, чтобы не адаптировать переменные к тем меньшим частям, на которые вы сейчас смотрите. Это было хорошо для первого раунда раздела, но не для следующего, поскольку у вас были прежние переменные.