快速排序給出錯誤的排序順序

Question

我是新來的Java，我試圖實現QuickSort。 下面是我的腳本。

public class QuickSort { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     int a[] ={5,6,7,4,1,3}; 
     QuickSort qs = new QuickSort(); 
     qs.quickSort(a,0,a.length-1); 
     for(int i=0;i<a.length;i++) { 
      System.out.println(a[i]); 
     } 

    } 
    public void quickSort(int[] a,int left, int length) { 

     if(left >= length) return; 
     int index = partition(a,left,length); 
     if(left < index) { 
      quickSort(a,left,index-1); 
     } 
     else { 
      quickSort(a,index,length); 
     } 
    } 

    private int partition(int[] a,int l, int length) { 
     // TODO Auto-generated method stub 
     int left = l; 
     int right = length; 
     int pivot = a[(left+right)/2]; 
     while(left <= right) { 
      while(left < length && a[left] < pivot) { 
       left++; 
      } 
      while(right >= 0 && a[right] > pivot) { 
       right--; 
      } 
      if(left <= right) { 
       int temp = a[left]; 
       a[left]=a[right]; 
       a[right]=temp; 
       left++; 
       right--; 
      } 
     } 
     return left; 
    } 

} 

的時候，我打印解決方案，我得到下面的命令 -

[1,3,6,4,5,7] 

我無法找出錯誤，任何人都可以請幫我解決這個問題。

Answer 1

只是改變這個

if(left < index) { 
    quickSort(a,left,index-1); 
} 
else { 
    quickSort(a,index,length); 
} 

這個

quickSort(a,left,index-1); 
quickSort(a,index+1,length); 

既然你需要在陣列的每個分區遞歸排序陣！

Answer 2

快速排序將數組分成兩個較小的數組，位於數據透視的任一側。這意味着每次調用quicksort都會導致另外兩次調用quicksort。您的代碼目前以遞歸方式調用quicksort，但只有一半。

Quicksort(array) 
    pick a pivot 
    Arrays left, right 
    For each value in array 
     If value < pivot 
      Append to left array 
     Else 
      Append to right array 
    Quicksort(left) 
    Quicksort(right) 
    Return join(left, right) 

Answer 3

試試下面的代碼：

import java.util.ArrayList; 

public class MyQuickSort { 

/** 
* @param args 
*/ 
public static void main(String[] args) { 

    //int[] a = { 1, 23, 45, 2, 8, 134, 9, 4, 2000 }; 
    int a[]={23,44,1,2009,2,88,123,7,999,1040,88}; 
    quickSort(a, 0, a.length - 1); 
    System.out.println(a); 
    ArrayList al = new ArrayList(); 
} 

public static void quickSort(int[] a, int p, int r) 
{ 
    if(p<r) 
    { 
     int q=partition(a,p,r); 
     quickSort(a,p,q); 
     quickSort(a,q+1,r); 
    } 
} 

private static int partition(int[] a, int p, int r) { 

    int x = a[p]; 
    int i = p-1 ; 
    int j = r+1 ; 

    while (true) { 
     i++; 
     while (i< r && a[i] < x) 
      i++; 
     j--; 
     while (j>p && a[j] > x) 
      j--; 

     if (i < j) 
      swap(a, i, j); 
     else 
      return j; 
    } 
} 

private static void swap(int[] a, int i, int j) { 
    // TODO Auto-generated method stub 
    int temp = a[i]; 
    a[i] = a[j]; 
    a[j] = temp; 
} 

}

從here

Answer 4

下面拍攝的編輯的代碼，你可以取代它，

public void quickSort(int[] a,int left, int length) { 

      if(left >= length) return; 
      int index = partition(a,left,length); 
      if (left < index) 
       quickSort(a, left, index);  // left subarray 
      if (length > index + 1) 
       quickSort(a, index + 1, length); 
     } 

     private int partition(int[] arr,int l, int length) { 
      // TODO Auto-generated method stub 
      int pivot = arr[(l + length)/2]; 
      int left = l - 1; // index going left to right 
      int right = length + 1; // index going right to left 

      while (true) { 
       do { 
        left++; 
       } while (arr[left] < pivot); 
       do { 
        right--; 
       } while (arr[right] > pivot); 

       if (left < right){ 
       int temp = arr[left]; 
       arr[left] = arr[right]; 
       arr[right] = temp; 
       } 
       else 
        return right; // index of last element in the left subarray 
      }  
     } 

快速排序是分而征服算法。它首先將一個大列表分成兩個較小的子列表，然後對這兩個子列表進行遞歸排序。如果我們想在沒有任何額外空間的情況下對數組進行排序，則quicksort是個不錯的選擇。平均而言，時間複雜度爲O（n log（n））。

排序的陣列的基本步驟如下：

選擇一個樞軸，通常中間的一個 從兩端，交換元件，使上的所有元素的左小於所述樞轉並且在所有元素右側大於主鍵 遞歸排序左側部分和右側部分

Java中的Arrays.sort（）方法使用快速排序對基元數組進行排序，例如整數或浮點數組，並使用Mergesort來存放對象字符串數組。