1.選擇數組中的一個元素
2.進行一次Partition,將數組分為小于該元素和大于該元素的兩個部分
3.分別在兩個部分中選取元素遞歸第1-2步至有序即可
- 核心操作Partition:
我們通常會使用整個數組的第一個元素v作為整個數組的分界點
其中:
指向數組分界點元素v的指針記為l(小寫L);
大于v和小于v的分界線上的元素給個指針記為j;
正在判斷的當前元素e的指針為i;
即:
arr[l+1, j] < v
arr[j +1,i -1] > v
此時判斷e與v的大小:
若e > v,則 i++即可把e放入大于v的范圍中
若e < v,則交換j+1與i所指元素的位置,然后j++,即可把e放入小于v的范圍中
當所有排序結束后,只需要將l與j所指元素交換位置即可讓分界點位于其應該在的位置
image.png
image.png
//返回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...i)>v
int j = l;
for (int i = l + 1; i <= r; i++){
if (arr[i] < v){
swap(arr[j + 1], arr[i]);
j++;
}
}
swap(arr[j], arr[l]);
return j;
}
- 未優(yōu)化quicksort
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);
}
- 優(yōu)化1：隨機選中一個元素作為數組的分界點
發(fā)現(xiàn)問題：對近乎有序的數組進行排序時：
n較大恶座，quicksort出現(xiàn)stackoverflow内舟。
n較小边臼，快速排序的時間遠大于歸并排序的時間肢专。
int __partition(T arr[], int l, int r){
int s = rand() % (r - l + 1) + l;
swap(arr[l], arr[s]);
T v = arr[l];
//arr[l + 1...j]<v; arr[j + 1...i)>v
int j = l;
for (int i = l + 1; i <= r; i++){
if (arr[i] < v){
swap(arr[j + 1], arr[i]);
j++;
}
}
swap(arr[j], arr[l]);
return j;
}
- 優(yōu)化2：雙路快速排序法
問題分析:由于待排數組中出現(xiàn)大量重復元素,導致一旦分界點選擇過大或過小,就會造成大規(guī)模的不平衡堂淡。
甚至由于有大量重復元素,就算分界點選中了正中間的5,也有大量的5聚集在大于v的節(jié)點中（因為判斷條件是arr[i]<v余掖，才進行交換贿肩，等于v時苍凛，j++）,仍會導致分配不均的問題出現(xiàn)。
image.png
image.png
image.png
template<typename T>
int __partition2(T arr[], int l, int r){
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
//arr[l+1...i)<=v;arr(j...r]>=v
int i = l + 1, j = r;
while (true){
while (i <= r&&arr[i] < v) i++;
while (j >= l + 1 && arr[j] > v) j--;
if (i > j) break;
swap(arr[i], arr[j]);
i++;
j--;
}
swap(arr[l], arr[j]);
return j;
}
-
優(yōu)化3：三路快速排序
e<v
image.png
image.png
lt++;
i++;
e>v
image.png
image.png
gt--;
處理完后
image.png
image.png
- while版
template<typename T>
void __quickSort3Ways(T arr[], int l, int r){
if (r - l <= 15){
insertionSort2(arr, l, r);
return;
}
//partition
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
int lt = l; //arr[l+1...lt]<v
int gt = r + 1; //arr[gt..r]>v
int i = l + 1; //arr[lt+1...i)=v
while (i < gt){
if (arr[i] < v){
swap(arr[i], arr[lt + 1]);
lt++;
i++;
}
else if (arr[i] > v){
swap(arr[i], arr[gt - 1]);
gt--;
}
else{
i++;
}
}
swap(arr[l], arr[lt]);
__quickSort3Ways(arr, l, lt - 1);
__quickSort3Ways(arr, gt, r);
}
- 自己寫的for版
template<typename T>
void __quickSort3Ways(T arr[], int l, int r){
if (r - l <= 15){
insertionSort2(arr, l, r);
return;
}
//partition
swap(arr[l], arr[rand() % (r - l + 1) + l]);
T v = arr[l];
int lt = l; //arr[l+1...lt]<v
int gt = r + 1; //arr[gt..r]>v
int i = l + 1; //arr[lt+1...i)=v
for (int i = l + 1; i < gt; i++){
if (arr[i] < v){
swap(arr[i], arr[lt + 1]);
lt++;
}
else if (arr[i] > v){
swap(arr[i], arr[gt - 1]);
gt--;
--i;
}
}
swap(arr[l], arr[lt]);
__quickSort3Ways(arr, l, lt - 1);
__quickSort3Ways(arr, gt, r);
}
