快速排序给出错误的排序顺序

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来存放对象字符串数组。