详解快速排序算法中的区间划分法及Java实现示例

public class Partition { 
 
 /** 
  * 基于base划分，小的在左，大的在右， 不要求整个序列有序 
  * 
  * @param ary 
  * @param base 
  */ 
 static void sort(int[] ary, int base) { 
  int left = 0; 
  int right = ary.length - 1; 
   
  int leftpoint = left, rightpoint = right; 
   
  while (true) { 
   // 分成左右两边同时进行比较，一边从左向右，一边从右向左， 
   while (leftpoint < right && ary[leftpoint++] < base); //leftpoint大于right或ary[leftpoint]>base停止循环 
    
   while (rightpoint >= left && ary[rightpoint--] > base); //反之 
   System.out.println("左边需要交换的索引:" + (leftpoint-1)); 
   System.out.println("右边需要交换的索引:"+ (rightpoint+1)); 
   //上面拿到了不符合条件的两个索引，即需要交换的两个索引 
   if (leftpoint - 1 < rightpoint + 1) {//需要交换 
    swap(ary, leftpoint - 1, rightpoint + 1); 
    Util.printArray(ary); 
    leftpoint = left; 
    rightpoint = right; 
   } else { 
    break; 
   } 
  } 
 } 
  
 
 private static void swap(int[] ary, int a, int b) { 
  int temp = ary[a]; 
  ary[a] = ary[b]; 
  ary[b] = temp; 
 } 
 
 public static void main(String[] args) { 
  int[] ary = Util.generateIntArray(10); 
  System.out.println("原序列："); 
  Util.printArray(ary); 
  sort(ary, 5); 
  System.out.println("排序后："); 
  Util.printArray(ary); 
 } 
} 

原序列： 
[2, 8, 4, 3, 7, 5, 1, 9, 0, 6] 
左边需要交换的索引:1 
右边需要交换的索引:8 
[2, 0, 4, 3, 7, 5, 1, 9, 8, 6] 
左边需要交换的索引:4 
右边需要交换的索引:6 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 
左边需要交换的索引:5 
右边需要交换的索引:5 
排序后： 
[2, 0, 4, 3, 1, 5, 7, 9, 8, 6] 

public void qSort(int array[],int left,int right) 
 { 
  if(left < right){ 
 
   int key = array[left]; 
 
   int high = right; 
    
   int low = left+1; 
    
   while(true){ 
     
    while(low <= high && array[low] <= key) low++; 
 
    while(low <= high && array[high] >= key) high--; 
        
    if(low > high) 
     break; 
 
    swap(array,low,high); 
   } 
   swap(array,left,high); 
    
   printArray(array); 
 
   qSort(array,left,high-1); 
 
   qSort(array,high+1,right); 
  } 
 }