1. 快排基礎
?快速排序的要點是先找到第一個元素的最終的位置，如何尋找就如下圖所示，找到比4小的數，在找到比4大的數，核心就是如何把4這個數挪到正確的位置上，
?下圖中，l記錄的是當前的元素，j記錄<v和>v的分界點（對于j這個點上值多少不用去管），i是當前訪問的元素，如果當e>v就直接放在后面，
?如果當e<v這種情況，就需要把e放在前面橙色的部分，方法很簡單，e和j位置上的元素互換（直接將e放到j的位置），而j++就好，
?最后都結束了之后再把v這個元素放在j上，
初版代碼如下：
// 對arr[l,,r]部分進行partition操作
//回傳是一個索引 p 使得arr[l...p-1] < arr[p] arr[p+1....r] > arr[p]
template <typename T>
int __partition(T arr[],int l,int r){
// 先把數保存下來
T v = arr[l];
// arr[l+1...j] < v arr[j+1....r） > arr[j]
int j = l;
for (int i = l+1; i <= r; ++i) {
if (arr[i] < v){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
// 內部快排介面 對arr[l...r]進行快速排序
template <typename T>
void __quickSort(T arr[],int l,int r){
// 出現例外
if (l>=r){
return;
}
int p = __partition(arr,l,r);
__quickSort(arr,l,p-1);
__quickSort(arr,p+1,r);
}
// 快速排序
template <typename T>
void quickSort(T arr[],int n){
__quickSort(arr,0,n-1);
}
和直接插入排序相比
結果如下：
quick order:0.01s
insertSort:2.941s
Process finished with exit code 0
2. 快排進階
?當遇到近乎有序的陣列時，快速排序會慢很多倍，
結果如下：
quick order:0.028s
insertSort:0s
?原因如下圖，他和歸并排序不一樣的地方是歸并排序始終是對陣列一分為二，但是在快速排序中左右子樹是不一定對稱的，當遇到最差情況就是有序的陣列左側（或者右側）子樹是沒有的，那么他會退化成o（n^2），
解決方法也是很簡單，即設定隨機種子，隨機選擇一個元素把這個元素與第一個元素進行互換，這樣可以降低退化成o（n^2）的可能性，
// 對arr[l,,r]部分進行partition操作
//回傳是一個索引 p 使得arr[l...p-1] < arr[p] arr[p+1....r] > arr[p]
template <typename T>
int __partition(T arr[],int l,int r){
// 先把數保存下來
swap(arr[l],arr[rand()%(r-l+1)+l]);
T v = arr[l];
// arr[l+1...j] < v arr[j+1....r） > arr[j]
int j = l;
for (int i = l+1; i <= r; ++i) {
if (arr[i] < v){
swap(arr[j+1],arr[i]);
j++;
}
}
swap(arr[l],arr[j]);
return j;
}
// 內部快排介面 對arr[l...r]進行快速排序
template <typename T>
void __quickSort(T arr[],int l,int r){
// 出現例外
if (r<l){
// insertSort(arr,r-l+1);
return;
}
int p = __partition(arr,l,r);
__quickSort(arr,l,p-1);
__quickSort(arr,p+1,r);
}
// 快速排序
template <typename T>
void quickSort(T arr[],int n){
srand(time(NULL));
__quickSort(arr,0,n-1);
}
3. 快速排序高階
?通過使用雙指標的方式進行排序入，下圖所示：
參考文獻
[1]維基百科.快速排序[EB/OL].https://zh.wikipedia.org/wiki/快速排序,2020-10-10.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/227461.html
標籤：C++
上一篇：c++末尾匹配