快排是基于分治思想的一种算法，可使用双指针使代码更加优美。
基本步骤
- 确定分界点 q[l], q[(l+r)>>1]（l+(r-l>>1)防止整型溢出）, q[r]
- 调整区间，使得第一个区间内的数都<=x，第二个区间内的数都>=x
- 递归处理左右两段
暴力做法
*注意：暴力做法单词时间复杂度O(n)
- 新建两个数组 a[], b[]
- 对区间[l, r]: 如果 q[i] 比x小q[i]存入a数组， 否则q[i]存入b数组
- a，b 两个数组依次放回q数组
优美的双指针做法
直接给代码，平均时间复杂度O(nlogn)
#include<bits/stdc++.h>
using namespace std;
//异或交换可能提高效率
void xor_swap(int &a, int &b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
//双指针快排
void quick_sort(vector<int> &q, int l, int r)
{
if (l >= r) return ;
int x=q[l+(r-l>>1)],i=l-1,j=r+1;
while(i<j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if (i < j) xor_swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin>>n;
vector<int> q(n);
for (int i = 0; i < n; i++) cin>>q[i];
quick_sort(q, 0, n - 1);
for (auto i: q) cout << i << ' ';
cout<<'\n';
return 0;
}关于xor_swap的一些说明
平时其实不建议用xor_swap，正常的std::sort已经够用了。这里选择使用xor_swap的原因为AcWing上提交的时候被卡xor_swap了。
关于xor_swap的证明可参照关于xor_swap的证明
评论（0）
暂无评论