快速排序：一聽名字就知道這種排序很快的，是吧？沒錯，它是一種效率比較高的排序算法。

快速排序采用的是分治的思想。

比如，將一串數中的一個元素作為基準，然后將比它小的數排在它的左邊，比它大的數排在它的右邊。將作為基準的那個元素排在正確的位置。然后通過遞歸，依次將所有的元素都排好。（實質就是遞歸子問題）

在這里，快速排序也有幾種不同的方式，下面我給大家一一敘述吧。

快速排序的幾種方法：

1.左右指針法(交換)：
?????? 有一個數組a[size],左指針left指向下標為0的位置，右指針right指向下標為size-1的位置，同時標志key=a[right];left找a[left]>key的元素的下標，right找a[right] < key的元素的下標。left先開始走，當遇到比key大的數時，停下來，再由right開始走，當遇到比key小的數時，停下來。將left和right分別指的數交換，前提是left<right時，如果left>=right就說明一次快排結束。再將left指向的值與key值交換即可。此時的數組呈現出左邊的值都比key值小，右邊的值都比key值大。一次快排將數組分為兩個區間，我們再對每個區間進行上述的排序方式。直到每個小區間已不能再劃分。(即一個區間只有兩個元素)

代碼實現：

int PartSort(int* a,int left,int right)
{int& key = a[right];//int key = right;while(left < right) {while(left < right && a[left] <= key) //a[left] <= a[key]++left;while(left < right && a[right] >= key) //a[right] >= a[key]--right;swap(a[left],a[right]);}swap(a[left],key);//swap(a[left],a[key]);return left;
}
void QuickSort(int* a,int left,int right)
{if(left < right){int div = PartSort(a,left,right);QuickSort(a,left,div-1);QuickSort(a,div+1,right);}
}
void Display(int *a,size_t size)
{for(size_t i = 0; i < size; ++i){cout<<a[i]<<" ";}cout<<endl;
}

2.挖坑法
?????? 有一個數組a[size],左指針left指向下標為0的位置，右指針right指向下標為size-1的位置，同時標志key=a[right];首先將key的位置設為一個坑，從left開始，找比key值大的，找到后將a[left]放到坑里，即a[right]=a[left]，同時將left的位置再設為坑;再從right開始找比key小的，找到后將a[right]放到上次設的坑里，即a[left]= a[right];直到left>=right,將key值放到現在的坑中即可。此時的數組呈現出左邊的值都比key值小，右邊的值都比key值大。一次快排將數組分為兩個區間，我們再對每個區間進行上述的排序方式。直到每個小區間已不能再劃分。(即一個區間只有兩個元素)

代碼實現：

int PartSort1(int* a,int left,int right)
{int key = a[right];while(left < right) {while(left < right && a[left] <= key) ++left;a[right] = a[left];while(left < right && a[right] >= key) --right;a[left] = a[right];}a[left] = key;return left;
}
void QuickSort(int* a,int left,int right)
{if(left < right){int div = PartSort1(a,left,right);QuickSort(a,left,div-1);QuickSort(a,div+1,right);}
}

3.前后指針法
????? 有一個數組a[size],指針cur指向0的位置,prev指向cur-1的位置，key為a[size-1];當cur對應的值大于key值時，cur++，然后將++prev對應的值與cur對應的值交換。繼續比它大的值就跳過，找到a[cur]<key的值時，交換a[cur]和a[++prev]的值。直到cur指向最后一個元素，此時將a[++prev]和最后一個元素交換。此時的數組呈現出左邊的值都比key值小，右邊的值都比key值大。一次快排將數組分為兩個區間，我們再對每個區間進行上述的排序方式。直到每個小區間已不能再劃分。(即一個區間只有兩個元素)

代碼實現：

