常用的排序算法：快速排序、归并排序，堆排序、计数排序（较常用）

排序方法分类

基于比较的方法

• 快速排序
• 归并排序
• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 堆排序

基于非比较（桶）的排序方法

• 计数排序
• 桶排序
• 基数排序

稳定性

稳定排序：冒泡、归并、插入 + 基于非比较的排序（计数、桶、基数） 不稳定排序：除了稳定的就是不稳定的，快排、选择、希尔、堆排

八大排序算法代码模板，桶排序实现方式比较多，基数排序基本不用，就不实现啦~ 注意：这里堆排序下标从 1 开始处理比较方便。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

// 快速排序：找一个基准值 x，将比 x 大的数放到 x 的后面，比 x 小的数放到 x 的前面，递归左边部分和右边部分
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;

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

    quickSort(nums, l, j), quickSort(nums, j + 1, r);
}

// 归并排序：先向下拆分，直到每个区间只剩一个元素，然后两两区间进行两路归并排序，再往上合并，最后将排序后的数组放到原数组中。

void mergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l >= r) return;

    int mid = l + r >> 1;
    mergeSort(nums, l, mid, tmp), mergeSort(nums, mid + 1, r, tmp);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) tmp[k ++ ] = nums[i ++ ];
        else tmp[k ++ ] = nums[j ++ ];
    }

    while (i <= mid) tmp[k ++ ] = nums[i ++ ];
    while (j <= r) tmp[k ++ ] = nums[j ++ ];

    for (int i = l, k = 0; i <= r; i ++ ) nums[i] = tmp[k ++ ];
}

// 冒泡排序：比较相邻两个元素的大小，将最大的元素放到数组的末尾，每次排序可以确定一个值的位置，最多经过 n - 1 趟排序即可排序完成

void bubbleSort(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i ++ ) {
        for (int j = 0; j < nums.size() - i - 1; j ++ ) {
            if (nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);
        }
    }
}

// 选择排序：每次选择一个较小值从前往后依次放，直到所有数都放到了该放的位置

void selectSort(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i ++ ) {
        int minIndex = i;
        for (int j = i + 1; j < nums.size(); j ++ ) {
            if (nums[j] < nums[minIndex])
                minIndex = j;
        }

        if (minIndex != i)
            swap(nums[minIndex], nums[i]);
    }
}

// 插入排序：维护两个区间，一个是已排序区间， 初始状态只有第一个数，另一个是未排序区间，每次从未排序区间中取一个数 x，从已排序区间中找到小于 x 的位置 j，然后将其放到 j + 1 位置上，直到所有数都插入完成。

void insertSort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i ++ ) {
        int x = nums[i], j = i - 1;
        while (j >= 0 && nums[j] >= x) {
            nums[j + 1] = nums[j];
            j -- ;            
        }
        nums[j + 1] = x;
    }
}

// 插入排序 2：和方法 1 思想是一样的，区别就是：不采用向后移动元素的方式插入，而是用交换的方式找到这个数应该放的位置。

void insertSort2(vector<int>& nums) {
    for (int i = 1; i < nums.size(); i ++ ) {
        for (int j = i - 1; j >= 0 && nums[j] >= nums[j + 1]; j -- ) 
            swap(nums[j], nums[j + 1]);
    }
}

// 希尔排序：对比 [插入排序 2] 记忆；首先将数组进行分组，组内再用插入排序进行排序，最后合并起来就是排序后的结果。

void shellSort(vector<int>& nums) {
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i ++ ) {
            for (int j = i - gap; j >= 0 && nums[j] >= nums[j + gap]; j -= gap) {
                swap(nums[j], nums[j + gap]);
            }
        }
    }
}

// 堆 - 向下调整：找出当前节点 u 和左右儿子值的的最大者 t，如果当前节点 u 不是最大值，那么将 u 和 t 的值交换，此时节点 u 是堆顶且是最大值，递归向下调整节点 t

void down(vector<int>& nums, int n, int u) {
    int t = u, left = u * 2, right = u * 2 + 1;
    if (left <= n && nums[left] > nums[t]) t = left;
    if (right <= n && nums[right] > nums[t]) t = right;
    if (u != t) {
        swap(nums[u], nums[t]);
        down(nums, n, t);
    }
}

// 堆排序 - 下标从 1 开始
void heapSort(vector<int>& nums, int size) {
    int n = size;
    // 建堆
    for (int i = n / 2; i >= 1; i -- ) down(nums, n, i);

    // 堆排序：每次将堆顶和待排序区间的最后一个元素交换，然后新的堆顶再向下调整
    for (int i = 1; i <= size; i ++ ) {
        swap(nums[1], nums[n]);
        n -- ;
        down(nums, n, 1);
    }
}

// 堆排序 - 下标从 0 开始
/*void down(vector<int>& nums, int n, int u) {
    int t = u, left = u * 2, right = u * 2 + 1;
    if (left <= n && nums[left] > nums[t]) t = left;
    if (right <= n && nums[right] > nums[t]) t = right;
    if (u != t) {
        swap(nums[u], nums[t]);
        down(nums, n, t);
    }
}

void heapSort(vector<int>& nums, int size) {
    int n = size;

    // 建堆
    for (int i = n / 2; i >= 1; i -- ) down(nums, n, i);

    // 堆排序
    for (int i = 1; i <= size; i ++ ) {
        swap(nums[1], nums[n]);
        n -- ;
        down(nums, n, 1);
    }
}*/

// 计数排序：开数组数值范围的桶，每个元素一个桶，每个桶记录每个元素出现的次数，最后遍历桶输出

void countingSort(vector<int>& nums) {
    int n = nums.size();
    // 开一个桶，假设最大值是 100
    vector<int> cnt(101, 0);

    // cnt 记录每个元素出现的次数
    for (int i = 0; i < n; i ++ ) cnt[nums[i]] ++ ;

    for (int i = 0, k = 0; i <= 100; i ++ ) {
        // 将桶里的数放到原数组中
        while (cnt[i]) {
            nums[k ++ ] = i;
            cnt[i] -- ;
        }
    }
}

int main()
{
    /* 测试数据
        2
        5
        5 2 3 1 4
        10
        6 8 1 3 2 5 9 7 4 0
    */
    int T;
    cin >> T;
    while (T -- ) {
        int n;
        cin >> n;

        vector<int> nums(n);
        for (int i = 0; i < n; i ++ ) cin >> nums[i];

        // quickSort(nums, 0, nums.size() - 1);
        // vector<int> tmp(n);
        // mergeSort(nums, 0, nums.size() - 1, tmp);
        // bubbleSort(nums);
        // selectSort(nums);
        // insertSort(nums);
        // insertSort2(nums);
        // shellSort(nums);

        // vector<int> nums(n + 1);
        // for (int i = 1; i <= n; i ++ ) cin >> nums[i];
        // heapSort(nums, n); // 堆排序下标从 1 开始比较好写，其他排序从 0 开始
        // for (int i = 1; i <= n; i ++ ) cout << nums[i] << " ";

        // countingSort(nums);

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

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com