AcWing 785. 快速排序
原题链接
简单
作者:
月下邂逅
,
2024-04-17 16:52:33
,
所有人可见
,
阅读 1
快速排序
C++ 代码
#include<iostream>
using namespace std;
const int N=1000010;
int arr[N];
void quick_sort(int arr[],int l,int r)
{
//l>=r时说明所有数据都已经安排完了,可以返回
if(l>=r)return ;
//i和j会先进行一次++和--再操作,num取中间数的值,取两边的值可能会超出内存限制
int i=l-1,j=r+1,num=arr[l+r>>1];
while(i<j)
{
//do while防止因为两边同时等于num导致循环卡死,最终a[l.l+1,...,i]<=num,a[j.j+1,...,r]>=num。这里判断条件不能相等,否则在全相等情况下i和j会下标越界,且j+1=0造成无限划分
do i++;while(arr[i]<num);
do j--;while(arr[j]>num);
//i和j相等时可以不交换
if(i<j) swap(arr[i],arr[j]);
}
//以j划分num不能为arr[r],以i划分不能选择arr[l],可能造成无限划分因为j>=l,而i可能取到r
quick_sort(arr,l,j);
quick_sort(arr,j+1,r);
}
int main()
{
int n;
//scanf和printf的速度远远快于cin和cout
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
//快速排序
quick_sort(arr,0,n-1);
for(int i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
return 0;
}