快速排序

主要基于分治思想
在数组左右边界分别设2个指针

且向中间移动

当左指针遇到大于x的数则停下，右指针同（反）理（之）

当两指针都停下时，则使两数交换位置

在两指针到同一点时~~其实只判一点也是可以的~~，这一点左边的数都大于（等于）x而右边都小于（等于）x

以上x皆可替换为特殊性质

写个模板

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int l, int r) //传入两个边界
{
    if(l >= r) return; //两点重合递归终点 

    int x = q[l], i = l - 1, j = r + 1; //要是差一点能过可以把x换为随机数（还是看脸）
    while(i < j)
    {
        do i ++; while(q[i] < x); //第i位小于x则i指针向前移动
        do j --; while(q[j] > x); //第j位大于x则j指针向后移动
        //执行完以上两行则说明i，j都已经不满足while从句
        if(i < j) swap(q[i],q[j]); //确认此时的i依然小于j（重合便不再操作）
    }
    quick_sort(l,j);//对左区间递归
    quick_sort(j+1,r);//对右区间递归
}
//输入 5 
//1 2 2 2 5
//不会死循环是因为dowhile是先执行再判断是否满足条件的
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&q[i]);

    sort(q,q+n);

    for(int i=0;i<n;i++){cout<<q[i]<<" ";};

    return 0;
}

~~虽然甚至没有自带的快排快~~
还是传上来了。

还是一样的题目，写一下

归并排序

对比快排更加稳定，适合大数据量

并不重要…

#include  <bits/stdc++.h>
using namespace std;
const int MAXN = 1e8 + 10;
int n, a[MAXN], T[MAXN];
void Mergesort(int l, int r) {
    if (l == r) return; //区间内只有一个数，返回
    int mid = l + r >> 1; //相当于(l + r) / 2
    Mergesort(l, mid); //递归左半部分
    Mergesort(mid + 1, r); //递归右半部分
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) //合并
        if (a[i] <= a[j]) T[k++] = a[i++];
        else T[k++] = a[j++];
    while (i <= mid) T[k++] = a[i++];
    while (j <= r) T[k++] = a[j++];
    for (int q = l; q <= r; q++) a[q] = T[q]; //转移
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    Mergesort(1, n);
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

如果忘记了记得看这个

至于冒泡和桶排，便没什么必要了吧