等一下，你要是初级排序都没弄明白先看这个,考研要点之初级排序的总结:

https://www.acwing.com/file_system/file/content/whole/index/content/4239728/

希尔排序（Shell Sort）

出名的原因是当年第一个最坏时间复杂度小于O(n^2),实现的比较好的是O(n^5/4),这个排序效率比较鸡肋,不如咱往后会讲到的其他排序

简述思想:

假设我们有若干个元素,先将所有元素分组
分成若干组,每一组内下标构成等差数组,
而等差数列的公差可以理解为增量,
公差可以取2/n,然后对所有元素进行分组,
每一组内用简单插入排序进行每次排序,
然后,第二次排序,将公差定成4/n,再进行分组,
并对每一组内继续插入排序排好,
第三次再把公差定位n/8,重复上面操作,
.....
这里我们假设n=8,那么第三次公差就是1,也就是我们希尔排序最后一个公差一定是1,也就是全部元素都在同一组内,最后,排完之后,整个序列一定是有序的,因为我们的增量(公差)为1

增量选择方式证明:

如果我们设置为:
n/2, n/4, n/8.....那么最坏时间复杂度为O(n^2),但在上机实际运行效率还不错
如果我们设置为:
n/3, n/(3^2), n/(3^3).....
这组增量序列,可以证明最坏时间复杂度是O(n√n)
这个增量序列，你可以不用怀疑，已被科学证明，感兴趣自己了解，这里不展开，考研不考证明

这里有不懂的小明就要问我了，为什么分完组要用插入排序？

这是因为插入排序对于部分有序的序列时间效率很高，甚至超过快速排序，同时C++库sort里面不是纯快排，而是快排和插排的结合，比如快速排序最后分治出的区间长度小于28的时候，每一部分都建立相对有序因此用一遍插排实现加速

讲得够多了，结合代码：

void shell_sort()   //希尔排序
{
    for (int d = n / 2; d ; d /= 2) 
    //设置每一轮分组的增列公差
    {
        for (int start = 0; start < d; start ++) 
        //按公差d来分出每一组等差数列
        {
            for (int i = start + d; i < n ;i += d)
            //对分出的每一组等差数列进行插排
            {
                int t = q[i], j = i;
                while(j > start && q[j - d] > t)
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

上面的公差感觉效率不高？

那就用科学证明的最优公差再写一遍：

void shell_sort()   //希尔排序
{
    //注意：这里我们要特判2，保证最后一个增量是1
    for (int d = n / 3; d ; d = d == 2 ? 1 : d / 3) //设置每一轮分组的增列公差
    {
        for (int start = 0; start < d; start ++) //
        {
            for (int i = start + d; i < n ;i += d)
            {
                int t = q[i], j = i;
                while(j > start && q[j - d] > t)
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

分析：希尔的时间复杂度比较难分析，不做展开

1. 时间复杂度O（(n^(3/2)）(注意：用科学证明的增量序列最坏是低于O(n^2)，但用n/2…最坏还是O(n^2))
2. 空间复杂度O(1)
3. 不稳定,因为它涉及到分组的过程，
   举个栗子：
   1 3 2 2 .....
   -> 1 2…分一组
   -> 3 2…分一组
   分组排完序，就可能把第四个2分到第二个位置上，这样就跟第三个2的相对位置不一样了

快速排序（Quick sort）

不用怀疑，直接望文生义，没错！快速就是快，目前最快的排序算法。

喜欢生动点理解，推荐你去看《啊哈，算法》，我就简单粗暴点了：

策略：
①找分界点（20多年前写法保留x，现在的写法没必要都一样没区别）
②划分成2段：用双指针双边遍历并按要求进行判断换位，直到相遇就结束，让左边都是<=x,右边都是>=x（算法当中的分治思想+双指针算法思想）
③递归排左右两边（别告诉我递归，你不会！）

天啊，还有人问我第③步递归证明其正确性，原则就是数学归纳法，好吧，不再展开叙述

这玩意考研出不出不知道，面试官爱问的算法，感兴趣给大家扩展一下面试题：快排支持链式存储,题目链接： https://www.acwing.com/problem/content/1453/

上代码：

void quick_sort(int l , int r)  //快速排序
{
    if(l >= r)  return;
    //划分讲策略，划分不好导致递归层数太多，
    //适得其反,取左右端点数据卡你就不好过，一般取中间
    int i = l - 1, j = r + 1, x = q[(l + r) / 2];

    while (i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j)   swap(q[i],q[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

说实话，你要真理解不了，或者按理解自己去推整个代码老容易出错，那我建议你直接背下来吧，不丢人！

效率分析很特殊：

划分的过程，一共会划分logn层，所以平均复杂度就是O(nlogn),但最坏情况也是划分n层，时间复杂度直接怼到O(n^2).
1. 时间复杂度：最好是O(nlogn)，平均也是O(nlogn)，最坏是O(n^2)
2. 空间复杂度：因为要用到递归会用到系统栈，最坏是O(n^2),但这种情况，所以是O(logn)
3. 不稳定,整个做划分的过程

又有不懂的小明问我了，既然快排最坏也是O(n^2)那为啥称之为目前最快的排序算法，我想说的是我安排八股文写的，但实际使用过程当中，遇到最坏的情况，就像买彩票中大奖一样，自嗨，它和哈希同理实际操作不考虑最坏情况，所以一般来说只看平均情况

堆排序

预备知识：数据结构之堆（或优先队列），完全二叉树，分为小根堆和大根堆，简单而言就是根>=所有儿子就是大根堆，说严谨点就是每个结点大于等于左右两个结点的值，就是大根堆，小根堆同理

敲黑板：

堆的存储：堆一般用顺序存储，少用链式存储（比较麻烦效率一般会下降），而且顺序存储支持随机索引，都是从数组的下标为1开始的将整棵树映射到数组里面，这样根节点为x，左儿子为2x，右儿子为2x+1

堆的创建：从完全二叉树的最下面开始从下往上递归去创建，那么我们每一次维护根结点都是最多logn层的向下移动也就是所谓的down(x)函数,那么其时间复杂度就是O(logn),我们在写的时候，只需要从倒数第二层开始维护即可，总的来说遍历n/2次每一次都是logn,所以整个建堆的时间复杂度O(nlogn)

我们可以假设一颗完全二叉树有四层从下往上依次是n/2, n/4 * 2, n/8 * 3, n/16 * 4 ; 然后我们构建成高中学过的等差数列为

(n/(2^1)1 + n/(2^2)2 + .....)
=n(1/(2^1) + 2/(2^2) + 3/(2^3) + ....)
我们把括号内设为S,然后构建2S和2S-S最后推得
S=1 + 1/2 + 1/4 + 1/8 +.... = 2
所以原式=2*n

堆的删除：也就是删除堆顶，那么我们同时就要将最后一个元素放到根节点（因为除掉最后一个元素很容易），并删除它原来结点，最后，对这个根节点进行down()操作即可，维护整个堆

这时候又有不懂得小明问我了，为啥删除要搞这么麻烦呢？原因很简单，就像大哥张牧之想除掉黄四郎很难，那就把他的替身带到人民群众最前面进行斩首，一个道理，我们之间把最后的结点放到根节点最后维护一下整个堆就可以了

讲了这么多，带入到代码里面思考

//堆要维护一个sz，表示堆里面时刻有多少个元素，实时更新全局变量
int sz;

void down(int u)
{
    int t = u;
    if(u * 2 <= sz && q[u * 2] > q[t])  t = u * 2;
    if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t])  t = u * 2 + 1;
    if(u != t)
    {
        swap(q[u], q[t]);
        down(t);
    }
}

void heap_sort()
{
    sz = n;
    for(int i = n / 2; i ; i --)    down(i);

    for (int i = 0; i < n - 1;i ++)
    {
        swap(q[1], q[sz]);  //把最后一个元素放到最后
        sz --;              //删掉最后一个元素
        down(1);
    }
}

分析：

1. 时间复杂度：最好情况，最坏情况平均情况都是O(nlogn)
2. 空间复杂度：O(logn)
3. 不稳定，每次会把最后一个换掉第一个所以容易改变相等元素的 相对位置

归并排序

也是跟快排一样基于分治的算法

简述策略：

1. 递归分割两段 [L,mid], [mid+1,R] （正确性证明源于数学归纳法）
2. 二路归并，将第一步递归完两个相对有序的序列进行双指针算法合并（两个指针分别指向两段相对有序的数列第一位往后进行二路归并）

前面已经说的口干舌燥了，不哔哔了直接敲键盘

//辅助数组
int w[N];

void merge_sort(int l, int r)  // 归并排序
{
     if(l >= r)  return;
    //先分割
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    //再二路归并
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if(q[i] <= q[j]) w[k ++] = q[i ++];
        else    w[k ++] = q[j ++];
    while (i <= mid)    w[k ++] = q[i ++];//把左区间残余的归入
    while (j <= r)      w[k ++] = q[j ++];//把右区间残余的归入,这波叫做捡漏
    //辅助数组归并完事就要物归原主，更新原数组
    for (i = l, j = 0;j < k;i ++, j ++) q[i] = w[j];
}

分析：

1. 时间复杂度：O(nlogn)
2. 空间复杂度：O(n)
3. 稳定，不详细讲了，三两句讲一下，例如两个相等的元素在两个区间，我们判断标准时<=，符合的话优先讲左边的先归入，那么就不影响整体了，累了累了，不过多叙述了，对于笔试够用了

把上面所有代码整个一下，供大家参考

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;

int n;
int q[N];



void shell_sort()   //希尔排序
{
    //注意：这里我们要特判2，保证最后一个增量是1
    for (int d = n / 3; d ; d = d == 2 ? 1 : d / 3) //设置每一轮分组的增列公差
    {
        for (int start = 0; start < d; start ++) //
        {
            for (int i = start + d; i < n ;i += d)
            {
                int t = q[i], j = i;
                while(j > start && q[j - d] > t)
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}

void quick_sort(int l , int r)  //快速排序
{
    if(l >= r)  return;
    //划分讲策略，划分不好导致递归层数太多，适得其反
    int i = l - 1, j = r + 1, x = q[(l + r) / 2];

    while (i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j)   swap(q[i],q[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

//堆要维护一个sz，表示堆里面时刻有多少个元素，实时更新全局变量
int sz;

void down(int u)
{
    int t = u;
    if(u * 2 <= sz && q[u * 2] > q[t])  t = u * 2;
    if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t])  t = u * 2 + 1;
    if(u != t)
    {
        swap(q[u], q[t]);
        down(t);
    }
}

void heap_sort()
{
    sz = n;
    for(int i = n / 2; i ; i --)    down(i);

    for (int i = 0; i < n - 1;i ++)
    {
        swap(q[1], q[sz]);  //把最后一个元素放到最后
        sz --;              //删掉最后一个元素
        down(1);
    }
}

//辅助数组
int w[N];

void merge_sort(int l, int r)  // 归并排序
{
     if(l >= r)  return;
    //先分割
    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    //再二路归并
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if(q[i] <= q[j]) w[k ++] = q[i ++];
        else    w[k ++] = q[j ++];
    while (i <= mid)    w[k ++] = q[i ++];//把左区间残余的归入
    while (j <= r)      w[k ++] = q[j ++];//把右区间残余的归入,这波叫做捡漏
    //辅助数组归并完事就要物归原主，更新原数组
    for (i = l, j = 0;j < k;i ++, j ++) q[i] = w[j];
}


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

    // shell_sort();
    // quick_sort(0, n - 1);
    // heap_sort(); //注意用堆排序需要将输入输出改成从下标为1开始
    merge_sort(0, n - 1);

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

你以为8大排序学完笔试就没问题了，还没完！这仅仅只是内部排序！

考研要点之特殊排序的总结：
https://www.acwing.com/blog/content/16518/