快速排序劃分

Question

我有以下陣列：

int[] arr = { 19, 4, 2, 3, 9, 2, 10, 2, 7, 12, 5, 16, 8, 3, 11, 14, 0, 5 }; 

現在我用快速排序的分區與轉動部件7的陣列分區：

public static void partition(int[] arr, int low, int high) { 
    int pivot = arr[low + (high - low)/2]; 
    int i = low; 
    int j = high; 
    while (i <= j) { 
     // If the current value from the left list is smaller then the pivot 
     // element then get the next element from the left list 
     while (arr[i] < pivot) { 
      i++; 
     } 
     // If the current value from the right list is larger then the pivot 
     // element then get the next element from the right list 
     while (arr[j] > pivot) { 
      j--; 
     } 

     // If we have found a values in the left list which is larger then 
     // the pivot element and if we have found a value in the right list 
     // which is smaller then the pivot element then we exchange the 
     // values. 
     // As we are done we can increase i and j 
     if (i <= j) { 
      swap(arr, i, j); 
      i++; 
      j--; 
     } 
    } 
} 

我感到困惑與結果：

5 4 2 3 0 2 3 2 5 12 7 16 8 10 11 14 9 19 

我認爲每個元素< = pivot（7）必須在左邊，並且每個元素> pi vot元素必須在右側。但是，爲什麼12離開到7？

Answer 1

在C++甲partition函數看起來像這樣：

while (first!=last) { 
    while (pred(*first)) { 
     ++first; 
     if (first==last) return first; 
    } 
    do { 
     --last; 
     if (first==last) return first; 
    } while (!pred(*last)); 
    swap (*first,*last); 
    ++first; 
    } 
    return first; 

First和last是指向數組中的元素，類似於您i和j變量迭代器。 pred是謂詞的縮寫，例如可以是i <= 7。從本質上講，這個函數返回中點，所以在C++代碼中，通過迭代到中點左邊的所有元素，以及從迭代到最後的所有元素。爲了減少混淆：

我應該是第一個元素，j應該是最後一個元素。

//獲取中點第一

...

// Note. <= is the opposite of > 
// Which logically is the same as 
// pred is the opposite of !pred 
    while (i != j) { 
    while (i <= midpoint) { 
     ++i; 
     if (i == j) return i; 
    } 
    do { 
     --j; 
     if (i == j) return i; 
    } while (i > midpoint); 
    swap (i, j); 
    ++i; 
    } 
    return i; 

... 

for (int i = 0; i < get_midpoint(...); i++) 
for (int i = get_midpoint; i < end_of_array; i++) 

Answer 2

此實現不能保證你所期望的。它所做的就是下面的（前提是你改變arr[i] <= pivot，作爲Achintya傑哈建議，否則它甚至不能保證）：

每對價值a, b與a <= pivot < b，可以保證a將留下b最後。但是，您不保證關於pivot在最終數組中的確切位置（僅限於所有值都較大的值）。

Answer 3

的快速排序法

package com.Ramesh; 

public class QuickSort { 

public void sort(int[] a,int left,int right){ 
    if(left<right) 
    { 
     int partition=getPartition(a, left, right); 
     sort(a,left,partition-1); 
     sort(a,partition+1,right); 
    } 
} 
public int getPartition(int[] a,int l,int r) 
{ 
    int pivot=a[l]; 
    int left=l; 
    int right=r; 
    while(left<right) 
    { 
     while(a[left]<pivot){ 
      left++; 
     } 

     while(a[right]>pivot){ 
      right--; 
     } 

     if(left<right){ 
      int temp=a[left]; 
      a[left]=a[right]; 
      a[right]=temp; 
     } 

    } 
    return right; 
} 

} 

創建一個類2.創建另一個類調用排序方法

import java.util.Scanner; 
public class Execute { 

    private int[] a; 
    private int len; 

    public int[] getA() { 
     return a; 
    } 

    public void setA(int[] a) { 
     this.a = a; 
    } 

    public int getLen() { 
     return len; 
    } 

    public void setLen(int len) { 
     this.len = len; 
    } 

    public static void main(String[] args) { 
     Execute ex=new Execute(); 
     ex.takeInput(); 
     QuickSort q=new QuickSort(); 
     q.sort(ex.getA(),0,ex.getLen()-1); 
     System.out.println("Printing the the Sorted Object"); 
     System.out.println(ex); 
     } 

    public void takeInput() 
    { 
     Scanner s1=new Scanner(System.in); 
     System.out.println("Please enter the no of element to be sorted"); 
     len=s1.nextInt(); 
     a=new int[len]; 
     System.out.println("Pls enter the elements"); 
     for(int i=0;i<len;i++){ 
      a[i]=s1.nextInt(); 
     } 

    } 

    @Override 
    public String toString(){ 
     StringBuffer s=new StringBuffer(""); 
     for(int i=0;i<this.len;i++){ 
      s.append(this.a[i]+"\n"); 
     } 
     return s.toString(); 

    } 

}