上一文中我们介绍了插入排序与希尔排序，本文，我们来重点介绍一下==选择排序与堆排序==

@TOC

🌳选择排序

📕简单选择排序

首先我们来说一说直接选择排序，首先来看一种我们经常见到的

void Select_Sort2(int* a, int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        int k = i;
        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[k])
                k = j;
        }
        if (k != i) {
            int t = a[k];
            a[k] = a[i];
            a[i] = t;
        }
    }
}

• 首先记录下数组中的第一个数，然后从i + 1个数开始向后遍历，若是找到一个比它小的数，则记录下这个数的位置，最后当这个数与记录的第一个数字不相同时，就进行一个交换
• 这是我们很早就学会了的简单选择排序算法，很直观，在遍历N个数的同时又去层内向后遍历，时间复杂度为==O(N^2^)==

给大家看一下动画，方便理解

📕直接选择排序

然后我们来讲一种略微高效一点的选择排序

• 其原理就是利用双指针，一个begin前指针，一个end后指针，记录下首尾两个位置
• 然后设置一个最小值，一个最大值，一开始最小值为begin，最大值为end，接着通过一个内层的for循环从begin到end去做一个遍历，若是找到比这个最小值还要小的，就更新最小值；若是找到比这个最大值还要大的，就更新最大值
• 很简单又直观，我们来看一下代码

/*直接选择排序*/
void Select_Sort(int* a, int n)
{
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mini = begin;
        int maxi = end;
        for (int i = begin; i <= end; ++i)
        {
            /*更新最大最小值*/
            if (a[i] < a[mini])
            {
                mini = i;
            }
            if (a[i] > a[maxi])
            {
                maxi = i;
            }

        }
        //将最小值放在最前面，将最大值放在最后面
        swap(a[begin], a[mini]);
        swap(a[end], a[maxi]);
        begin++;
        end--;
    }
}

但是这种写法有一个缺陷，若是最大值max与前指针begin重合了，就会发生错误

• 因为当你执行这段语句时，此时的最大值就会被最小值覆盖，最小值会放到最前面的位置
• swap(a[begin], a[mini]);
• 此时再去执行这一个语句，便会找不着最大值了
• swap(a[end], a[maxi]);

我们去VS里测试一下看看

• 可以看到，我将最大值9放在首位，后面在排序的时候，首位便发生了错乱，一直不会更新，末尾的位置也是一样，就只是中间进行了排序
• 那我们要怎么去修正它呢？其实只要在第一次换位的时候做一个判断就可以了，若是这个max最大值与begin重合了，那么此时在更新max只需要更新一下max值就可以了

swap(a[begin], a[mini]);
if (begin == maxi)
{
    maxi = mini;
}
swap(a[end], a[maxi]);
begin++;
end--;

📕选择排序时间复杂度分析

• 从上面这两种选择排序的方式来看，它们都属于O(N^2^)，而且选择排序无论是在随机排序还是顺序排序下，其时间复杂度都是==O(N^2^)==，所有说这种排序的效率并不是很高，反倒是我们昨天介绍的直接插入排序来得好，因为若数组是呈有序序列排列的，那直接插入排序的时间复杂度是可以达到O(N)的
• 所以我们在选择排序算法的时候如果会使用其他的排序算法尽量就不要使用选择排序，看这张表就知道了。这里也只是给大家简单地介绍一下。

接下来我们来看一种复杂但是很高效的排序算法——==堆排序==

🌳堆排序

⏳什么是堆？

堆，它得物理结构是一个数组，是一个 完全二叉树，而堆排序是根据堆的这种数据结构设计的一种排序，其中堆分为大根堆和小根堆

大根堆

• 对于大根堆得要求，所有的父亲结点都大于等于其孩子结点

小根堆

• 对于小根堆得要求，所有的父亲结点都小于等于其孩子结点

• 刚才说到孩子结点与父亲结点，那它们之间的关系是怎样的呢，我们来看一下

【LeftChild = Parent * 2 + 1】
【RightChild = Parent * 2 + 2】
【Parent = (Child - 1)/2】

• 以上就是它们之间的关系，对于任何的地方都适用

⏳向下调整算法

什么是向下调整算法呢？我们也是分别通过 小根堆和大根堆来看一下

小根堆调整

• 也就是从根节点开始，作为父亲结点，选出其左右孩子中较小的那一个，若是比父亲结点来的小，则交换这两个结点，然后更新交换后的孩子结点为新的父亲结点，继续向下调整，==直到叶子结点就终止==

