/**
 * 對指定的數(shù)組中索引從start到end之間的元素進行快速排序
 * 
 * @param array 指定的數(shù)組
 * @param start 需要快速排序的數(shù)組索引起點
 * @param end 需要快速排序的數(shù)組索引終點
 */
public static final void quickSort(int[] array, int start, int end) {
  // i相當于助手1的位置，j相當于助手2的位置
  int i = start, j = end;
  int pivot = array[i]; // 取第1個元素為基準元素
  int emptyIndex = i; // 表示空位的位置索引，默認為被取出的基準元素的位置
  // 如果需要排序的元素個數(shù)不止1個，就進入快速排序(只要i和j不同，就表明至少有2個數(shù)組元素需要排序)
  while (i < j) {
    // 助手2開始從右向左一個個地查找小于基準元素的元素
    while (i < j && pivot <= array[j])
      j--;
    if (i < j) {
      // 如果助手2在遇到助手1之前就找到了對應的元素，就將該元素給助手1的"空位"，j成了空位
      array[emptyIndex] = array[emptyIndex = j];
    }
    
    // 助手1開始從左向右一個個地查找大于基準元素的元素
    while (i < j && array[i] <= pivot)
      i++;
    if (i < j) {
      // 如果助手1在遇到助手2之前就找到了對應的元素，就將該元素給助手2的"空位"，i成了空位
      array[emptyIndex] = array[emptyIndex = i];
    }
  }    
  // 助手1和助手2相遇后會停止循環(huán)，將最初取出的基準值給最后的空位
  array[emptyIndex] = pivot;
  
  // =====本輪快速排序完成=====
  
  // 如果分割點i左側有2個以上的元素，遞歸調(diào)用繼續(xù)對其進行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割點j右側有2個以上的元素，遞歸調(diào)用繼續(xù)對其進行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}

//主方法
public static void main(String[] args) {
  // =====使用快速排序法對表示8名運動員身高的數(shù)組heights進行從低到高的排序=====
  // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
  int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
  // 調(diào)用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 輸出排序后的結果
  for (int height : heights) {
    System.out.println(height);
  }
}

163
169
172
181
182
187
189
191

int partition(int[] a, int lo, int hi) {
  int i = lo - 1, j = lo;
  int v = a[hi];
  while (j < hi) {
    if (a[j] <= v) {
      swap(a, ++i, j);
    }
    j++;
  }
  swap(a, i + 1, hi);
  return i + 1;
}