所有常见排序算法实现模板(详细注释)

声明：感谢gpt codex提供的大部分注释

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

// 定义数组和变量
int a[100001], n; // a数组用于存储待排序的元素，n表示元素个数
const int N = 1e5; // 常量N用于定义数组大小
int cnt[N], b[100001]; // cnt数组用于计数排序，b数组用于临时存储排序结果
int minn = 0x3f3f3f3f, maxn = 0; // minn和maxn用于存储数组中的最小值和最大值
vector<int> tmp; // tmp向量用于临时存储归并排序中的中间结果

// 选择排序
void selection_sort() 
{
    for(int i = 1; i < n; i++) // 遍历数组，每次选择最小的元素放到合适的位置
    {
        int ith = i; // 记录当前最小元素的位置
        for(int j = i + 1; j <= n; j++) // 在未排序部分寻找最小元素
        {
            if(a[ith] > a[j]) ith = j; // 更新最小元素的位置
        } 
        swap(a[i], a[ith]); // 将找到的最小元素与当前元素交换
    }
}

// 冒泡排序
void bubble_sort()
{
    bool flag = true; // 标志位，用于检测是否发生交换
    while(flag)
    {
        flag = false; // 假设本次循环没有发生交换
        for(int i = 1; i < n; i++) // 遍历数组
        {
            if(a[i] > a[i + 1]) // 如果前一个元素大于后一个元素
            {
                flag = true; // 发生交换，标志位置为true
                swap(a[i], a[i + 1]); // 交换两个元素
            }
        }
    }
}

// 插入排序
void Insertion_sort()
{
    for(int i = 2; i <= n; i++) // 从第二个元素开始遍历
    {
        int j = i - 1, t = a[i]; // j指向当前元素的前一个位置，t存储当前元素的值
        // 将当前元素插入到已排序部分的合适位置
		while(j>0&&a[j]>/*a[i]*/t) //a[i]会变 
        {
            a[j + 1] = a[j]; // 向后移动元素
            j--; // 向前移动指针
        }
        a[j + 1] = t; // 插入当前元素到合适位置
    }
}

// 计数排序
void Counting_sort()
{
    memset(b, 0, sizeof(b)); // 初始化b数组为0
    for(int i = 1; i <= n; i++) 
    {
        minn = min(a[i], minn); // 更新最小值
        maxn = max(a[i], maxn); // 更新最大值
        cnt[a[i]]++; // 统计每个元素出现的次数
    }
    for(int i = minn + 1; i <= maxn; i++) cnt[i] += cnt[i - 1]; // 计算累积计数
    for(int i = n; i >= 1; i--) b[cnt[a[i]]--] = a[i]; // 根据累积计数将元素放入b数组
    memcpy(a, b, sizeof(b)); // 将b数组复制回a数组
}

// 基数排序
void radix_sort()
{
    for(int i = 1; i <= n; i++) maxn = max(a[i], maxn); // 找到最大值
    int digit = 0; // 记录最大值的位数
    while(maxn)
    {
        maxn /= 10; // 计算位数
        digit++;
    }
    int base = 1; // 基数
    for(int i = 1; i <= digit; i++) //共digit位，每一位进行计数排序 
    {
        memset(cnt, 0, sizeof(cnt)); // 初始化计数数组
        for(int i = 1; i <= n; i++) cnt[(a[i] / base) % 10]++; // 统计每个位上的数字出现次数
        for(int i = 1; i < 10; i++) cnt[i] += cnt[i - 1]; // 计算累积计数
        for(int i = n; i >= 1; i--) b[cnt[(a[i] / base) % 10]--] = a[i]; // 根据累积计数将元素放入b数组
        memcpy(a, b, sizeof(b)); // 将b数组复制回a数组
        base *= 10; // 基数乘以10
    }
}

vector<int> bucket[N];
void bucket_sort()
{
    for(int i=1;i<=n;i++)
    {
        maxn=max(a[i],maxn);
        minn=min(a[i],minn);
    }
    int size=(maxn-minn)/n+1;//+1:保证桶可装 /n：尽量均匀
    int cnt=(maxn-minn)/size+1;//+1:保证有桶
    for(int i=1;i<=n;i++) bucket[(a[i]-minn)/size].push_back(a[i]);
    for(int i=0;i<cnt;i++) 
    {
        sort(bucket[i].begin(),bucket[i].end());
        for(int v:bucket[i]) cout<<v<<' ';
    }
}

// 快速排序的三种分区方法 内部局部排序
int hoare_sort(int l, int r) // 左右指针法
{
    int key = l; // 选择第一个元素作为基准
    int base = a[key]; // 基准值
    while(l < r)
    {
        while(l < r && a[r] >= base) r--; // 从右向左找到第一个小于基准的元素
        while(l < r && a[l] <= base) l++; // 从左向右找到第一个大于基准的元素
        swap(a[l], a[r]); // 交换这两个元素
    } 
    swap(a[l], a[key]); // 将基准元素放到合适位置
    return l; // 返回基准位置
}

