顧名思義，快速排序（quick sort）速度十分快，時間復雜度為O(nlogn)。雖然從此角度講，也有很多排序算法如歸並排序、堆排序甚至希爾排序等，都能達到如此快速，但是快速排序使用更加廣泛，以至於STL中默認排序方法就是快速排序。此外，快速排序的思想——劃分（Partition）思想給人很多啟發。下面以非降序排序進行介紹，不求有更深的理解，只求為自己做個簡要筆記。
1）劃分（Partition）
劃分思想十分簡單，卻又十分重要，應用廣泛。即：將待排序數組以某一個元素為鍵值（Key），將比此key小的放在左邊，否則放在右邊。其可能的情況為：3,1,4,2,0,KEY=5,6,9,7,8.鍵值Key可以任意選擇。好的鍵值對於提高性能有幫助，但選擇最優鍵值的方法，本身就是一種排序思想。所以，對於排序來說，一般選擇第一個元素作為Key。以下為Partition代碼的一種實現：
注:此處end為數組長度N-1.
1 int partition(int arr[],int start,int end){
2 int i=start, j=end, key;
3 if (start>=end) return -1;
4 for(key=arr[i]; i<j;){
5 for(;i<j && arr[j]>=key; --j);
6 arr[i] = arr[j];
7 for(;i<j && arr[i]<=key; ++i);
8 arr[j] = arr[i];
9 }
10 arr[i] = key;
11 return i;
12 }
首先定義兩個下標變量i,j，分別指向開始和結尾，並將開始start的元素作為鍵值key。然後從後向前遍歷arr[]，找到小於key的元素j，將其覆蓋i；從前向後遍歷arr[]，找到大於key的元素i，將其覆蓋j。直到i與j碰頭，將key寫回i。此時i的位置即選中的key應該在的位置，即：key左邊的元素不大於key，key右邊的不小於key。返回此時key的下標位置i。其時間復雜度為O(n).
2）快速排序（quick sort）
快速排序就是利用劃分思想。每次經過劃分之後，其key所在位置（下標）必然是經過排序後key所在的位置！如上面的3,1,4,2,0,KEY=5,6,9,7,8。元素5此時在位置5，正是其排序後的位置。再如：3,5,1,KEY=10,23,19.元素10在位置3，也是其排完序後所在的位置。正是如此，利用劃分進行快速排序才成為可能。
快速排序思想為：對於數組arr[]以及其首位元素位置start和末尾元素end，選擇其中一個元素作為Key，進行一趟劃分，得到key此時應該在的位置i；然後對於key的左部分start~i-1進行劃分，對於key右部分i+1~end進行劃分；逐漸劃分更小的范圍進行劃分。最終排序完畢。每次進二分劃分，一共劃分了logn次，故快速排序時間復雜度為O(nlogn)。
void quick_sort(int arr[],int start, int end){
int mid;
mid = partition(arr,start,end);
if (mid<0) return;
quick_sort(arr,0,mid-1);
quick_sort(arr,mid+1,end);
}
一種寫法更加巧妙的快速排序，將quick_sort與partition結合，如下：
1 void quick_sort(int arr[],int start,int end){
2 int i=start, j=end, key;
3 if (start>=end) return;
4 for(key=arr[i]; i<j;){
5 for(;i<j && arr[j]>=key; --j);
6 arr[i] = arr[j];
7 for(;i<j && arr[i]<=key; ++i);
8 arr[j] = arr[i];
9 }
10 arr[i] = key;
11 quick_sort(arr,0,i-1);
12 quick_sort(arr,i+1,end);
13 }
注：以上end均為數組長度N-1.
對於長度為N的數組arr[]而言，快速排序只需調用quick_sort(arr,0,N-1)。
3）鏈表的快速排序
鏈表的排序方法也有很多，此處使用快速排序對單鏈表進行排序。其中鏈表節點定義如下：
1 typedef struct _ListNode{
2 int val;
3 struct _ListNode *next;
4 }ListNode;
由於數組進行劃分時，其元素進行移動很費時，然而對於鏈表而言，其元素劃分後，並不需要移動，只需要指針交換即可。所以，定義兩個指針mid和p，p進行快速向後遍歷，當遇到小於KEY的節點時，將其加入到mid尾部並且mid後移一位。執行一趟partition後，p到達尾部NULL，mid為KEY的位置，然後繼續劃分start~mid以及mid~end。其代碼如下：
1 void qsort(ListNode *start,ListNode *end){
2 if (start==end || start==NULL) return;
3 ListNode *p,*mid;
4 for(p=mid=start; p!=end; p=p->next){
5 if(p->val > start->val) continue;
6 mid = mid->next;
7 swap(p->val,mid->val);
8 }
9 swap(start->val,mid->val);
10 qsort(start,mid);
11 qsort(mid->next,end);
12 }
對於一個無頭節點的單鏈表ListNode *head而言，進行快速排序只需調用qsort(head,NULL);即可。此處已將parition合並到快速排序中，並沒有單獨給出Partition，如需要請自行寫出。
