算法之——疾速排序（Quick Sort）。本站提示廣大學習愛好者：（算法之——疾速排序（Quick Sort））文章只能為提供參考，不一定能成為您想要的結果。以下是算法之——疾速排序（Quick Sort）正文
望文生義，疾速排序（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，如需求請自行寫出。
