【八大数据排序法】堆积树排序法的图形理解和案例实现 | C++

本文涉及的产品
云原生大数据计算服务 MaxCompute,5000CU*H 100GB 3个月
云原生大数据计算服务MaxCompute,500CU*H 100GB 3个月
简介: 排序算法是我们在程序设计中经常见到和使用的一种算法,它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代,随着大数据和人工智能的发展,大型企业的数据库中有亿级的用户数据量。因此对其进行处理,排序算法也就成为了其中必不可缺的步骤之一。

712179699b5ce05abbb6f6ba37e52ad3_72ec8f9c32be40d787c8950af73f9aaf.png

前言

       排序算法是我们在程序设计中经常见到和使用的一种算法,它主要是将一堆不规则的数据按照递增或递减的方式重新进行排序。在如今的互联网信息时代,随着大数据和人工智能的发展,大型企业的数据库中有亿级的用户数据量。因此对其进行处理,排序算法也就成为了其中必不可缺的步骤之一。


认识排序    

       排序功能对计算机领域而言,是一项非常重要而且普遍的工作。排序中数据的移动方式可分为直接移动和逻辑移动两种方式,直接移动是直接交换存储数据的位置,而逻辑移动并不会移动数据存储的位置,仅改变指向这些数据辅助指针的值。排序通常按照数据量的多少和所使用的内存,可分为内部排序和外部排序,数据量小可以全部加载到内存来进行排序的,就称为内部排序,大部分排序属于此类。数据量大而无法一次性加载到内存中,必须借助磁带,磁盘等辅助存储器进行排序的,则称为外部排序。随着数据结构科学的进步,如今,陆续被提出的冒泡排序法,选择排序法,插入排序法,合并排序法,快速排序法,堆积排序法,希尔排序法,基数排序法,直接合并排序法等等,它们各有其特色和其应用场合。并且在算法中,我们非常关注算法程序代码的时间复杂度和空间复杂度,因为它会直接体现出我们程序代码的执行效率以及编程人员的逻辑思维等等的综合能力。当数据量相当庞大时,排序算法所花费的时间就显得相当重要,排序算法的时间复杂度可分为最好情况、最坏情况以及平均情况。另外,对于任何的排序算法都会有数据交换的操作,数据互换位置会暂时用到一个额外的空间,这也是排序算法中空间复杂度要考虑到的问题,而在排序算法中所使用的额外空间越小,它的空间复杂度就越好。


一、堆积树排序法是什么?

1.简要介绍

       堆积树排序法是选择排序法的改进版,它减少了在选择排序法中的比较次数,从而提高了时间效率。堆积排序法用到了二叉树的技巧,它是利用堆积树去完成排序的。


2.图形理解

       堆积树是一种特殊的二叉树,可以分为最大堆积树和最小堆积树:

最大堆积树需要满足的条件:
① 它是一棵完全二叉树
② 树根的值是堆积树中最大的
③ 所有节点的值都大于或等于它左右子节点的值
最小堆积树需要满足的条件:
① 它是一棵完全二叉树
② 树根的值是堆积树中最小的
③ 所有节点的值都小于或等于它左右子节点的值

        (1)首先我们来理解如何将二叉树转化成堆积树的操作步骤。我们将下面如图所示表示数列(33,20,19,27,38,95,68,1,14)的二叉树进行转化:

4bbbcab80bc4fade8a4d3c2bf6781640_b48574ad70394ff5804517b8f21a005e.png


       将该二叉树中所有节点的值用数组存储起来,即tree[0],tree[1],tree[2],tree[3],tree[4],tree[5],tree[6],tree[7],tree[8]。


       ①tree[0]=33为树根,因为tree[1]=20


       ②因为tree[2]=19


       ③因为tree[3]=27>tree[1],故交换位置。具体情况如下图所示:

58fb94c88895254dc1141d595f8c3b50_3db54da9e05843a897a553d8adc403cd.png


        ④因为tree[4]=38>tree[1],故交换位置。具体情况如下图所示:


  47234b4d1f6ea16d60c257cad27b72b5_741040c104824ba8bd03b1cc20d132c7.png


      ⑤因为tree[5]=95>tree[2],故交换位置。具体情况如下图所示:      

5336517a2a69b13a8f79d96700c48a9f_790c9e08ef574eeab8ec82700c3574ca.png

       ⑥因为tree[6]=68


       ⑦再将树根tree[0]=33与其已经交换后的tree[1]=38,tree[2]=95比较,因为tree[0]

7c5d76ad2d40ba8b0eb0661382971234_cae0219033164bca93cda0028e6fac64.png



       ⑧继续扫描树根子节点的情况,左子节点满足情况,右子节点不满足需要交换位置。因为tree[6=68]>tree[2]=33,故交换位置。且交换位置后,tree[0]=95>tree[2]=68,所以不交换。具体情况如下图所示:

5351b2f425146c069d172b92bc29ce06_20bc711d50fd41ae831e0920cb5a132c.png



        ⑨因为tree[7]=1


        ⑩因为tree[8]=14


       (2)上面我们示范的是一棵最大堆积树的建立方法(从上往下建立)。堆积树并非唯一,如果从数组的最后一个元素,从下往上逐一比较也可以去建立一棵最大堆积树,并且通过堆积树排序法得到的数列大小是从大到小的。如果想从小到大排序,就必须去建立最小堆积树,方法与建立最大堆积树方法一致,只需注意表格中最小堆积树需满足的条件即可。下面我们用堆积排序法对(1)进行从大到小的排序:


       ①已经堆积树具体情况如下图所示:

4bd783adca8ec7b0655594a682112ae5_d63466583a8b4a6e8e4b8db72a733a18.png

        ②将95从树根删除,重新建立堆积树,如下图所示:

43741f38e89e326e9ed5dff48ec6e6d1_f5ee143e858140f3bcf35335da3e23d4.png

       ③将68从树根删除,重新建立堆积树,如下图所示:

a94bf5c8f740a0d82b9a9fab01624f29_29b5139e71334515820dd377cbe80766.png


       ④将38从树根删除,重新建立堆积树,如下图所示:


ee0104e6e20fbb24b8e7ee7a85bb6b03_a38006b02cd94bcca3d82b9c369d6724.png

        ⑤将33从树根删除,重新建立堆积树,如下图所示:


e9b6bff7eeaa5d35e48dd81b6adaa427_70d9ed5377a34def88de70209dde3801.png


        ⑥将27从树根删除,重新建立堆积树,如下图所示:


396c2d5a01ec1738ab4a4e8f1c785bd9_74a33b3454ed4b3eaf6e43781b3103b3.png


        ⑦将20从树根删除,重新建立堆积树,如下图所示:

5e9ea0a181c89952d614c19eb3648b9c_c59352f4e4a747178a2a96da7be887da.png



        ⑧将19从树根删除,重新建立堆积树,如下图所示:


02c315a4cb1f8c2ac4164b91f6fe4108_e5e2cb09e9cc4bf4b3b950ba81e321fe.png


        ⑨将14从树根删除,重新建立堆积树,如下图所示:


c6faa84d42c34f46018e70f1dbe5bf52_be190f4594f549e7acefdcc2882b8dd6.png


        ⑩将1从树根删除,从而完成了最终的排序,如下图所示:

265de04121cfc1ed6d521c7071faf423_0a3d52ccfbd94035abc69fbd93128023.png

3.算法分析

      ①堆积树排序法在所有情况下,时间复杂度都为O()。


      ②堆积树排序法不是稳定排序法。


      ③堆积树排序法只需要一个额外的空间,空间复杂度为O(1)。


二、案例实现

1.案例一

①范例情况:用堆积树排序法对随机8个数据下的数列进行从小到大的排序。


②代码情况:

#include<iostream>
using namespace std;
#define size 9 //事先声明  数据元素+1
class tree {
public:
  int data[size];
  void showresult() {
  for (int i = 1; i < size; i++)
  cout << data[i] << " ";
  cout << endl;
  }
  void tree_start(int i,int len) {
  int j = 2 * i,temp=data[i],post=0;
  while (j <= len && post == 0)
  {
    if (j < len) {
    if (data[j] < data[j + 1])    //找出大节点
      j++;
    }
    if(temp>=data[j]){                 //若树根较大,则结束比较过程
    post = 1;
    }
    else {                          //若树根较小,则继续进行比较
    data[j / 2] = data[j];
    j = 2 * j;
    }
  }
  data[j / 2] = temp;       //指定树根为父节点
  }
  void tree_sort_start() {
  for (int i = size / 2; i > 0; i--)    //建立堆积树的结点
    tree_start(i,size-1);
  cout << "原始堆积树的内容:"; showresult();
  for (int j = size - 2; j > 0; j--)
  {
    int temp;
    //头尾结点继续交换
    temp = data[j + 1];
    data[j + 1] = data[1];
    data[1] = temp;
    tree_start(1,j);   //处理剩余节点
  }
  }
};
void text()
{
  tree t;
  cout << "请输入要排序的" << size-1 << "个数据" << endl;
  for (int i = 1; i < size; i++)
  cin >> t.data[i];
  cout << "排序前:";t.showresult();
  t.tree_sort_start();
  cout << "排序后:";t.showresult();
}
int main()
{
  text();
}

③结果展示:

1261eb2a87c61d50942fe1d0cdd9fcd6_35c0a4da5de444f0a7d2c6542d81e0c0.png


总结

       以上就是堆积树排序法的所有内容,因为在上面我们做了比较详细的讲解,所以在总结这部分不做太多的解释与说明。



相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
打赏
0
0
0
0
46
分享
相关文章
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
39 12
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
11 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
65 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
53 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
51 10
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
39 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
62 10
|
1月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
49 7
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
47 5
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2