大根堆调整

• 大根堆与小根堆刚好相反。不过一样是从根节点开始，作为父亲结点，选出其左右孩子中较大的那一个，若是比父亲结点来的大，则交换这两个结点，然后更新交换后的孩子结点为新的父亲结点，继续向下调整，==直到叶子结点就终止==

尤其要注意的一点是如果你要使用这个算法，那根结点左子树和右子树必须都是小堆或者大堆

🐀算法图示

• 以下就是向下调整算法的原理，首先看到27，为根结点，接着我们看起左子树和右子树是不是均为小顶堆
• 然后现在它的左右孩子为15和19，经过比较是15来的小，选出小的那个孩子后，就将其与根节点进行一个比较，若是比根节点小的，则将这个小的孩子换上来，若是比根节点大的，就原本就是小顶锥，就不需要换了

• 然后在换完一次后，上一次的较小孩子结点就成了下一次得的父亲结点，它也会有自己的孩子，看到小的那个为28，所以将27与18进行一个交换
• 最后一次的交换便是父亲结点25与27的交换

那这个交换的次数最多是几次呢？

• 根据我们前面二叉树的知识，这是呈一个等比数列。若一棵满二叉树树的高度为h，那个结点的个数就为2^h^ - 1 = N，那这里是完全二叉树，后面肯定缺了一些结点，那就是2^h^ - 1 - X= N，减1后在减缺的结点X，但是相比N，它是可忽略的值
• 所以我们可以得到h = log~2~N + 1 + X，根据这个大O渐进法的规则，算法的常数操作可忽略不计
• 所以可以得出这个向下调整算法要调整的高度为O(logN)也就是其时间复杂度

但若是这个左右子树不满足是小顶堆或者大顶堆的条件，就不可以去使用这个算法，这时我们就需要进行【建堆】做调整，我们后面再说

🐀代码实现与分析

先来看一下向下调整算法的代码的实现:school_satchel:

void swap(int& x, int& y)
{
    int t = x;
    x = y;
    y = t;
}

void Adjust_Down(int* a, int n, int root)
{
    int parent = root;
    int child = parent * 2 + 1;
    while (child < n)
    {
        //选出左右孩子中小的那一个
        if (child + 1 < n && a[child + 1] < a[child])
        {    //考虑到右孩子越界的情况
            child += 1;
                //若右孩子来的小，则更新孩子结点为小的那个
        }
        //交换父亲节点和小的那个孩子结点
        if (a[child] < a[parent]){
            swap(a[child], a[parent]);
            //重置父亲节点和孩子结点
            parent = child;
            child = parent * 2 + 1;
        }
        else {        //若已是小根堆，则不交换
            break;
        }
    }
}

• 外层的while循环控制的就是调整到叶子结点时便不再向下做调整，内部的第一个if分支判断是选出左右孩子中小的那一个，因为我们默认左孩子较小，若时右孩子小一些的话，将其值+1便可，注意这里的==child + 1 < n==，因为a[child + 1]去算它的右孩子时，就有可能会越界了。因此要加一个条件就是==child + 1 < n==，当最后的这个叶子结点只落在左孩子上时，我们才去进行一个判断
• 第二个分支判断就是交换父亲结点和小的那个孩子结点，然后进行一个更替，但若是孩子结点这时已经比父亲结点要来的大了，就不需要一直往下调整，已经是OK了，因此直接break就行

⏳建堆

上面我们有说到，当这个左右子树不是大堆或者小堆的时候，就不能去直接使用向下调整算法了，那这个时候怎么办呢？我们就需要去进行一个调整

• 那我们应该从哪里开始调整呢，是去调整这个叶子6或者1吗，既然它是叶子，我们就没有必要去进行一个调整，只需要调整子树即可，也就是图中的这个8
• 那我们要怎么去找到8这个结点呢，这就要看它的叶子结点0了，我们上面有说到过一组公式，就是知道一个父亲结点的孩子结点，怎么去求这个父亲结点==Parent = (Child - 1)/2==
• 而最后一个结点的值为n - 1，所以我们将其定义为一个循环，从下往上依次去进行一个换位寻找，直到原来的根节点为止，然后内部通过我们上面推导出的【向下调整算法】进行一个改进，变为【向“上”调整算法】

for (int i = (n - 1 - 1) / 2; i >= 0; --i)
    Adjust_Down(a, n, i);

• 这个叫做==自底向上==的建堆方式，从倒数第二层的结点（叶子结点得上一层）开始，从右向左，从下到上得向下进行调整

