快速排序的時間復雜度為 O[nlog (n)]，空間復雜度是 O[log (n)] ，這種演算法應用比較廣泛（面試也愛考），非常適合在資料量較多且關鍵字隨機分布的情況下使用，
記得博主第一次學習冒泡排序時覺得，這個冒泡排序很easy啊，然后就去看冒泡排序改進版的代碼（也就是快速排序啦），然后，，，，
啊這 ，，，
相信應該也有一些小伙伴和我過類似的經歷吧，即使能讀懂代碼，卻有難以理解其流程，面試手撕時也難以快速應對，
不過后來，當我接觸到分治演算法后，再回過頭來這個快速排序的方法，，，，
就這？以后快排我不用提前準備，隨時手撕!
好啦，廢話不多說了，進入正題，
先說一說什么是分治演算法:
就如字面意思，我們需要把一個大的問題分解成多個形式相同的小問題解決，并且這些小問題的解的合并就是大問題的解，
這可能理解起來還是抽象的，我們就以排序舉例子：
假設我們的陣列有這樣九個數字： [ 5 8 9 6 7 4 1 2 3 ]
現在我們從陣列中隨便取一個數字（就去陣列中的第一個數字吧），以它為閾值，所有小于他數的放其左邊，并在邏輯上視為一個新的陣列（就叫小”陣列“吧），所有大于他的數放其右邊，同樣在邏輯上視為一個新的陣列（就叫大”陣列“吧），然后我們再對新出現的大陣列和小陣列進行同樣的操作直到新陣列的大小小于2時停止：
以第一個數字5為閾值進行拆分操作，分成 [ 小陣列 ] 閾值 [ 大陣列 ] ,如下：
[ 4 1 2 3 ] 5 [ 8 9 6 7 ] (在快速排序中小”陣列“其實會是[ 3 2 1 4 ],因為快排會從原陣列首尾的兩個指標向中間交替前進分大小，但這對我們這個例子并無影響)
[ 1 2 3 ] 4 [ ] 5 [ 6 7 ] 8 [ 9 ] 黃色部分是對[4 1 2 3]的拆分操作，綠色部分是對 [8 9 6 7]的拆分操作，紅色部分要么是當前操作的閾值要么是長度不足2的陣列，將不會參與后面的拆分操作
[ ] 1 [ 2 3 ] 4 [ ] 5 6 [ 7 ] 8 [ 9 ] 粉色部分是對[ 1 2 3 ]的拆分操作 ，淡藍色部分是對[ 6 7 ] 的拆分操作， 紅色部分要么是當前操作的閾值要么是長度不足2的陣列，將不會參與后面的拆分操作
[ ] 1 2 [ 3 ] 4 [ ] 5 6 [ 7 ] 8 [ 9 ] 深藍色部分是對‘[ 2 3 ]的拆分操作，紅色部分要么是當前拆分操作的閾值要么是長度不足2的陣列，將不會參與后面的拆分操作
現在你看，這個陣列是不是有序了，
這就有點像建立一個二叉搜索樹一樣，把一個陣列分成一個閥值（父節點）、一個小陣列（左子樹集合）和一個大陣列（右子樹集合），然后對兩個新的陣列（左、右子樹）遞回該操作，
當然，快排和這個流程還是有一點小區別的，當我們把一個“陣列”拆分成兩個新“陣列”時，上面的演示流程為了方便大家理解，不憑空增加復雜性，采用的是從左向右遍歷原陣列的每個元素，
如 [ 5 8 9 6 7 4 1 2 3 ] 操作后的小陣列順序是 [ 4 1 2 3 ]，但在快排中，對原陣列的遍歷不是這樣的，它是使用兩個指標從原陣列首尾開始向中間前進進行遍歷的（小伙伴可以在下面的代碼里體會），所以我才在上面的小括號里說快排中的小陣列順序是[ 3 2 1 4 ]，（即尾指標向中間前進，遇到小于閾值5的數字的順序 3 2 1 4 ），
最后，大家從分治的思想來看看下面的快排代碼，是不是就不覺得更好理解了呢？
1 import java.util.Arrays;
2
3 public class QuickSort {
4 public static void sort(int[] array,int begin_edge,int end_edge){
5 //左右邊界下標重合時，就表示邏輯上的新陣列大小不足2了，
6 // 故不再需要二分成兩個新“陣列”了
7 if(begin_edge>=end_edge){return;}
8 //獲取新“陣列”的首尾指標
9 int l_pointer = begin_edge;
10 int r_pointer = end_edge;
11 int threshold = array[l_pointer];
12 //回圈結束時，所有l_pointer左邊的元素會小于threshold，右邊的會大于threshold（有點二叉搜索樹的意思2333）
13 while (l_pointer<r_pointer){//跳出回圈時完成對當前“陣列”的二分
14 //尾指標向前遍歷，遇到小于閾值的數就跳出回圈，把它放進小“陣列”
15 while (l_pointer<r_pointer && array[r_pointer]>=threshold){
16 r_pointer--;
17 }
18 array[l_pointer] = array[r_pointer];
19 //首指標向后遍歷，遇到大于閾值的數就跳出回圈，把它放進大“陣列”
20 while (l_pointer<r_pointer && array[l_pointer]<=threshold) {
21 l_pointer++;
22 }
23 array[r_pointer] = array[l_pointer];
24 }
25 //把閾值插到兩個“陣列”的中間以區分兩個“陣列”的邊界（此時l_pointer等于r_pointer）
26 array[l_pointer] = threshold;
27 //遞回呼叫，分治思想，化大問題為形式相同的小問題
28 sort(array,begin_edge,l_pointer-1);
29 sort(array,l_pointer+1,end_edge);
30 }
31
32 public static void main(String[] args) {
33 int array[] = { 4, 2, 5, 1, 7, 3, 5, 9, 8,1 };
34 sort(array,0,array.length-1);
35 System.out.println(Arrays.toString(array));
36 }
37 }
測驗結果：
最后的最后，如果小伙伴覺得這篇博文對你有幫助的話，就長按??，，，，啊，呸，就點個推薦吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/14517.html
標籤：其他