【模板】快速排序与归并排序——Template，QuickSort&MergeSort-蒲公英云

【模板】快速排序与归并排序——Template，QuickSort&MergeSort

快速排序

#include<iostream>
using namespace std;
int n,a[1000001];
void qsort(int l,int r)//应用二分思想
{ 
    int mid=a[(l+r)/2];//中间数
    int i=l,j=r;
    do{ 
        while(a[i]<mid) i++;//查找左半部分比中间数大的数
        while(a[j]>mid) j--;//查找右半部分比中间数小的数
        if(i<=j)//如果有一组不满足排序条件（左小右大）的数
        { 
            swap(a[i],a[j]);//交换
            i++;
            j--;
        }
    }while(i<=j);//这里注意要有=
    if(l<j) qsort(l,j);//递归搜索左半部分
    if(i<r) qsort(i,r);//递归搜索右半部分
}
int main()
{ 
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}

归并排序

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N], tmp[N];
void merge_sort(int q[], int l, int r) { 
    if(l >= r) {                               //如果数组中没有数，或者只有一个数，直接return
        return ;
    }
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);                     //递归归并左右两部分
    merge_sort(q, mid + 1, r);
    int k = 0, i = l, j = mid + 1;             //k记录当前tmp数组中已经放好位置的是第几个数
    while(i <= mid && j <= r) { 
        if(q[i] <= q[j]) {                      //把较小的那个数放入tmp数组中
            tmp[k++] = q[i++];
        } else { 
            tmp[k++] = q[j++];
        }
    }
    while(i <= mid) {                          //如果某个指针走到了尽头，则把另一个数组剩下的部分全部加入到tmp数组中
        tmp[k++] = q[i++];
    }
    while(j <= r) { 
        tmp[k++] = q[j++];
    }
    for(int i = l, j = 0; i <= r; ++i, ++j) {             //再把tmp数组的数写回到q[l~r]
        q[i] = tmp[j];
    }
}
int main() { 
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) { 
        scanf("%d", &q[i]);
    }
    merge_sort(q, 0, n - 1);
    for(int i = 0; i < n; ++i) { 
        printf("%d ", q[i]);
    }
    return 0;
}