基本思想

已發布：

【算法知識】詳解選擇冒泡算法

【算法知識】詳解選擇排序算法

【算法知識】詳解插入排序算法

本文的思路是以從小到大為例講的。
快速排序的基本思想是任取待排序序列的一個元素作為中心元素(可以用第一個，最后一個，也可以是中間任何一個)，習慣將其稱為pivot，樞軸元素；
將所有比樞軸元素小的放在其左邊；
將所有比它大的放在其右邊；
形成左右兩個子表；
然后對左右兩個子表再按照前面的算法進行排序，直到每個子表的元素只剩下一個。

可見快速排序用到了分而治之的思想。
將一個數組分成兩個數組的方法為：
先從數組右邊找到一個比樞軸元素小的元素，將數組的第一個位置賦值為該元素；
再從數組的左邊找到一個比樞軸元素大的元素，將從上面取元素的位置賦值為該值；
依次進行，直到左右相遇，把樞軸元素賦值到相遇位置。

例子

輸入數組
arr 為 [39 , 28 ?, 55 , ?87 , 66 , 3 ,17 ,39*]
為了區別兩個相同元素，將最后一個加上 * ；
初始狀態如下圖：

初始狀態

定義一樞軸元素pivot，初始化為第一個元素的值，即39；
查詢左邊的元素的變量為left，初始值為第一個元素的索引,0;
查詢右邊的元素的變量為right，初始值為第一個元素的索引,7。
如下圖：

初始化

演示第一輪排序過程
從右邊開始，從右邊找到一個比樞軸元素小的，如果沒找到right一直自減1；

第一輪排序狀態1

然后把當前left所在元素賦值為該值；
這里right所指元素并沒有空，只是為了好演示，設置為空（下同）；

第一輪排序狀態2

然后從左邊開始找一個比樞軸元素pivot大的元素；如果沒找到left一直自增1；

第一輪排序狀態3

將當前right所指元素設為該值；

第一輪排序狀態4

然后從右邊找到一個比樞軸元素小的，如果沒找到right一直自減1；

第一輪排序狀態5

將當前left所指元素設為該值；

第一輪排序狀態6

然后從左邊開始找一個比樞軸元素pivot大的元素；如果沒找到left一直自增1；

第一輪排序狀態7

將當前right所指元素設為該值；

第一輪排序狀態8

然后從右邊找到一個比樞軸元素小的，如果沒找到right一直自減1；

第一輪排序狀態9

這時left和right相遇了，將樞軸元素賦值給當前位置。

第一輪排序狀態10

第一輪排序動態過程：

第一輪排序動態過程

然后將數組分成了

[17,28,3] ?與 ?[66, 87, 55, 39*]兩部分；
再對這兩部分進行上述環節即可。
反反復復，直到只剩下一個元素。

排序全過程

排序全過程

代碼

對每一個數組進行分化的代碼如下：
初始化pivot為數組第一個元素；
只要left還小于right就進行循環；
外層循環內部如下：
先從右邊找一個比樞軸元素小的元素；
將當前left所指元素賦值為找到的元素；
再從左邊找一個比樞軸元素大的元素；
將當前right所指元素賦值為找到的元素；
當left和right相等將樞軸元素賦值在此。
最后返回中間元素的索引。

public?static?int?partition(int[]?arr,int?left,int?right){int?pivot?=?arr[left];while(left?<?right){while(left<right?&&?arr[right]?>=?pivot)right--;arr[left]?=?arr[right];while(left?<?right?&&?arr[left]<=?pivot)left++;arr[right]?=?arr[left];}arr[left]?=?pivot;return?left;}

快排代碼：
第一個是快排的重載，直接傳數組；
然后調用另一個重載函數，傳數組，left為第一個元素索引0，right為最后一個元素索引數組長度減去1；
主要介紹傳三個參數的快排函數：
定義一個將來劃分為兩個數組的中間元素的索引；
如果left比right小，進行一次劃分，將返回來的值賦值給middle；
對left到middle - 1的部分進行一次快排（遞歸進行）；
對middle + 1到right的部分進行一次快排（遞歸進行）。

public?static?void?quickSort(int[]?arr){quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}public?static?void?quickSort(int[]?arr,int?left,int?right){int?middle;if(left?<?right){middle?=?partition(arr,left,right);quickSort(arr,left,middle-1);quickSort(arr,middle+1,right);}}

完整代碼:

import?java.util.Arrays;public?class?Solution?{public?static?void?main(String[]?args)?{quickSort(new?int[]{39,28,55,87,66,3,17,39});}public?static?void?quickSort(int[]?arr){quickSort(arr,0,arr.length-1);System.out.println(Arrays.toString(arr));}public?static?void?quickSort(int[]?arr,int?left,int?right){int?middle;if(left?<?right){middle?=?partition(arr,left,right);quickSort(arr,left,middle-1);quickSort(arr,middle+1,right);}}public?static?int?partition(int[]?arr,int?left,int?right){int?pivot?=?arr[left];while(left?<?right){while(left<right?&&?arr[right]?>=?pivot)right--;arr[left]?=?arr[right];while(left?<?right?&&?arr[left]<=?pivot)left++;arr[right]?=?arr[left];}arr[left]?=?pivot;return?left;} }

時間復雜度

理想的情況：
每次劃分所選擇的中軸元素恰好將當前序列幾乎等分，經過趟劃分，便可以排序完畢。這樣，所以理想狀態下整個算法的時間復雜度為。
最壞的情況是，每次所選的中間數是當前序列中的最值元素，這時每次劃分的兩個子表一個長度是0，一個是當前數組長度減去1。這樣的話，長度為n的數組需要經過n趟劃分，這時的時間復雜度為；
為改善最壞情況下的時間性能，可以在最樞軸元素的原則中進行優化，選第一個元素，最后一個元素，中間元素中的中位數即可。
這時，快速排序的時間復雜度即為。

穩定性

如下面的數組
相同元素用 * ?標出 [ 2 , 3 ?, 1, 1* ]
第一次排序為
[1* , 1, 2, 3]
第二次為
[1* , 1 , 2 , 3] 相對順序發生了變化，所以是不穩定的。

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習在線手冊深度學習在線手冊AI基礎下載（pdf更新到25集）本站qq群1003271085，加入微信群請回復“加群”獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的【算法知识】详解快速排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。