欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

圖文講解Java中實(shí)現(xiàn)quickSort快速排序算法的方法

 更新時間:2016年05月04日 16:22:51   作者:飛翔的貓咪  
這篇文章主要介紹了Java中實(shí)現(xiàn)quickSort快速排序算法的方法,文章最后還介紹了一種單向掃描的實(shí)現(xiàn)方法,需要的朋友可以參考下

相對冒泡排序、選擇排序等算法而言,快速排序的具體算法原理及實(shí)現(xiàn)有一定的難度。為了更好地理解快速排序,我們?nèi)匀灰耘e例說明的形式來詳細(xì)描述快速排序的算法原理。在前面的排序算法中,我們以5名運(yùn)動員的身高排序問題為例進(jìn)行講解,為了更好地體現(xiàn)快速排序的特點(diǎn),這里我們再額外添加3名運(yùn)動員。實(shí)例中的8名運(yùn)動員及其身高信息詳細(xì)如下(F、G、H為新增的運(yùn)動員): A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)

在前面的排序算法中,這些排序都是由教練主導(dǎo)完成了,現(xiàn)在運(yùn)動員人數(shù)增加了,教練也想趁機(jī)去休息一下,于是教練叫來了兩名助手,讓這兩名助手以快速排序法的排序方式來實(shí)現(xiàn)對8名運(yùn)動員的身高從左到右、從低到高的排序。

按照快速排序法的算法原理,兩名助手分別站在運(yùn)動員排列的兩側(cè),如下圖所示:

201654161611529.png (587×80)

首先,助手1從排列中選出一名運(yùn)動員(一般選擇左側(cè)第1位運(yùn)動員或最中間的運(yùn)動員),這里選擇運(yùn)動員A(181)。由于排序是從左到右、從低到高,所以助手1需要一個身高比A(181)更小的運(yùn)動員(選出來的A(181)作為比較的基準(zhǔn),本輪所有的比較,都是與最初選出來的運(yùn)動員A(181)比較):

201654161640234.png (665×171)

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

201654161656734.png (639×142)

201654161713046.png (646×151)

201654161739235.png (639×152)

201654161755999.png (625×147)

201654161810165.png (650×138)

201654161825241.png (640×135)

201654161844120.png (688×131)

當(dāng)兩名助手在排序?qū)ふ业倪^程中相遇后,就停止當(dāng)前輪次的比較,并把最初選出來的運(yùn)動員A(181)放在兩名助手相遇的空位上:

201654161859313.png (633×82)

在快速排序中,當(dāng)兩名助手相遇時,本輪排序就結(jié)束了。此時,我們發(fā)現(xiàn),以兩名運(yùn)動員相遇的位置A(181)作為分割點(diǎn),排列左邊的都是身高比A(181)小的運(yùn)動員,排列右側(cè)的都是身高比A(181)大的運(yùn)動員。這個時候,我們再把A(181)左側(cè)和右側(cè)的兩個排序分開來看,如果我們繼續(xù)使用上述兩名助手的排序方法分別對兩邊的排列進(jìn)行排序,那么經(jīng)過多次排列后,最后就能夠得到我們所需要的排序結(jié)果。

上面就是快速排序的整個排序?qū)崿F(xiàn)過程??焖倥判蚓褪抢蒙鲜龅呐判蛞?guī)則,將一個排列分為兩個排列,兩個排列分為四個排列,直到無排列可分為止,最后就得到了我們所需要的排序結(jié)果。

現(xiàn)在,我們依然編程Java代碼來實(shí)現(xiàn)使用快速排序?qū)ι鲜?名運(yùn)動員的身高進(jìn)行排序:

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

//主方法
public static void main(String[] args) {
  // =====使用快速排序法對表示8名運(yùn)動員身高的數(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);
  }
}

以上Java代碼運(yùn)行結(jié)果輸出如下:

163
169
172
181
182
187
189
191

注意:由于局部思維差異,上述快速排序的代碼實(shí)現(xiàn)可能存在多種變體。不過,無論何種形式的變體,快速排序的核心思想并不會發(fā)生改變。

另一種實(shí)現(xiàn):單向掃描
快速排序的數(shù)組切分還有另一種單向掃描的版本,具體步驟是選擇數(shù)組中最后一個元素作為切分元素,同樣設(shè)置兩個指針,指針i指向數(shù)組中第一個元素前面一個位置,j則指向數(shù)組中第一個元素。j從前左右往右掃描,遇到小于等于切分元素時就把i加一,然后交換i和j指向的元素。最后把i+1位置的元素和切分元素交換即可完成一次數(shù)組劃分。代碼實(shí)現(xiàn)如下:

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

相關(guān)文章

最新評論