int PartSort2(int* a,int left,int right)
{int key = a[right];int cur = left;int prev = cur-1;while(cur < right){if(a[cur] < key && ++prev != cur)swap(a[cur],a[prev]);++cur;}swap(a[++prev],a[cur]);return prev;
}
void QuickSort(int* a,int left,int right)
{if(left < right){int div = PartSort2(a,left,right);QuickSort(a,left,div-1);QuickSort(a,div+1,right);}
}

以上就是快速排序的幾種方法。

當然，分析過時間復雜度和空間復雜度之后，在某些特定的情況下，快速排序依然不是很快。下面就給大家介紹幾種快速排序優化后的算法。

1.三數取中法

????? 在快排算法中，如果數組本來就有序，key值就不會是中間的數字，那么快排每次遍歷N次，時間復雜度就為O(N*N)為了避免快排遇到最壞的情況，我們采用三數取中法的方式，取到中間值的數與最后一個數交換，再進行快排方式。 這樣可以使數組的key值都在較中間的位置,趨向于二叉樹結構。時間復雜度也將提升到N*lgN。

代碼實現：

//三數取中法
int MidNum(int* a,int left,int right)
{int mid = left+((right-left)>>1);if(a[mid] < a[right]){if(a[mid] < a[right])return mid;else if(a[left] < a[right])return right;elsereturn left;}else{if(a[left] < a[right])return left;else if(a[mid] < a[right])return right;elsereturn mid;}
}int PartSortMid(int* a,int left,int right)
{int MidKey = MidNum(a,left,right);swap(a[MidKey],a[right]);int key = right;while(left < right){while(left < right && a[left] <= a[key])    //左邊如果比key位置的數小，則跳過++left;while(left < right && a[right] >= a[key])   //右邊如果比key位置的數大，則跳過--right;swap(a[left],a[right]);}swap(a[left],a[key]);return left;
}
void QuickSort(int* a,int left,int right)
{if(left < right){int div = PartSortMid(a,left,right);	QuickSort(a,left,div-1);QuickSort(a,div+1,right);}
}

2.小區間優化

????? 對于上述三數取中法的快排算法，每次都是將一小段區間進行快排算法，即使區間很小也重復快排算法。我們前面學過 插入算法，當數組接近有序時，時間復雜度就為O(N)，那么在快排算法中，我們可以對小區間進行優化，區間很小時，我們可以將數組視為接近有序，此時用插入排序來代替快排，比如當right-left<一個小區間的值時(自己規定，一般為13或20較好),這樣就大大提高了快排的效率。

代碼實現：

//小區間優化
void QuickSort(int* a,int left,int right)
{if(left < right){if(right - left < 3)     //當區間比較小，接近有序時，適合使用插入排序{InsertSort(a,right-left+1);}int div = PartSort(a,left,right);QuickSort(a,left,div-1);QuickSort(a,div+1,right);}
}

1.之前寫的快排都是遞歸實現的。我們也可以用非遞歸實現快速排序。這里會用到棧。

代碼實現：

//用棧實現
#include<stack>
int MidNum(int* a,int left,int right)
{int mid = left+((right-left)>>1);if(a[mid] < a[right]){if(a[mid] < a[right])return mid;else if(a[left] < a[right])return right;elsereturn left;}else{if(a[left] < a[right])return left;else if(a[mid] < a[right])return right;elsereturn mid;}
}int PartSortMid(int* a,int left,int right)
{int MidKey = MidNum(a,left,right);swap(a[MidKey],a[right]);int key = right;while(left < right){while(left < right && a[left] <= a[key])++left;while(left < right && a[right] >= a[key])--right;swap(a[left],a[right]);}swap(a[left],a[key]);return left;
}void QuickSortNonR(int *a,int left,int right)
{stack<int> st;st.push(right);st.push(left);while(!st.empty()){if(right-left < 3)InsertSort(a,right-left+1);left = st.top();st.pop();right = st.top();st.pop();int div = PartSortMid(a,left,right);if(div-1 > left){st.push(div-1);     //注意入棧順序st.push(left);}if(div+1 < right){st.push(right);st.push(div+1);}}
}

運行結果：