手撸快速排序 -- java 排序算法之快速排序(左右指针法)

基本思路：

1．将数组的第一作为基准数 stone 。
2．以 stone 进行分组，左边要小于或等于 stone ; 右边大于或等于 stone ; 

例：[12, 21, 3, 5, 2, 18]  以 12 为 stone  low = 0 ; hi = array.length-1;

分组过程:

记录　stone  index

int oldIndex = low;　

hi 开始向前找比 stone 大的的数（hi 找大最后大的全移右边），循环找 比 low< hi，由右向左找  stone 值 和rray[hi]比较，找不到hi- -找到,退出循环；

while(low<hi&&rray[hi] >= stone)
{
    hi--
}

从数组的首元素 low 开始向后找比 stone 的数（low 找小，小的最后全移左边），循环找low <hi，由左向右，low++ 找到,退出循环；

while(low<hi&&rray[low] <= stone)
{
    low++
}

找到后然后两者交换（swap）,

if(low<hi)
{
    array[low],arry[hi],交换
}

再循环，直到 low<hi终止；最后判断，if(low==hi)  移 stone 到正确位置，完成分组，以stone 划分 左边小，右边大；

if(low==hi)
{
   array[oldInde ], array[low] 交换
}

记下当前 divideIndex ;
3．再对左组小值组,递归 hi = divideIndex -1; 右值组 递归 low = divideIndex +1，直到各区间只有一个数。

快速排序之左右指针排序前:[12, 21, 3, 5, 2, 18]
left ,right swap low:1 hi:4 array:[12, 2, 3, 5, 21, 18]
stone Index :0 divideIndex:3 move stone swap :[5, 2, 3, 12, 21, 18]
stone Index :0 divideIndex:2 move stone swap :[3, 2, 5, 12, 21, 18]
stone Index :0 divideIndex:1 move stone swap :[2, 3, 5, 12, 21, 18]
stone Index :4 divideIndex:5 move stone swap :[2, 3, 5, 12, 18, 21]
快速排序之左右指针排序后:[2, 3, 5, 12, 18, 21]

 

import java.util.Arrays;

/**
 * 第次以 array[low ] 为 stone 划分两部分，最后记得把 stone 放到中间位置；递归，最后可得到结果；
 * 
 * @author jacli
 * 
 */

public class quickSort {

  public static void swap(int[] array, int low, int hi) {
    int tmp = array[low];
    array[low] = array[hi];
    array[hi] = tmp;
  }

  public static int getDivideIndex(int[] array, int low, int hi) {
    int stoneValue = array[low];
    // save stone index 最后记得把 stone 放到中间位置
    int oldStoneIndex = low;
    while (low < hi) {
      // first hi

      // hi 从右向左移，如果 值小于 stone hi ++ ；如果大于去和左边low互换，小值 最后全跑左边
      while (low < hi && array[hi] >= stoneValue) {
        hi--;
      }

      // low 从左向右移，如果 值小于 stone hi ++ ；如果大于去和左边low互换，小值 最后全跑左边
      while (low < hi && array[low] <= stoneValue) {
        low++;
      }
      // 互换 low,hi 值，小值跑左边，大值跑右边；
      if (low < hi) {
        swap(array, low, hi);
        System.out.println("left ,right swap low:" + low + " hi:" + hi
            + " array:" + Arrays.toString(array));
      }
    }
    // 最后把 stone 移到相应位置
    if (low == hi) {
      swap(array, oldStoneIndex, hi);
      System.out.println("stone Index :" + oldStoneIndex
          + " divideIndex:" + hi+ " move stone swap :"
          + Arrays.toString(array));
    }

    return low;
  }

  public static void quickSort(int[] array, int low, int hi) {
    if (low < hi) {
      // array[low] get divideIndex divice two part;
      int divideIndex = getDivideIndex(array, low, hi);
      // 由 stone 分两部分，左边小值，右边大值
      // 继续递归
      quickSort(array, low, divideIndex - 1);
      quickSort(array, divideIndex + 1, hi);

    }
  }

  public static void main(String[] args) {

    int[] arrays = { 12, 21, 3, 5, 2, 18 };

    System.out.println("快速排序之左右指针排序前:" + Arrays.toString(arrays));
    quickSort(arrays, 0, arrays.length - 1);
    System.out.println("快速排序之左右指针排序后:" + Arrays.toString(arrays));
  }

}