⏳排升序，建大堆or小堆？

知道了如何去建一个堆，那这个地基就算搭好了，接下去我们就要使用这个 堆积树去进行一个 堆排序

• 一般我们都会去实现升序排序，那对于这个升序排序的话是要建大堆呢还是小堆呢？，许多同学可能都会认为是建小堆，因为小堆的话是根结点来的小，也就是开头来的小，那后面大，也就构成了升序排序，真的是这样吗，我们来探究一番？

• 从图示中我们可以看出，若是建小堆的话，那最小的那个数就在堆顶，这个歌时候再去剩下的数里面选数的话，这个根节点就需要重新选择，但是这样的话==原本的左孩子结点就会变成新的根结点，而右孩子结点就会变成新的左孩子结点==
• 这就会导致剩下的树结构都乱了，那便需要重新去建堆才能选出下一个数，对于建堆，其时间复杂度我们可以看出来，一层for循环，需要O(n)，这就会导致堆排序的时间复杂度上升，那也就没了它的优势
• 所以我们在是实现升序排序的时候不要用大根堆，效率过低，并且建堆选数，还不如直接遍历选数，遍历的话也是可以找出最小数

从上面的分析可以看出，要实现一个升序排序，不可以去建立一个小顶堆，那我们就应该去建立一个大顶堆，那大顶堆要怎么建立呢？其实只需要稍微改一下我们上面那个【向下调整算法】即可，如下:point_down:

//选出左右孩子中大的那一个
if (child + 1 < n && a[child + 1] > a[child])
{    //考虑到右孩子越界的情况
    child += 1;
        //若右孩子来的小，则更新孩子结点为小的那个
}
//交换父亲节点和大的那个孩子结点
if (a[child] > a[parent]){
    swap(a[child], a[parent]);
    //重置父亲节点和孩子结点
    parent = child;
    child = parent * 2 + 1;
}
else {        //若已是小根堆，则不交换
    break;
}

• 也就是修改两个if分支的条件，去找出大的那个孩子结点，找出后若比父亲结点小，则进行一个交换即可
• 下面就是调整出来的大根堆，这个时候我们只需要将根结点的第一个数与最后一个叶子结点进行一个交换即可

• 那接下来应该怎么办呢？我们将刚刚从堆顶换下来的最大的那个数排除在堆外，接下去看我用绿色笔圈起来的两个子树，依旧是呈现一个大顶堆，这时看到可以看到我们两个紫色三角形做的两个标记数，这就是下一次要交换的两个数，也就是每次都将上层的大的数字与最后层的叶子结点进行一个交换，接着在交换之后将最低端的那个数排除在堆外即可，因为==即使排除了这个数字，也不会像上面那样改变了整棵树的整体层次结构==，左右子树依旧是呈现一个大顶堆的现状

• 我们再来分析一下其时间复杂度，向下调整的话我们上面说到过是logN，又因为有N个数需要调整，因此建堆的时间复杂度为O(n)，所以它的总体时间复杂度为==O(NlogN)==

我们来看一下其代码实现

//排升序，建大堆
int end = n - 1;        //获取最后一个叶子结点
while (end > 0)
{
    swap(a[0], a[end]);        //将第一个数与最后一个数交换
    Adjust_Down(a, end, 0);        //向下调整，选出次大的数，再和倒数第二个数交换
    end--;        //最后一个数前移，上一个交换完后的数不看做堆中的数
}

• 首先，你需要去获取最后一个叶子结点的位置，然后建立一个循环，去交换第一个数和最后一个数，接着继续寻找次大的数
• 通过一个【向下调整算法】，去选数，再让每次结束后的end--，也就是往左结点遍历，直到遍历到这个根结点为止，才跳出while循环

⏳总体时间复杂度分析【⭐⭐⭐⭐⭐】

对于堆排序，我们是分成了三个部分，第一部分是先去实现一个==向下调整算法==，接着第二部分我们需要去==建堆==，将这个左右子树都调整为大顶堆或是小顶堆，第三部分就是==根据建立好的堆去进行一个排序==，升序的话需要通过大顶堆去排序，不可以通过小顶堆，否则会乱了树层结构

接着我们来仔细地回顾并分析一起它们的时间复杂度

向下调整算法

• 对于向下调整算法，可以看出，它是通过一个外层的while循环在控制，慢慢地向下遍历，若是小根堆调整，则是将小的结点都慢慢交换上来，大根堆则是相反
• 从第0个结点也就是根节点开始到第n - 1个结点，就是有n个结点，因此其时间复杂度为O(N)

