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;
}
- 未优化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);
}
- 优化1：随机选中一个元素作为数组的分界点
发现问题：对近乎有序的数组进行排序时：
n较大，quicksort出现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;
}
- 优化2：双路快速排序法
问题分析:由于待排数组中出现大量重复元素,导致一旦分界点选择过大或过小,就会造成大规模的不平衡。
甚至由于有大量重复元素,就算分界点选中了正中间的5,也有大量的5聚集在大于v的节点中（因为判断条件是arr[i]<v，才进行交换，等于v时，j++）,仍会导致分配不均的问题出现。
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;
}
-
优化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);
}
