圖文講授Java中完成quickSort疾速排序算法的辦法。本站提示廣大學習愛好者：（圖文講授Java中完成quickSort疾速排序算法的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是圖文講授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;
}
