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

//主方法
public static void main(String[] args) {
  // =====使用快速排序法對(duì)表示8名運(yùn)動(dòng)員身高的數(shù)組heights進(jìn)行從低到高的排序=====
  // 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);
  // 輸出排序后的結(jié)果
  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;
}