圖文講解Java中實(shí)現(xiàn)quickSort快速排序算法的方法
相對冒泡排序、選擇排序等算法而言,快速排序的具體算法原理及實(shí)現(xiàn)有一定的難度。為了更好地理解快速排序,我們?nèi)匀灰耘e例說明的形式來詳細(xì)描述快速排序的算法原理。在前面的排序算法中,我們以5名運(yùn)動(dòng)員的身高排序問題為例進(jìn)行講解,為了更好地體現(xiàn)快速排序的特點(diǎn),這里我們再額外添加3名運(yùn)動(dòng)員。實(shí)例中的8名運(yùn)動(dòng)員及其身高信息詳細(xì)如下(F、G、H為新增的運(yùn)動(dòng)員): A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
在前面的排序算法中,這些排序都是由教練主導(dǎo)完成了,現(xiàn)在運(yùn)動(dòng)員人數(shù)增加了,教練也想趁機(jī)去休息一下,于是教練叫來了兩名助手,讓這兩名助手以快速排序法的排序方式來實(shí)現(xiàn)對8名運(yùn)動(dòng)員的身高從左到右、從低到高的排序。
按照快速排序法的算法原理,兩名助手分別站在運(yùn)動(dòng)員排列的兩側(cè),如下圖所示:
首先,助手1從排列中選出一名運(yùn)動(dòng)員(一般選擇左側(cè)第1位運(yùn)動(dòng)員或最中間的運(yùn)動(dòng)員),這里選擇運(yùn)動(dòng)員A(181)。由于排序是從左到右、從低到高,所以助手1需要一個(gè)身高比A(181)更小的運(yùn)動(dòng)員(選出來的A(181)作為比較的基準(zhǔn),本輪所有的比較,都是與最初選出來的運(yùn)動(dòng)員A(181)比較):
下面我們來繼續(xù)參考快速排序第一輪的詳細(xì)示意圖。
當(dāng)兩名助手在排序?qū)ふ业倪^程中相遇后,就停止當(dāng)前輪次的比較,并把最初選出來的運(yùn)動(dòng)員A(181)放在兩名助手相遇的空位上:
在快速排序中,當(dāng)兩名助手相遇時(shí),本輪排序就結(jié)束了。此時(shí),我們發(fā)現(xiàn),以兩名運(yùn)動(dòng)員相遇的位置A(181)作為分割點(diǎn),排列左邊的都是身高比A(181)小的運(yùn)動(dòng)員,排列右側(cè)的都是身高比A(181)大的運(yùn)動(dòng)員。這個(gè)時(shí)候,我們再把A(181)左側(cè)和右側(cè)的兩個(gè)排序分開來看,如果我們繼續(xù)使用上述兩名助手的排序方法分別對兩邊的排列進(jìn)行排序,那么經(jīng)過多次排列后,最后就能夠得到我們所需要的排序結(jié)果。
上面就是快速排序的整個(gè)排序?qū)崿F(xiàn)過程??焖倥判蚓褪抢蒙鲜龅呐判蛞?guī)則,將一個(gè)排列分為兩個(gè)排列,兩個(gè)排列分為四個(gè)排列,直到無排列可分為止,最后就得到了我們所需要的排序結(jié)果。
現(xiàn)在,我們依然編程Java代碼來實(shí)現(xiàn)使用快速排序?qū)ι鲜?名運(yùn)動(dòng)員的身高進(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個(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之前就找到了對應(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之前就找到了對應(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ù)對其進(jìn)行快速排序 if (i - start > 1) { quickSort(array, 0, i - 1); } // 如果分割點(diǎn)j右側(cè)有2個(gè)以上的元素,遞歸調(diào)用繼續(xù)對其進(jìn)行快速排序 if (end - j > 1) { quickSort(array, j + 1, end); } } //主方法 public static void main(String[] args) { // =====使用快速排序法對表示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); } }
以上Java代碼運(yùn)行結(jié)果輸出如下:
163 169 172 181 182 187 189 191
注意:由于局部思維差異,上述快速排序的代碼實(shí)現(xiàn)可能存在多種變體。不過,無論何種形式的變體,快速排序的核心思想并不會(huì)發(fā)生改變。
另一種實(shí)現(xiàn):單向掃描
快速排序的數(shù)組切分還有另一種單向掃描的版本,具體步驟是選擇數(shù)組中最后一個(gè)元素作為切分元素,同樣設(shè)置兩個(gè)指針,指針i指向數(shù)組中第一個(gè)元素前面一個(gè)位置,j則指向數(shù)組中第一個(gè)元素。j從前左右往右掃描,遇到小于等于切分元素時(shí)就把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)文章
Java使用Iterator迭代器遍歷集合數(shù)據(jù)的方法小結(jié)
這篇文章主要介紹了Java使用Iterator迭代器遍歷集合數(shù)據(jù)的方法,結(jié)合實(shí)例形式分析了java迭代器進(jìn)行集合數(shù)據(jù)遍歷的常見操作技巧,需要的朋友可以參考下2019-11-11Java和scala實(shí)現(xiàn) Spark RDD轉(zhuǎn)換成DataFrame的兩種方法小結(jié)
今天小編就為大家分享一篇Java和scala實(shí)現(xiàn) Spark RDD轉(zhuǎn)換成DataFrame的兩種方法小結(jié),具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-06-06springBoot詳細(xì)講解使用mybaties案例
MyBatis本是apache的一個(gè)開源項(xiàng)目iBatis,2010年這個(gè)項(xiàng)目由apache software foundation遷移到了google code,并且改名為MyBatis。2013年11月遷移到Github。iBATIS一詞來源于“internet”和“abatis”的組合,是一個(gè)基于Java的持久層框架2022-05-05Java如何基于ProcessBuilder類調(diào)用外部程序
這篇文章主要介紹了Java如何基于ProcessBuilder類調(diào)用外部程序,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-01-01SpringBoot+Mybatis項(xiàng)目使用Redis做Mybatis的二級緩存的方法
本篇文章主要介紹了SpringBoot+Mybatis項(xiàng)目使用Redis做Mybatis的二級緩存的方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-12-12Java操作Mongodb數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)的增刪查改功能示例
這篇文章主要介紹了Java操作Mongodb數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)的增刪查改功能,結(jié)合完整實(shí)例形式分析了java針對MongoDB數(shù)據(jù)庫的連接、增刪改查等相關(guān)操作技巧,需要的朋友可以參考下2017-08-08SpringBoot集成SSM、Dubbo、Redis、JSP的案例小結(jié)及思路講解
這個(gè)案例其實(shí)就是SpringBoot集成SSM、Dubbo、Redis、JSP,看起來感覺很繁瑣,其實(shí)就是很簡單,下面通過案例分析給大家講解,感興趣的朋友跟隨小編一起看看吧2021-05-05