[数据结构与算法]排序(堆排序，快速排序，归并排序)

前言：如果内容不全，说明还没复习到，复习时会陆续更新。

堆排序?

建议初学者先去看这两篇文章，写的很好，保姆级别教学。此篇只是加入了些个人理解以及代码模板供自己复习使用，具体细节太多了，本人时间和水平有限，就不在此写具体实现过程了。有的地方可能说的不对，欢迎指正。

文章链接：

堆排序——深入浅出（图解）

堆排序

?

前置知识

1.堆：堆是一种数据结构，一种叫做完全二叉树的数据结构。

2.堆的性质：这里我们用到两种堆，其实也算是一种。

大顶堆：每个节点的值都大于或者等于它的左右子节点的值。

小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

3.完全二叉树

（1）父节点编号 = （该节点编号 - 1）/2

（2）左儿子编号 = 2i+1（根编号为0的情况）

（3）右儿子编号 = 2i+2（根编号为0的情况），如果根编号为1，左二子 = 2i，右儿子 = 2i+1

（4）完全二叉树最后一个非叶子节点的编号 = n（节点个数）/2

排序过程

分为两个部分，构造初始堆和重建堆。时间复杂度也不同，构造初始堆的时间复杂度为O(n)，重建堆的时间复杂度为O(nlogn)，空间复杂度O(n)。

先附上一张搬运的经典过程图像

?

构造初始堆，即将无序的完全二叉树构建成一个大（小）根堆。

重建堆，即每次取出堆顶元素后将最后一个叶子节点转移到堆顶，再将其下推的过程。

因为是完全二叉树，所以直接用数组来存，这里方便起见，使用1作为根。实现过程直接看代码。

?

/*利用完全二叉树进行的排序，满足一定条件的完全二叉树就是堆
时间复杂度：构造初始堆O(n),重建堆的时间复杂度O(nlogn)

该模板属于离线模板，不支持后序添加新数据，实现此功能请转优先队列
此模板为小顶堆
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<string>
using namespace std;
typedef long long int ll;

const int MAX_N = 1e5+10;
int tree[MAX_N];//堆(完全二叉树)
//向下调整
inline void siftdown(int now,int n)
{
    //当节点有儿子时
    while((now<<1)<=n){
        int temp = now;
        //先判断左儿子（因为没法保证有右儿子）
       if(tree[now] > tree[now<<1]) temp = now<<1;
       //接着判断右儿子,首先得保证有右儿子
       if((now<<1|1) <= n)
           if(tree[temp] > tree[now<<1|1])
                temp = now<<1|1;
       if(temp != now){
           swap(tree[now],tree[temp]);
           //如果进行了交换，跟新now,便于下一步继续下推
           now = temp;
       }else{
           //如果没有进行交换，说明已经不用下推
           break;
       }
    }
}

//建立初始堆
void creat(int n)
{
    //从第一个非叶子节点到第一个节点依次向上调整
    for(int i = n/2;i>=1;i--){
        siftdown(i,n);
    }
}


//拿出堆顶元素
int getTop(int &n)
{
    int temp;
    temp = tree[1];//记录堆顶元素
    tree[1] = tree[n];//将最后一个节点移到堆顶
    n--;//堆中元素个数-1
    siftdown(1,n);//下推
    return temp;
}

int main()
{
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>tree[i];
    }
    creat(n);
    int all = n;//因为堆里元素个数在不断变化，用另一个变量保存初始堆元素个数
    for(int i = 1;i<=n;i++){
        cout<<getTop(all)<<" ";
    }
    cout<<endl;

    return 0;
}
/*测试数据：
10
4 5 6 1 2 2 8 15 4 10
*/

另外两个排序待更新。