建堆

• 对于建堆的操作，虽然只有两行，一个for循环内部嵌套一个向下调整算法，大家可能认为这是O(n)或是O(n^2^)，不是很确定，我们一起来看看👀
• 上面说过，对于这个建堆，是一个自底向上的方式，从右到左，从下到上进行一个调整
• 我们现在假设其为一棵满二叉树，堆高为h。同样的，假设每层得高度为h~i~，每层的结点数为n~i~，则建堆得复杂度为t(n) =

• 我们根据一棵满二叉树去推导，用它得这个结点个数*最多调整次数，就可以一步步推算出下面的这个公式

• 然后从这个公式我们可以观察出此为一个等比数列，所以我们可以联想到等比数列得应用中比较常见的一种叫做【错位相减法】
• 让原本的公式两遍都去乘以2，然后将其后移，实施一个错位相减，后面经过归类，用等比数列的公式去套，就可以得出t(n)是为-h + 2^h^-1
• 我们在上面有说到过这个二叉树的总结点个数公式为2^h^-1 = N，而对于树的高度，就是我们在向下调整算法时说到的最多调整logN次
• 所以可以得出这个整体的时间复杂度为N - logN，再由这个大O渐进法的规则，==保留高阶次的复杂度==，最后可以看出这个建堆的总体时间复杂度化简后为为O(N)

排序

• 最后呢是通过建大堆去实现这个升序排序。首先上面的建堆算法是O(n)，然后剩下的部分我们通过向下调整算法选数，为O(logN)
• 所以可以得出堆排序的完整时间复杂度应该是为==O(NlogN)==

我们通过代码来测试一下

• 可以看出，这个堆排序的效率还是很高的，和希尔排序是一个层次级别，不过8ms和14ms差别不大，但可以看出，比直接插入排序是快了不少。大家也可以自己去测试一下:computer:

// 测试排序的性能对比
void TestOP()
{
    srand(time(0));
    const int N = 100000;
    int* a1 = (int*)malloc(sizeof(int) * N);
    int* a2 = (int*)malloc(sizeof(int) * N);
    int* a3 = (int*)malloc(sizeof(int) * N);
    int* a4 = (int*)malloc(sizeof(int) * N);
    int* a5 = (int*)malloc(sizeof(int) * N);
    int* a6 = (int*)malloc(sizeof(int) * N);
    for (int i = 0; i < N; ++i)
    {
        a1[i] = rand();
        a2[i] = a1[i];
        a3[i] = a1[i];
        a4[i] = a1[i];
        a5[i] = a1[i];
        a6[i] = a1[i];
    }
    int begin1 = clock();
    InsertSort2(a1, N);
    int end1 = clock();

    int begin2 = clock();
    Shell_Sort2(a2, N);
    int end2 = clock();

    int begin3 = clock();
    //SelectSort(a3, N);
    int end3 = clock();

    int begin4 = clock();
    Heap_Sort(a4, N);
    int end4 = clock();

    int begin5 = clock();
    //QuickSort(a5, 0, N - 1);
    int end5 = clock();

    int begin6 = clock();
    //MergeSort(a6, N);
    int end6 = clock();

    printf("InsertSort:%d\n", end1 - begin1);
    printf("ShellSort:%d\n", end2 - begin2);
//    printf("SelectSort:%d\n", end3 - begin3);
    printf("HeapSort:%d\n", end4 - begin4);
    //printf("QuickSort:%d\n", end5 - begin5);
    //printf("MergeSort:%d\n", end6 - begin6);
    free(a1);
    free(a2);
    free(a3);
    free(a4);
    free(a5);
    free(a6);
}

🌳总结与提炼

• 本文我们讲述了选择排序与堆排序，选择排序，其性能在众多排序中并不是很高效，并不作为大家的首选。
• 然后着重讲述了一种叫做堆排序，它是利用堆积树（堆）这种数据结构所设计的一种排序算法，虽然需要通过向下==调整算法、建堆、查数==这些操作，而且还需要你对【二叉树】这种数据结构掌握得比较牢固，但从我们的分析来看，其确实是比较高效地一种排序算法，与希尔排序是等价的，时间复杂度均为O(NlogN)
• 下文我们将进入交换排序，为大家介绍多数人最常用的两种排序算法——冒泡排序与快速排序

最后感谢您对本文的观看，如有问题请于评论区留言或者私信我:cherry_blossom: