【C++】十大排序算法之 堆排序 & 计数排序

���次介绍内容参考自：十大经典排序算法（C++实现） - fengMisaka - 博客园 (cnblogs.com)

排序算法是《数据结构与算法》中最基本的算法之一。

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，时间复杂度为 O(nlogn)～O(n²)。
• 非比较类排序：不通过比较来决定元素间的相对次序，其时间复杂度可以突破 O(nlogn)，以线性时间运行。

  【十大经典排序算法分类】

  【十大经典排序算法的复杂度分析】

  名词解释：

  • 时间/空间复杂度：描述一个算法执行时间/占用空间与数据规模的增长关系。

  • n：待排序列的个数。

  • k：“桶”的个数（上面的三种非比较类排序都是基于“桶”的思想实现的）。

  • In-place：原地算法，指的是占用常量内存，不占用额外内存。即空间复杂度为 O(1) 。

  • Out-place：非原地算法，占用额外内存。

  • 稳定性：假设待排序列中两元素相等，排序前后这两个相等元素的相对位置不变，则认为是稳定的。

    ---

    ---

    一、堆排序（Heap-Sort）

           堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

    1.1、算法描述

    • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
    • 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]=0;i--) {HeapAdjust(arr, i, len - 1);}//每次将根和待排序的最后一次交换，然后在调整int tmp = 0;for (int i = 0; i

      ---

      1.4 、算法分析

             堆排序是不稳定排序，适合数据量较大的序列，它的平均时间复杂度为 Ο(n * log n)，空间复杂度为 O(1)。

              此外，堆排序仅需一个记录大小供交换用的辅助存储空间。

      ---

      ---

      二、计数排序（Counting Sort）

              计数排序（Counting Sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

      2.1 、算法描述

      • 找出待排序的数组中最大和最小的元素；
      • 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
      • 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
      • 反向填充目标数组：将每个元素i放在新数组的第 C(i) 项，每放一个元素就将 C(i) 减去 1。

        2.2 、动图演示

        计数排序动图演示

        ---

        2.3、C++编码

        /*** @version Copyright (c) 2024 NCDC, Servo。 Unpublished - All rights reserved* @file CountingSort.hpp* @brief 计数排序* @autor 写代码的小恐龙er* @date 2024/03/06*/// 时间复杂度O(n + k)// 空间复杂度O(k)void CountingSort(int arr[], int n) {    if (arr == NULL) return;    // 定义辅助空间并初始化    int max = arr[0], min = arr[0];    int i;    for (i = 1; i  arr[i]) min = arr[i];    }    int r = max - min + 1;    vector C(r, 0);    // 统计每个元素出现的次数    for (i = 0; i = 0; i--) R[--C[arr[i] - min]] = arr[i];    // // 目标数组里的结果重新赋值给 arr    // for (i = 0; i  
        2.4 、算法分析
         
                计数排序属于非交换排序，是稳定排序，适合数据范围不显著大于数据数量的序列。