快速排序详解

package com.sort;
/**
* 2010-10-18
* 快速排序
* 1。取中值
* 2。按照中值将数组进行分组（不是分的越细越好）
* 3。将分组后的数据再进行分组.........
*/
public class QuickSort {

  public void sort(int[] arr,int leftIndex,int rightIndex){
    
    //确定中值（假定中值为数组中间的数）
    int pivot=(leftIndex+rightIndex)/2;
    
    //为了便于排序，把pivot放到数组最后一个位置上    结果是rightIndex所在的位置是中值
    swap(arr,pivot,rightIndex);
    
    /*
     * 将数组分成小于、大于中值的两个部分
     * 小于中值的部分在左侧
     * 大于中值的部分在右侧
     * key是大于中值那部分的第一个元素的下标
     */
    int key=partiton(arr,leftIndex-1,rightIndex,arr[rightIndex]);     //之所以是arr[rightIndex]而不是arr[pivot]是因为前面交换位置了
    /*
     * 将中值（rightIndex位置上的）与大于中值那部分的第一个元素交换，以保证中值的左侧都小于中值，右侧都大于中值
     */
    swap(arr,key,rightIndex);
    
    //以中值为界，对中值的左右部分再次划分
    
    /*
     * 如果左侧的长度大于1个元素可以继续进行划分
     */
    if((key-leftIndex)>1){
      
      /*
        * 将中值左侧的继续进行划分，之所以不包括中值（key)是因为中值的位置已经确定无需参与比较
        * 中值左侧的都小于中值，中值右侧的都大于中值
        */
      sort(arr,leftIndex,key-1);
    }
    
    /*
     * 如果右侧的长度大于1个元素可以继续进行划分
     */
    if((rightIndex-key)>1){
      
      sort(arr,key+1,rightIndex);
    }
    
    
  }
  
  /**
    *
    * @param arr                目标数组
    * @param leftIndex    数组最左侧的元素下标
    * @param rightIndex 数组最右侧的元素下标
    * @param pivot            中值
    * @return                     大于中值的第一个元素的下标（用来和中值进行交换|||||||非常重要）
    */
  private int partiton(int[] arr, int leftIndex, int rightIndex,int pivot) {
    
    do{
      /*
        * leftIndex 保存的是从左侧开始依次每个元素的下标
        * 当arr[++leftIndex]不再小于中值（pivot）
        * 即左侧出现大于中值的元素时，则跳出循环
        * 此时leftIndex保存的下标就是大于中值的那个元素的下标
        *
        */
      while(arr[++leftIndex]<pivot){
        //无执行体 因为条件本身就是执行体
      }
      
      /*
        * rightIndex 保存的是从右侧开始的依次每个元素的下标
        * 当arr[--rightIndex]不再大于中值（pivot）
        * 即右侧出现小于中值的元素时，则跳出循环
        * 此时rightIndex保存的下标就是小于中值的那个元素的下标
        *
        */
      while((rightIndex!=0)&&arr[--rightIndex]>pivot){
        //无执行体 因为条件本身就是执行体
      }
      
      swap(arr,leftIndex,rightIndex);
      
    }
    //如果所有元素都与中值比较过则跳出循环（即左侧下标leftIndex和右侧rightIndex相交时）
    while(leftIndex<rightIndex);
    
      swap(arr,leftIndex,rightIndex);
      
      return leftIndex;
  }

  private void swap(int[] arr, int i, int j) {

    int temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }

  public static void main(String[] args) {
    
    int arr[]={23,2,45,34,65,9,78,100};
    QuickSort sort=new QuickSort();
    sort.sort(arr, 0, arr.length-1);
    System.out.println("排序结果是"+java.util.Arrays.toString(arr));
  }

}