圖文講解Java中實作quickSort快速排序演算法的方法

相對冒泡排序、選擇排序等演算法而言，快速排序的具體演算法原理及實作有一定的難度。為了更好地理解快速排序，我們仍然以舉例說明的形式來詳細描述快速排序的演算法原理。在前面的排序演算法中，我們以5位運動員的身高排序問題為例進行講解，為了更好地體現快速排序的特點，這裡我們再額外添加3名運動員。實例中8位運動員及其身高資料詳細如下(F、G、H為新增的運動員)： A(181)、B(169)、C(187)、D(172)、E(163)、 F(191)、G(189)、H(182)

在前面的排序演算法中，這些排序都是由教練主導完成了，現在運動員人數增加了，教練也想趁機去休息一下，於是教練叫來了兩位助手，讓這兩位助手以快速排序法的排序方式來實現8名運動員的身高從左到右、從低到高的排序。

依照快速排序法的演算法原理，兩名助手分別站在運動員排列的兩側，如下圖所示

首先，助手1從排列中選出一名運動員(一般選擇左側第1位運動員或最中間的運動員)，在此選擇運動員A(181)。由於排序是從左到右、從低到高，所以助手1需要一個身高比A(181)更小的運動員(選出來的A(181)作為比較的基準，本輪所有的比較，都是與最初選出來的運動員A(181)比較)：

下面我們來繼續參考快速排序第一輪的詳細示意圖。

當兩名助手在排序尋找的過程中相遇後，就停止當前輪次的比較，並把最初選出來的兩名運動員A(181)助手相遇的空位上

在快速排序中，當兩名助手相遇時，本輪排序就結束了。此時，我們發現，以兩位運動員相遇的位置A(181)作為分割點，排列左邊的都是身高比A(181)小的運動員，排列右側的都是身高比A(181)大的運動員。這時候，我們再把A(181)左側和右側的兩個排序分開來看，如果我們繼續使用上述兩名助手的排序方法分別對兩邊的排列進行排序，那麼經過多次排列後，最後就能夠得到我們所需要的排序結果。

上面就是快速排序的整個排序實作過程。快速排序就是利用上述的排序規則，將一個排列分成兩個排列，兩個排列分成四個排列，直到無排列可分為止，最後就得到了我們所需要的排序結果。

現在，我們依然編程Java代碼來實現使用快速排序對上述8名運動員的身高進行排序：

/**
 * 对指定的数组中索引从start到end之间的元素进行快速排序
 * 
 * @param array 指定的数组
 * @param start 需要快速排序的数组索引起点
 * @param end 需要快速排序的数组索引终点
 */
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; // 表示空位的位置索引，默认为被取出的基准元素的位置
  // 如果需要排序的元素个数不止1个，就进入快速排序(只要i和j不同，就表明至少有2个数组元素需要排序)
  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相遇后会停止循环，将最初取出的基准值给最后的空位
  array[emptyIndex] = pivot;
   
  // =====本轮快速排序完成=====
   
  // 如果分割点i左侧有2个以上的元素，递归调用继续对其进行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割点j右侧有2个以上的元素，递归调用继续对其进行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}
 
//主方法
public static void main(String[] args) {
  // =====使用快速排序法对表示8名运动员身高的数组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 };
  // 调用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 输出排序后的结果
  for (int height : heights) {
    System.out.println(height);
  }
}

以上Java代碼運行結果輸出如下：

163
169
172
181
182
187
189
191

注意：由於局部思維差異，上述快速排序的代碼實作可能存在多種變體。不過，無論何種形式的變體，快速排序的核心思想並不會改變。

另一種實現：單向掃描
快速排序的數組切分還有另一種單向掃描的版本，具體步驟是選擇數組中最後一個元素作為切分元素，同樣設置兩個指針，指針i指向數組中第一個元素前面一個位置，j則指向數組中第一個元素。 j從前左右往右掃描，遇到小於等於切分元素時就把i加一，然後交換i和j指向的元素。最後把i+1位置的元素和切分元素交換即可完成一次陣列劃分。程式碼實作如下：

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;
}

更多圖文講解Java中實作quickSort快速排序演算法的方法相關文章請關注PHP中文網！