算法思想
把n個元素劃分為三段：左端Left,中間段middle和右端right。中段僅有一個元素。左端的元素都不大於中間段的元素，右端的元素都不小於中間段的元素。因此可以對lefe和right對立排序，所以，快速排序是一種分治思想，把大問題分為了若干個小問題。middle的元素稱為支點或分割元素。
舉例。考察元素【4，8，3，7，1，5，6，2】。假設選擇元素6作為支點。因此6屬於middle；4，3，1，5，2屬於left,8和7屬於right。left排序結果為1，2，3，4，5；right排序為7，8。把右端的元素放在支點之後，左端left元素放在支點之前，即可得到有序序列。這個例子僅僅是對快速排序的一個簡單的描述，實際操作要比這複雜。
快速排序步驟
指定一個支點
注意，是“指定”，並沒有明確的約束條件，也就是說這個支點是任意一個元素，一般我們選擇兩種支點：當前序列首元，或者隨機選取
兩種方式各有優劣，前者勝在簡單，但可能影響算法效率
快排中，支點的最終位置越靠近中間位置效率越高，讀起來可能有點怪怪的，注意支點是一個值（具體元素），而不是字面意思的位置，當支點在最終序列中的位置靠前或者靠後時算法效率都不高（類似於“最壞情況”）。
因此，後者在一定程度上減少了最壞情況的發生次數，但隨機選取需要耗費額外的時間
所以在具體應用中一般採用第一種方式來指定“支點”，也就是直接把當前序列的首元作為“支點”。
- 進行一趟快排
快排中，一趟操作的最終目的是把“支點”放到它應該去的地方，同時，支點左邊的元素都小於支點，右邊的元素都大於支點，舉個例子，已知序列{7, -1, 5, 23, 100, 101}，那麼第一趟快排的結果是{_, _, 7, _, _, _}
可以看到，首元（支點）已經去了它該去的地方（在最終的結果序列中，7就在中間位置，沒錯吧）。
- 對子序列進行快排。
第二步我們已經成功用支點將序列分成了3個部分，left,middle right，這三個部分總體是有序的，但是每個元素內部確實無序的，因此我們需要讓這3個部分的內部也有序，對left和right繼續使用快速排序就好（遞歸思想）。
優點分析
在最壞情況下，例如，數據段left總是空的，這快速排序用時O(n^2)。在最好情況下，即數據段的left和right規模大致相同，這時快速排序用時為O(nlogn)。而快速排序的平均複雜度也是O（nlogn），這是令人驚奇的速度，amazing!
快排的前身是歸併，而正是因為歸併存在不可忽視的缺點，才產生了快排。歸併的最大問題是需要額外的存儲空間，並且由於合併過程不確定，致使每個元素在序列中的最終位置上不可預知的。針對這一點，快速排序提出了新的思路：把更多的時間用在“分”上，而把較少的時間用在“治”上。從而解決了額外存儲空間的問題，並提升了算法效率。
快排之所以被稱為“快”排，是因為它在平均時間上說最快的，主要原因是硬件方面的，每趟快排需要指定一個“支點”（也就是作為分界點的值），一趟中涉及的所有比較都是與這個“支點”來進行比較的，那麼我們可以把這個“支點”放在寄存器裡，如此這般，效率自然大大提高。除此之外，快排的高效率與分治思想也是分不開的。
C++語言實現
首先把數組a的最大元素移動到數組的最右端（這樣可以避免支點為最大的元素），然後調用函數執行排序。
#include <iostream>
using namespace std;
template <class>
int indexOfMax(T* a, int n);
template <class>
void quickSort(T * a, int n);
template <class>
void quickSort(T* a, int leftEnd, int rightEnd);
int main()
{
int* a =new int[5];
a[0] = 4, a[1] = 3, a[2] = 1, a[3] = 5, a[4] = 2;
quickSort(a, 5);
for (int i = 0; i < 5; i++) {
cout</<class>/<class>/<class>/<iostream>
閱讀更多 蔚來網 的文章