int hole_sort(int l, int r) // 挖坑法
{
    int base = a[l]; // 选择第一个元素作为基准
    while(l < r)
    {
        while(l < r && a[r] >= base) r--; // 从右向左找到第一个小于基准的元素
        a[l] = a[r]; // 将该元素填入左边的坑
        while(l < r && a[l] <= base) l++; // 从左向右找到第一个大于基准的元素
        a[r] = a[l]; // 将该元素填入右边的坑
    }
    a[l] = base; // 将基准元素放到合适位置
    return l; // 返回基准位置
}

int qh_sort(int l, int r) // 前后指针法
{
    int base = a[l]; // 选择第一个元素作为基准
    int prev = l, cur = l + 1; // 前后指针
    while(cur <= r)
    {
        while(a[cur] <= base && ++prev != cur) swap(a[prev], a[cur]); // 如果当前元素小于等于基准，且前后指针不重合，交换
        cur++; // 后指针右移
    }
    swap(a[prev], a[l]); // 将基准元素放到合适位置
    return prev; // 返回基准位置
}

void tridiv_sort(int &l, int &r) // 三路划分
{
    int base = a[l]; // 选择第一个元素作为基准
    int cur = l + 1; // 当前指针
    while(cur <= r)
    {
        if(a[cur] < base) swap(a[l++], a[cur++]); // 如果当前元素小于基准，交换到左边
        // 如果当前元素大于基准，交换到右边
		else if(a[cur] > base) swap(a[r--], a[cur]); //cur不++:原来的a[r]未处理,不跳过
        else cur++; // 如果当前元素等于基准，指针右移
    }
}

// 快速排序
void quick_sort(int l, int r)
{
    if(l >= r) return; // 如果区间长度为0或负，返回
    /*int key=qh_sort(l,r);等三种内部局部排序函数
    quick_sort(l,key-1);
    quick_sort(key+1,r);*/
    int L = l, R = r; // 保存初始区间
    tridiv_sort(l, r); // 三路划分
    quick_sort(L, l - 1); // 递归排序左区间
    quick_sort(r + 1, R); // 递归排序右区间
}

// 归并排序
void merge_sort(int l, int r)
{
    if(l == r) return; // 如果区间长度为1，返回
    int mid = l + ((r - l) >> 1); // 计算中点
    merge_sort(l, mid); // 递归排序左区间
    merge_sort(mid + 1, r); // 递归排序右区间
    tmp.clear(); // 清空临时向量
    int i = l, j = mid + 1; // 左右指针
    while(i <= mid && j <= r) // 合并两个有序区间
    {
        if(a[i] > a[j]) tmp.push_back(a[j++]); // 如果左区间元素大于右区间元素，将右区间元素放入临时向量
        else tmp.push_back(a[i++]); // 否则将左区间元素放入临时向量
    }
    while(i <= mid) tmp.push_back(a[i++]); // 将剩余左区间元素放入临时向量
    while(j <= r) tmp.push_back(a[j++]); // 将剩余右区间元素放入临时向量
    for(int k = l; k <= r; k++) a[k] = tmp[k - l]; // 将临时向量中的元素复制回原数组
}

// 堆排序
void shift(int p, int end) // 调整堆
{
    while((p << 1) <= end) // 如果有左孩子
    {
        int lc = p << 1; // 左孩子
        int rc = p << 1 | 1; // 右孩子
        if(a[lc] < a[rc] && rc <= end) lc = rc; // 如果右孩子存在且大于左孩子，选择右孩子
        if(a[p] < a[lc]) swap(a[lc], a[p]); // 如果父节点小于孩子节点，交换
        else break; // 否则调整结束
        p = lc; // 继续向下调整
    }
}

void heap_sort()
{
    for(int i = n / 2; i; i--) shift(i, n); // 构建大顶堆
    for(int i = n; i; i--) // 排序
    {
        swap(a[1], a[i]); // 将堆顶元素与最后一个元素交换
        shift(1, i - 1); // 调整堆
    }
}

// 希尔排序
void shell_sort()
{
    int gap = n; // 初始间隔
    while(gap)
    {
        gap /= 2; // 间隔减半
        for(int i = gap + 1; i <= n; i++) // 对每个间隔进行插入排序
        {
            int t = a[i], j = i - gap; // 当前元素和前一个间隔元素
            while(j >= 1 && a[j] > t) // 插入排序
            {
                a[j + gap] = a[j]; // 向后移动元素
                j -= gap; // 向前移动指针
            }
            a[j + gap] = t; // 插入当前元素到合适位置
        }
    }
}

int main()	
{
    ios::sync_with_stdio(0); // 关闭同步流
    cin.tie(0); cout.tie(0); // 解绑输入输出流
    cin >> n; // 输入元素个数
    for(int i = 1; i <= n; i++) cin >> a[i]; // 输入元素
    //selection_sort();
    //bubble_sort();
    //Insertion_sort();
    //Counting_sort();
    //radix_sort();
    //quick_sort(1,n);
    //merge_sort(1,n);
    //bucket_sort();
    //heap_sort();
    //shell_sort();
    for(int i = 1; i <= n; i++) cout << a[i] << ' '; // 输出排序结果
    return 0;
}