AcWing 785. 快速排序

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;
int a[N];

void quick_sort(int a[],int l,int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1,x = a[(i+j) >> 1];
    while(i < j)
    {
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i< j) swap(a[i],a[j]);
    }
    quick_sort(a,l,j);
    quick_sort(a,j + 1,r);
    
}

int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n; i ++) scanf("%d",&a[i]);
    quick_sort(a,0,n - 1);
    for(int i = 0 ; i < n; i ++) printf("%d ",a[i]);
    
    
    return 0;
}

每次将在边界范围内数字,以一个基准数为标准,小于基准数的放左侧,大于基准数的放右侧,然后递归的对小区间做相同处理

AcWing 787. 归并排序

#include<stdio.h>
#define N 100010
int a[N],tmp[N];
void merge_sort(int a[],int l ,int r)
{
    int mid = (l + r)>>1;
    if (l >= r) return;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    int s = 0,i = l, j = mid + 1;
    while (i <= mid && j <= r)
    {
        if(a[i] <= a[j]) tmp[s ++] = a[i ++];
        else tmp[s ++] = a[j ++];
    }
    while (i <= mid) tmp[s ++] = a[i ++];
    while (j <= r) tmp[s ++] = a[j ++];
    for (int k = l,t = 0; k <= r ; k ++,t ++) a[k] = tmp[t];
    
}
int main(void)
{
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i ++) scanf("%d",&a[i]);
    
    merge_sort(a, 0, n-1);
    
    for( int i = 0 ; i < n ; i++) printf("%d ",a[i]);
    
    return 0;
}

 需要额外的空间用于存储temp数组.

将每个小区间排序,再合并区间,最后得到的就是有序数列