来自acwing y总
归并排序
#include <iostream>
using namespace std;
const int maxn = 100000+9;
int a[maxn];
void merge_sort(int l,int r)
{
if(l>=r) return ;
int tmp[maxn];
int mid = (l+r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int k = 0, i = l,j = mid+1;
while(i<=mid&&j<=r)
{
if(a[i]<a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while(i<=mid) tmp[k++] = a[i++];
while(j<=r) tmp[k++] = a[j++];
for(i=l,j=0;i<=r;i++,j++) a[i] = tmp[j];
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
merge_sort(0,n-1);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
快速排序
题目
步骤:
- 找分界点和基准点
- 交换,使得x的左边都小于等于x,x的右边都大于等于x
- 递归
#include <iostream>
using namespace std;
const int maxn = 1e5+9;
int a[maxn];
void qsort(int l,int r)
{
if(l>=r) return ;//递归截至条件
//第一步确定基准点
int mid = (l+r)>>1;
int i = l-1;
int j = r+1;
int x = a[mid];
while(i<j)
{
do i++; while(a[i]<x);
do j--; while(a[j]>x);
if(i<j) swap(a[i],a[j]);
}
qsort(l,j);
qsort(j+1,r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
qsort(0,n-1);
for(int i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}