一、步驟（從小到大排序）

1、在數組中選一個基準數（通常為數組第一個）。

2、將所有比基準值小的值擺放在基準的前面，所有比基準值大的擺放在基準的後面（相同的數可以放到任意一邊）;在這個分區推出之後，該基準就處於數列的中間位置。

3、遞歸地把「基準值前面的子數列」和「基準值後面的子數列」進行排序。

下面以數列a=[30,40,10,20,50]為例，演示它的快速排序過程：

上圖只是給出了第一趟快速排序的流程。在第一趟中，設置x=a[i],即x=30.

(01)從「右-->左」查找小於x的數；找到滿足條件的數a[j]=20,此時j=4;然後將a[j]賦值a[i],此時i=0;接著從左往右遍歷。

(02)從「左-->右」查找大於x的數；找到滿足條件的數a[i]=40,此時i=1；然後將a[i]賦值a[j],此時j=4;接著從右往左遍歷。

(03)從「右-->左」查找小於x的數；找到滿足條件的數a[j]=10,此時j=3；然後將a[j]賦值a[i],此時i=1;接著從左往右遍歷。

(04)從「左-->右」查找大於x的數；找到滿足條件的數a[i]=60,此時i=2；然後將a[i]賦值a[j],此時j=3;接著從右往左遍歷。

(05)從「右-->左」查找小於x的數；沒有找滿足條件的數。當i>=j時，停止查找；然後將x賦值給a[i]。此趟遍歷結束！

(06)安裝同樣的方法，對子數列進行遞歸遍歷。最後得到有序數組。

二、快速排序的時間複雜度和穩定性

快速排序穩定性

快速排序是不穩定的演算法，它不滿足穩定演算法的定義。

演算法穩定性---假設在數列中存在a[i]=a[j],若排序之前，a[i]在a[j]前面；並且排序之後，a[i]仍然在a[j]前面。則這個演算法是穩定的。

快速排序時間複雜度

快速排序的時間複雜度在最壞情況下是O(N^2)，平均的時間複雜度是O(N*lgN)。

這句話很好理解：

假設被排序的數列中有N個數。遍歷一次的時間複雜度數O(N),需要遍歷多少次呢？至少lg(N+1)次，最N次。

(01) 為什麼最少數lg(N+1)次？快速排序數採用分治法進行遍歷的，我們將它看作一顆二叉樹，它需要遍歷的次數就少二叉樹的深度，而根據完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數最少數lg(N+1)次。

(02)為什麼最多數N次？這個應該非常簡單，還是將快速排序看作一顆二叉樹，它的深度最大是N。因此，快速排序的遍歷次數最多是N次。