2026.02.13
- 快速排序看代码练习
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <vector>
#include <iostream>
int partition(vector<int>& nums,int low,int high)
{
int pivot=nums[high];
int i=low;
for(int j=low,j<high;j++)
{
if(nums[j]<=pivot)
{
swap(nums[i],nums[j]);
i++;
}
}
swap(nums[i],nums[high]);
return i;
}
void quickSort(vector<int>& nums,int low,int high)
{
if(low<high)
{
int p=partition(nums,low,high);
quickSort(nums,low,p-1);
quickSort(nums,p+1,high);
}
}
|
这是Lomuto分区的写法。思路如下：
让i先待在最左边，它代表的是小于区的右边界，也就是下一个<= pivot 的元素应该放的位置。
然后，j从low开始遍历，开始处理每一个数。如果nums[j]的值小于pivot，那么应该把它放到i那个位置。然后i再向右，为下一次赋值做准备。
发现，遍历的过程中，j是不到high的。j走完之后，i待的地方的值肯定是大于pivot的，这时候把最后一个也就是我们的pivot和该值交换，也不会有问题。
终于梳理了一遍搞懂了。再写两边巩固肌肉记忆：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| #include <iostream>
#include <vector>
int partition(vector<int>& nums,int low,int high)
{
int i=low;
int pivot=nums[high];
for(int j=low;j<high;j++)
{
if(nums[j]<=pivot)
{
swap(nums[i],nums[j]);
i++;
}
}
swap(nums[i],nums[high]);
return i;
}
void quickSort(vector<int>& nums,int low,int high)
{
if(low<high)
{
int pivot=partition(nums,low,high);
quickSort(nums,low,pivot-1);
quickSort(nums,pivot+1,high);
}
}
|
下面学习一下hoare分区：
这个算法大致看了一眼，循环次数要比lomuto要少，而且左右都可以有=，好像更均衡。
先抄写学习一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <iostream>
#include <vector>
int partition_hoare(vector<int>& nums,int low,int high)
{
int pivot=nums[low+(high-low)/2];
int i=low-1;
int j=high+1;
while(true)
{
do i++ ;while(nums[i]<pivot);
do j-- ;while(nums[j]>pivot);
if(i>=j)
{
return j;
}
swap(nums[i],nums[j]);
}
}
|
这个算法就是在夹逼操作。i和j先移动再判断，好理解一些。
每一个whiletrue里，i移动，最后停在一个>=pivot的位置上。j移动，最后停在一个<=pivot的位置上。
二者交换即可。这能让=pivot的能够分布在两边。
判断交错的时候也需要注意一下是i>=j。这个时候j指向左半部分的最后一个元素，i指向右半部分的第一个元素。返回j就行了，后面递归就是(low,j)和（j+1，high）。此时pivot不需要归位！
Hoare快是因为它一次交换同时修复两个元素的位置错误，而Lomuto一次交换只处理一个。
Lomuto是单向扫描：发现一个≤pivot的就往左边塞，被换到右边的元素不检查它该不该在右边。
Hoare是双向夹逼：左边找到该去右边的，右边找到该去左边的，一次交换两个元素各归其位。
所以Hoare的交换次数≈Lomuto的一半，重复元素越多差距越大。
把hoare再练习写一遍：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int partition_hoare(vector<int>& nums,int low,int high)
{
int pivot=nums[low+(high-low)/2];
int i=low-1;
int j=high+1;
while(true)
{
do i++; while(nums[i]<pivot);
do j--; while(nums[j]>pivot);
if(i>=j)
{
return j;
}
swap(nums[i],nums[j]);
}
}
void quickSort_Hoare(vector<int>& nums,int low,int high)
{
if(low<high)
{
int p=partition_hoare(nums,low,high);
quickSort_Hoare(nums,low,p);
quickSort_Hoare(nums,p+1,high);
}
}
|