来自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;
}

快速排序

题目
步骤：

  1. 找分界点和基准点
  2. 交换，使得x的左边都小于等于x，x的右边都大于等于x
  3. 递归 
#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;
}