1 快速排序基本思想
一趟快速排序。
Q：如何实现一趟快速排序呢？
A1：一般实现。
但是这种做法效率并不高，因为需要开辟新的内存空间，最后还需要将元素填回，非常耗时。
A2：不开辟新内存，一边遍历一边整理。
step1：选取首元素作为基点key，将数组划分成多个片段。
橙色区域：基点；
- 黄色&绿色区域：已处理序列；
· 黄色区域：元素均<key；
· 绿色区域：元素均≥key，且绿色区域紧挨着黄色区域；- 灰色区域：待处理序列。
即：
- nums[left]：基点key；
- nums[left+1...k：黄色区域，<key；
- nums[k...i：绿色区域，≥key；
- nums[i...n：灰色区域，待处理序列；
初始时：i=left+1，k=left+1，保证初始时刻黄色区域和绿色区域均为空。
step2：遍历灰色区域元素。
交换之后，黄色区域和绿色区域仍满足各自区域内元素要么全<key，要么全≥key。
step3：灰色区域遍历结束，将基点与黄色区域尾元素（即nums[k-1]）进行交换。
此时，完成一趟快速排序，基点对应下标为k-1，即key_index = k-1。
step4：对黄色区域和绿色区域分别进行快速排序，key_index = k-1。
- 黄色区域：nums[left ... key_index-1]；
- 绿色区域：nums[key_index+1 ... right]。
2 代码实现
class Solution {
public:
int partition(vector<int>& nums, int left, int right{
int privot = nums[left];
int i = left+1;
int k = i; // [left+1...k:<privot; [k...i:≥privot
for(; i<=right; i++{
if(nums[i] < privot{
swap(nums[i], nums[k++];
}
}
swap(nums[left], nums[k-1];
return k-1;
}
void quickSort(vector<int>& nums, int left, int right{
if(left >= right{
return;
}
int privotIndex = partition(nums, left, right;
quickSort(nums, left, privotIndex-1;
quickSort(nums, privotIndex+1, right;
}
vector<int> sortArray(vector<int>& nums {
quickSort(nums, 0, nums.size(-1;
return nums;
}
};
有效性测试
LeeCode.912. 排序数组
3 随机选取基点
Q：若选取首个元素作为基点，那么划分操作（即partition）在顺序数组或逆序数组上的效果将很差（如上面的超出时间限制）。
- 拆分的子问题只比原来减少了1个元素；
- 每一次划分只能确定一个元素的位置；
- 导致递归树高度增加（非常不平衡、递归树倾斜）；
- 快速排序退化成选择排序，时间复杂度为O(N^2。
解决：通过随机选取基点，打破原数组的有序性。
代码实现
#include<time.h>
#include<random>
int partition(vector<int>& nums, int left, int right{
srand((unsignedtime(NULL; // 设置随机种子
int randomIndex = rand( % (right - left + 1 + left;
swap(nums[randomIndex], nums[left];
int privot = nums[left];
int i = left+1;
int k = i; // [left+1...k:<privot [k...i:≥privot
for(; i<=right; i++{
if(nums[i] < privot{
swap(nums[i], nums[k++];
}
}
swap(nums[left], nums[k-1];
return k-1;
}
有效性测试：LeeCode.912. 排序数组
4 双路快排和三路快排
Q：针对数组含有大量重复元素（甚至所有元素均相同）的场景，随机选取基点无效！
解决方法如下：
4.1 双路快排
双路快排的目的：
Q：为什么黄色区域和绿色区域都可以=pivot，即二者区域内元素取值有重合呢？
A：因为双路快排是要将与基点值相等的元素均匀地分布到黄色区域和绿色区域，也就是使得黄色和绿色各自区域内均存在多个值=pivot的元素。
• 若二者取值不重合，如黄色区域代表≤pivot，绿色区域代表>pivot，那么经一趟快排之后，值=pivot的元素将全部在黄色区域内。
• 若二者取值重合，可保证值=pivot的元素不会扎堆在某一单色区域。
具体步骤：
step1：选取首元素作为基点key（随机选取基点），将数组划分成多个片段。
橙色区域：基点；
- 黄色&绿色区域：已处理序列，分别位于数组的最左侧（忽略基点）和最右侧；
· 黄色区域：元素均≤key；
· 绿色区域：元素均≥key；- 灰色区域：待处理序列。
即：
- nums[left]：基点key；
- nums[left+1...i：黄色区域，≤key；
- nums(j...right]：绿色区域，≥key；
- nums[i...j]：灰色区域，待处理序列；
初始时，i = left+1，j = right，保证初始时刻黄色区域和绿色区域为空。
step2：通过指针i和指针j双向遍历灰色区域元素。
- 正向遍历：
- 若当前元素nums[i]＜key，表示属于黄色区域，将当前元素追加至黄色区域尾部（i++即可）；
- 若当前元素nums[i]≥key，表示属于绿色区域，i暂停遍历，等待反向遍历至合适位置（即等j停住）。
- 反向遍历：
- 若当前元素nums[j]＞key，表示属于绿色区域，将当前元素加入绿色区域头部（j--即可）；
- 若当前元素nums[j]≤key，表示属于黄色区域，j暂停遍历，等待正向遍历至合适位置（即等i停住）。
A：因为双路快排是要将与基点值相等的元素均匀地分布到黄色区域和绿色区域，不仅要使得黄色和绿色各自区域内均存在多个值=pivot的元素，还要尽可能使得每个颜色区域内值=pivot的元素离散分布不要连续扎堆，否则在后续对子表继续进行快排时，就可能会出现值=pivot的元素连续扎堆的情况。
• i和j扫描到nums[i]=key或nums[j]=key时，不停住，只有当nums[i]>key和nums[j]<key时才停住：出现值=pivot的元素连续扎堆的情况；
• i和j扫描到nums[i]=key或nums[j]=key时，停住然后二者交换，实现值=pivot的元素在各颜色区域内离散分布。
step3：灰色区域遍历结束，此时i≥j，将基点与nums[j]进行交换。
-
i=j时：
-
i>j时：
代码实现：
int partition(vector<int>& nums, int left, int right{
/* step1: 随机选取基点privot */
srand((unsignedtime(NULL; // 设置随机种子
int randomIndex = rand( % (right - left + 1 + left;
swap(nums[randomIndex], nums[left];
int privot = nums[left];
/* step2: 执行一趟快排 */
int i = left+1;
int j = right;
while(1{
while(i <= j && nums[i] < privot{
i++;
}
while(i <= j && nums[j] > privot{
j--;
}
if(i >= j{
break;
}
swap(nums[i], nums[j];
i++;
j--;
}
/* step3: 将基点放在分界线处 */
swap(nums[left], nums[j];
return j;
}
4.2 三路快排
三路快排目的：
将与基点相等的元素集中放置在数组的中央位置，即实现下图效果。这样，相较于二路快排，三路快排经过1次快速排序就可以将多个元素放在它正确的位置上（多个与基点值相等的元素挤到了数组中央），而二路快排每次仅能确定一个元素在正确位置上。
具体步骤：
step1：选取首元素作为基点key（随机选取基点），将数组划分成多个片段。
- nums[left]：基点key；
- nums[left+1...lt：黄色区域，<key；
- nums(gt...right]：绿色区域，>key；
- nums[i...gt]：灰色区域，待处理序列；
step2：遍历灰色区域。
-
若nums[i]<key，需要将其加入黄色区域尾部，通过交换nums[i]和nums[lt]实现，然后lt++，i++；
代码实现：
#include<time.h>
#include<random>
class Solution {
public:
void quickSort(vector<int>& nums, int left, int right{
if(left >= right{
return;
}
/* step1: 随机选取基点privot */
srand((unsignedtime(NULL; // 设置随机种子
int randomIndex = rand( % (right - left + 1 + left;
swap(nums[randomIndex], nums[left];
int privot = nums[left];
/* step2: 执行一趟快排 */
int i = left + 1;
int lt = left + 1, gt = right;
while(i <= gt{
if(nums[i] == privot{
i++;
}else if(nums[i] < privot{
swap(nums[i++], nums[lt++];
}else{
swap(nums[i], nums[gt--];
}
}
/* step3: 将基点放在分界线处 */
swap(nums[left], nums[lt-1];
/* step4: 对左右子表进行快排 */
quickSort(nums, left, lt-2;
quickSort(nums, gt+1, right;
}
vector<int> sortArray(vector<int>& nums {
quickSort(nums, 0, nums.size(-1;
return nums;
}
};
4.3 有效性测试
LeeCode.912. 排序数组
5 三路快排partition思路的应用
问题描述：
算法思想：
将数组分组，如下图所示：
-
nums[k...i内元素均==1；
-
nums(j...right]内元素均==2。
初始时，i=left, k=left, j=right，保证初始时刻黄色、橙色、绿色三个区域均为空，然后遍历灰色区域直至结束： -
若nums[i]==0，应将其追加至黄色区域尾部，通过交换nums[i]和nums[k]实现，交换完毕需要执行i++, k++；
代码实现：
class Solution {
public:
void sortColors(vector<int>& nums {
int left = 0, right = nums.size(-1;
int i = 0, j = right, k = left;
while(i <= j{
if(nums[i] == 1{
i++;
}else if(nums[i] == 0{
swap(nums[i++], nums[k++];
}else{
swap(nums[i], nums[j--];
}
}
}
};