快排，和冒泡排序一樣，是同一類型的排序，都是交換排序

交換，涉及在遍歷中比較，然后相互交換元素

冒泡排序是根據(jù)趟數(shù)兩兩比較，邊比較邊交換，快排也一樣，不過冒泡是以順序表的格式進(jìn)行的，而快排則是建立在二叉樹的基礎(chǔ)上來完成遍歷交換的~（個人理解）

快排有很多個版本，快速排序是一位名hoare的人發(fā)明的，快排有很多個版本，什么horae版本，什么挖坑法，什么雙指針法，這里我們介紹horae版本，至于挖坑法和雙指針以后有機(jī)會再說~

---

已經(jīng)說了，快排基于二叉樹的規(guī)則來進(jìn)行排序，那么具體是怎么樣的呢？

比如說我們先搞一個無序數(shù)組，然后定義left和right分別是數(shù)組的頭尾下標(biāo)

然后定義一個基準(zhǔn)值? key? 這個key? 是用來劃分?jǐn)?shù)組的，當(dāng)遍歷交換完一次后，key下標(biāo)所對應(yīng)的值會在這個數(shù)組的某個位置，但是key左邊的元素都會比key下標(biāo)對應(yīng)的元素小，key左邊的元素都會比key下標(biāo)對應(yīng)的元素值要大，這就很類似于二分查找的時候的劃分一樣~

那具體是怎么樣遍歷和劃分的呢？下面讓老衲給你畫張圖即可

?

?下面我來解說一下第一輪的過程，首先給出了一個無序數(shù)組，把6設(shè)置為基準(zhǔn)，然后存一份，接著right開始減減，遇到比6小的就停下來，所以right先減到了3后，停下不動，此時3比6這個基準(zhǔn)小，然后right不動了，開始輪到left++，left的目的是尋找比基準(zhǔn)6大的值，所以left++到了7，就停下，此時left對應(yīng)的7比基準(zhǔn)6大，接著把right的3和left的7開始交換，交換后left對應(yīng)3，right對應(yīng)7，接著right接著開始往下減減，尋找比基準(zhǔn)6小的值，當(dāng)減到4的時候right停止不動，然后接left開始++，尋找比6大的值，一直++到right，沒有再比6大值，并且此時left和right相遇，暗示著第一輪循環(huán)結(jié)束，此時left和right相遇后，把它們相遇下標(biāo)的值，也就是4，開始和最開始的基準(zhǔn)，也就是下標(biāo)為0的值，也就是6，開始交換：完成交換后，你會發(fā)現(xiàn)此時6的左邊都是比6小的數(shù)，6的右邊都是比6大的數(shù)，接著根據(jù)6所在的位置，開始劃分成兩部分，一部分比6小，一部分比6大

劃分好后，我們現(xiàn)在只看比6小的部分，比6大的部分同理，看懂比6小的部分就行了

劃分后，我們看比6小的 把它當(dāng)做一個新數(shù)組? 值 為? 4? ?2? ?3?

然后根據(jù)上面的過程再來一遍，我們把這個數(shù)組的0下標(biāo)元素4看作基準(zhǔn)值，然后right對應(yīng)3，我們開始right--，我們發(fā)現(xiàn)此時right的3就是比4小的，所以不動，接著left開始++，找比4大的，一直++到3，沒發(fā)現(xiàn)比4大的，此時left和right又相遇了，接著再次劃分，只有比4小的部分，沒有比4大的部分了，那么我們就劃分出比4小的部分

劃分出3? 2? 后，我們按照剛才的過程再來一遍，把3看作基準(zhǔn)，right--找比3小的，left++找比3大的，直到left和right再次相遇，然后再劃分

一直到最后只剩下一個節(jié)點(diǎn)2的時候，就完成了遍歷，接著返回，沒錯，就是遞歸的返回，所以快排要基于二叉樹加上遞歸來實(shí)現(xiàn)，嘻嘻~~~

---

下面展示代碼，再說說細(xì)節(jié)~

public class 快排 {public static void main(String[] args) {int[] arr = {3,5,2,1,43,33,22,64,74,25,13,27,98,56,100,21,7};quickSort(arr);for(int x : arr){System.out.print(x + " ");}}public static void quickSort(int[] array){quick(array,0,array.length-1);}private static void quick(int[] array, int left, int right) {//遞歸結(jié)束條件:這里代表只有一個根 大于號：有可能沒有子樹 1 2 3 4 1為基準(zhǔn)，pivot-1就越界了if(left >= right){return;}int pivot = partition(array, left, right);quick(array,left,pivot-1);quick(array,pivot+1,right);}public static int partition(int[] array,int start, int end){int i = start;//這里存開始時基準(zhǔn)的下標(biāo)，為了循環(huán)結(jié)束后，相遇值和基準(zhǔn)值交換時能找到基準(zhǔn)值的下標(biāo)int key = array[start];//這是基準(zhǔn)while (start < end){while (start < end && array[end] >= key){end--;}while (start < end && array[start] <= key){start++;}swap(array,start,end);}//到這里s和e相遇，把相遇值和基準(zhǔn)值交換swap(array,start,i);return start;//返回基準(zhǔn)下標(biāo)}public static void swap(int[] array, int n, int m){int temp = array[n];array[n] = array[m];array[m] = temp;}}

寫快排就3個主要方法，一個是交換swap，一個是找基準(zhǔn)partition，一個是遞歸過程quick方法，遞歸直到left >= right 的時候返回~

---

第一個方法quick是遞歸用的，主要是劃分?jǐn)?shù)組的功能，返回條件是left >= right

假如你的數(shù)組是1 2 3 4的話，我們讓第一個元素為基準(zhǔn)，如果要劃分的話，只能劃分比1大的部分，方法里面又會自動劃分比1小的部分，也就是基準(zhǔn)下標(biāo)減一，那么就越界了

---

為什么要right先動，而不是left先動，那是因?yàn)槲覀円詌eft為基準(zhǔn)，如果left先動，劃分好后，你會發(fā)現(xiàn)基準(zhǔn)左邊的值存在比基準(zhǔn)大的值，而我們的策略是基準(zhǔn)左邊比基準(zhǔn)小，基準(zhǔn)右邊比基準(zhǔn)大~

---

partition方法里面有一個大while包含著兩個小while，小while是獨(dú)立的while，

所以要加上start < end

同時&&后面的array【end】 >= key, 為什么要是等于呢？如果不等于，假如你的數(shù)組頭和尾相同

比如說? ?3? 7 5? 8? 4? ?3，就會出現(xiàn)死循環(huán)了，3不大于3，而是等于3~

---

ok到這里就結(jié)束戰(zhàn)斗了，老衲要去睡覺了~

總結(jié)

以上是生活随笔為你收集整理的【JAVA】快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。