本文将介紹排序算法中最常用，以及最重要的快速排序。
1 快速排序執行個體
快速排序由C. A. R. Hoare在1960年提出，是冒泡排序的一種改進。快速排序就跟它的名字一樣，效率很快。跟冒泡排序，選擇排序相比，它們使用相同的空間大小，但是，快速排序卻可以達到O(nlogn)的時間複雜度，比O(n^2)要快上很多。那麼，快速排序是怎麼做的呢？它的核心思想是，
找到一個基準數，讓這個基準數到它該去的位置。并且，基準數左邊的數都比這個它要小，右邊的數都比它要大。根據這個思想，
我們每一趟至少能夠保證基準數在它應該在的位置，并且右邊的數都大于左邊的數，整體基本有序。那怎麼處理基準數左邊和右邊兩部分的數呢？很簡單，分别對左邊和右邊遞歸剛剛那個過程，就ok了。這就是快速排序，由于每次都能夠排好一個數，并且能夠保證左邊區域的數隻需要在左邊區域排序，右邊區域的數隻需要在右邊區域排序，它們本身在該在位置的機率很大，大大降低了需要交換的次數。
我們來看例子，給定數組[4,5,1,10,3,6,9,2]，怎麼用快速排序對它排序呢？
首先，選擇第一個數作為基準數
設定指針i和j，分别指向最左和最右
指針j向左移動，找到第一個小于基準數4的位置。由于指向的2比4小，是以指針j沒有移動。
指針i向右移動，找到第一個大于基準數4的位置
交換指針i和j對應的元素
指針j繼續向左移動，找到了3比基準數小。
指針i繼續向右移動，找到了10比基準數大。
交換指針i和j對應的元素
指針j繼續左移，與指針i相遇，停止。
交換指針i與基準數所在位置的元素。
這一趟快速排序結束，基準數4達到了它應該在的位置。而左邊都是比4小的數，右邊都是比4大的數。接下來我們隻需要遞歸這個過程就可以了。
2 代碼解析
49-62行就是剛剛的例子中做的操作，具體在代碼注釋中已經寫明。
66,67行，分别遞歸處理左邊和右邊，最終完成整體排序。
這裡還有一個問題：
為什麼每次都要從右邊開始找，而不能從左邊開始找呢？ 如果從左邊開始找，那麼在這個狀态時，i往右一步就停止了。這時候，如果交換基準數和指針i的元素，10會被交換到左邊，不符合快速排序“左邊的數都比基準數小”的限制。之是以要讓指針j先動，就是因為，
最後必須停在比基準數小的元素，隻有右邊先動才可以保證。3 效率分析
快速排序的效率跟基準數的選擇有很大關系。
如果基準數選得好，
每次基準數都能夠剛好排在中間的位置，遞歸的時候，兩個子問題的大小就是平衡的，不停地二分下去，最終的時間複雜度就是
T(n)=T(n/2)+T(n/2)+O(n)=
O(nlogn)如果基準數選得差，
每次基準數剛好是最大值或者最小值，每次子問題的規模隻減小了1，這樣無疑效率會差很多，最終的時間複雜度為
T(n)=T(n-1)+T(1)+O(n)=
O(n^2)