求支持~

导语

在写大部分题目时需要排序，感觉sort()函数已经够用了，为什么我们还要手写排序算法？

排序是最基本最常见的算法，在编程的过程中会发现许多算法都是基于排序算法的转变，并且许多算法离不开排序。

所以，在此奉上排序经典算法集合一份（以下有序的定义均为单调不下降）：

冒泡排序

一个指针重复地遍历过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。

遍历元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

//脚踏实地，一个一个地挪走
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; //数据范围依题目而定
int n; //数组长度
int q[N]; //待排序数组

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &q[i]);

    for (int i = 1; i <= n; i ++) //能够证明最多进行n次操作一定有序，见文末补充
    {
        //遍历前
        bool flag = true; //记录遍历区域内元素是否有序
        //遍历中
        for (int j = 1; j <= n - i; j ++) //j指针走访下标由1到n-i的所有元素（因为j+1刚好走到n-i+1）
            if (q[j] > q[j + 1]) //若无序
            {
                swap(q[j], q[j + 1]); //则交换
                flag = false; //记录无序的情况
            }
        //遍历后
        if (flag) break; //如果遍历后发现区域内没有无序，即有序，则退出。
    }

    for (int i = 1; i <= n; i ++) printf("%d ", q[i]);

    return 0;
}

插入排序

打个比方：桌上有一副扑克牌，你拿起一张牌以后要与你手中已有的牌一一比较，最终确定位置。

插入排序也是这样，只不过在上面的例子中“桌面”和“你的手”是两个不同的数组，

而算法中使用同一个数组，所以可能会有微小差别。

//精挑细选，插队也要有讲究
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; //数据范围依题目而定
int n; //数组长度
int q[N]; //待排序数组

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &q[i]);

    for (int i = 2; i <= n; i ++) //默认q[1]是有序的，毕竟比它小的只要放在它前面就行了
    {
        int tmp = q[i]; //存下待插入的元素
        int k = 1; //从下标1的位置开始比较

        while (q[k] < tmp && k < i) k ++; //若“插在这里就会无序！”或者“这个位置有人了！”，那么就找下一个
        for (int j = i - 1; j >= k; j --) q[j + 1] = q[j]; //有人要插队，排在后面的人就要赶紧让出空位
        q[k] = tmp; //插入
    }

    for (int i = 1; i <= n; i ++) printf("%d ", q[i]);

    return 0;
}

选择排序

第一次从待排序的数据元素中选出最值，存放在序列的起始位置，然后再从剩余的未排序元素中找到最值，

然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

在下面的代码中将有序与无序的元素都放入一个数组内，与描述会有微小差异。

//取最小值，swap一下排在后
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; //数据范围依题目而定
int n; //数组长度
int q[N]; //待排序数组

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &q[i]);

    for (int i = 1; i <= n; i ++)
    {
        int k = i; //k存储最值的下标
        for (int j = i + 1; j <= n; j ++) //前i-1个已经有序，i是待插入的位置，所以最值要从i+1开始找
            if (q[k] > q[j]) k = j; //不断更新最值
        swap(q[i], q[k]); //将q[k]的值交换至i的位置
    }

    for (int i = 1; i <= n; i ++) printf("%d ", q[i]);

    return 0;
}

快速排序

这是对冒泡排序的一种改进算法。具体流程如下：

1. 选择一个分界值
2. 通过双指针与交换，将数组分为小于和大于等于分界值的两部分，分别在数组的左边和右边
3. 对于左右两个区间，每个区间也做上述操作，没错，这个算法使用的是分治的思想和递归的操作。
4. 当递归细化到排序区间长度为1时，即将1个元素“排序”，则直接退出。

//分治，递归与双指针
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010; //数据范围依题目而定
int n; //数组长度
int q[N]; //待排序数组

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return; //对一个元素“排序”，简直可笑，赶紧退出

    int x = q[l], i = l - 1, j = r + 1;
    //这里的分界值设为q[l]，指针i，j从数组两端出发

    while (i < j)
    {
        do i ++; while (q[i] < x); //q[i]站对了，那就不要动，继续往下看
        do j --; while (q[j] > x); //q[j]站对了，那就不要动，继续往下看
        if (i < j) swap(q[i], q[j]);
        //出现站错位置的q[i], q[j]，那就让它俩换一下
    }

    quick_sort(q, l, j); //对左区间，即小于x的部分排序
    quick_sort(q, j + 1, r); //对右区间，即大于等于x的部分排序
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++) printf("%d ", q[i]);

    return 0;
}

归并排序

这是一种基于归并操作的算法，具体流程如下：

1. 申请空间，一个用来存归并前的元素，一个用来存归并后的元素
2. 两个指针，从两个未归并区间的左端开始进行归并
3. 比较两个指针所指的元素，取最值放入归并后数组内，并将指针移动到下一位置
4. 重复3，直到某一指针越界，即这一区间已全部归并
5. 将另一区间剩下的元素一股脑放入归并后数组
6. 将归并后数组复制到归并前数组，为下一轮归并做准备

//从最细化开始，逐层合并
#include <iostream>

using namespace std;

const int N = 1010; //数据范围依题目而定
int n; //数组长度
int q[N], tmp[N]; //待归并数组 和 已归并数组

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return; //对一个元素“排序”，简直可笑，赶紧退出

    int mid = (l + r) >> 1; //将整个数组一分为二，待两部分各自排完序后归并

    merge_sort(q, l, mid), merge_sort(q, mid + 1, r); //左右两个区间各自排序

    int k = 0, i = l, j = mid + 1; //k记录当前元素应放入tmp的位置，i, j两个指针从两个区间左端出发

    while (i <= mid && j <= r) //只要没有指针越界
    {
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];

        //取最值放入tmp指针后移
    }

    //将剩下元素一股脑塞进tmp
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];

    //tmp复制到q，准备下一轮归并
    for (int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

int main()
{
    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;
}

补充

1. 为什么冒泡排序中，最多n-1次操作就可以使数组有序：
   说不清楚，那就直接模拟吧：
   有数组 $q=3,2,1$ ，此时数组中最大值为 $3$ ，
   第一次遍历后， $q=2,1,3$ ，我们发现 $3$ 已经到达了它应到达的下标为n的位置，
   所以接下来，我们便不用考虑它了，只须将 $1~n-1$ 的区域变得有序就行了，此时这一区域的最大值为 $2$ 。
   第二次遍历后， $q=1,2,3$ ，我们发现 $2$ 也到达了它应到达的下标为n-1的位置。
   此时数组已有序，退出。
   这样一来，我们发现每一次遍历后，遍历区域内的最大值便会自动来到区域右边界，下一次遍历时就不需要考虑了。
2. 为什么坚持创作：
   往大了说，是因为内心对C++、对编程的热爱，希望更多人能懂它、理解它。
   往小了说，是为了提升阅读量，毕竟人非圣贤，总是有那么点自利心的嘛~~~
   您的支持是创作的最大动力，点个赞可不可以~【憨笑】