package com.eruite.test;

public class QuickSort {
 /**
  * 快速排序
  *
  * @param arr
  * @param left
  * @param right
  */
 public void quickSort(int[] arr, int left, int right) {
  int middle, temp;
  int i, j;
  i = left;
  j = right;
  middle = arr[(i + j) / 2];
  do {
   // 找出左边比中间值大的数
   while (arr[i] < middle && i < right)
    i++;
   // 找出右边比中间值小的数
   while (arr[j] > middle && j > left)
    j--;
   // 将左边大的数和右边小的数进行替换
   if (i <= j) {
    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++;
    j--;
   }
  } while (i <= j); // 当两者交错时停止

  if (i < right) {
   quickSort(arr, i, right);// 从右边进行递归
  }
  if (j > left) {
   quickSort(arr, left, j);// 从左边进行递归
  }
 }

 /**
  * @param args
  */
 public static void main(String[] args) {
  int[] arr = { 11, 66, 22, 0, 55, 22, 0, 32 };
  QuickSort sort = new QuickSort();
  sort.quickSort(arr, 0, arr.length - 1);
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }
}