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

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

1b81d063ce22610f902263f57369b5ab_8f56327c5b4142688171b6caa8126163.png

前言

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


认识排序

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


一、合并排序法是什么?

1.简要介绍

       合并排序法是针对已经排序好的两个或两个以上的数列,通过合并的方式将其组合成一个大的且已经排好序的数列。即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列,该排序法也用到了分治法分而治之的思想。


2.具体情况

       合并排序法的具体步骤如下:


       (1)将N个长度为1的键值成对地合并为N/2个长度为2地键值组。


       (2)将N/2个长度为2地键值成对地合并为N/4个长度为4地键值组。


       (3)将键值组不断地去合并,直到合并成一组长度为N的键值组为止。


下面用合并排序法对40、10、42、75、51、99、66、24这十个数据元素进行从小到大的排序,具体情况如下图所示:

9cdd8eafd153a88ddcaefc0550fad912_383ed8a77a1b4117b75f12df951fd2f9.png


上面的图片中展示的是简单的一种合并排序法,其又被称为2-way合并排序(适用于偶数个数据)。我们可以将它的排序步骤进行整理:把初始时的8个长度为1的数列合并成4个已经排序完成且长度为2的数列;再将4个长度为2的数列合并成2个已经排序完成且长度为4的数列;最后将2个长度为4的数列合并成1个已经排序完成且长度为8的数列。


3.算法分析

       ①合并排序法的n个数据一般需要处理约次, 每次处理的时间复杂度为O(n)。所以该排序法的最好情况,最坏情况以及平均情况的时间复杂度为O()。


       ②合并排序法在排序过程中需要一个与数据文件大小同样的额外空间,所以空间复杂度O(n)。


       ③合并排序法是稳定排序法。


二、案例实现

1.案例一

①范例情况:用合并排序法,对在快速排序法下已经排序好的数列一16,25,39,27,30,42和数列二12,8,45,63,20,99这两组数据的12个数据进行从小到大的排序。


②代码展示:

#include<iostream>
using namespace std;
//事先声明排序数据的个数
#define size_1 6 
#define size_2 6
class sort{
public:
  int data_1[size_1];
  int data_2[size_2];
  int data_3[size_1 + size_2];
  void showresult(int len,int data[]) {
  for (int i = 0; i < len; i++)
    cout << data[i] << " ";
  cout <<  endl;
  }
};
class quick :public sort {
public:
  void quick_start(int left, int right,int data[]) {
  int left_idx, right_idx;
  int temp;
  if (left < right)
  {
    left_idx = left + 1;
    right_idx = right;
    while (1)
    {
    //从左向右扫描,找出一个键值大于data[left]的数据元素
    for (int i = left + 1; i <= right; i++)
    {
      if (data[i] > data[left])
      {
      left_idx = i;
      break;
      }
      left_idx++;
    }
    //从右向左扫描,找出一个键值小于data[left]的数据元素
    for (int j = right; j >= left + 1; j--)
    {
      if (data[j] < data[left])
      {
      right_idx = j;
      break;
      }
      right_idx--;
    }
    //如果left_idx<right_idx,将二者交换位置
    if (left_idx < right_idx) {
      temp = data[left_idx];
      data[left_idx] = data[right_idx];
      data[right_idx] = temp;
    }
    else {
      break;
    }
    }
    //如果left_idx>=right_idx
    if (left_idx >= right_idx)
    {
    //将data[left]与data[right_idx]交换位置
    temp = data[left];
    data[left] = data[right_idx];
    data[right_idx] = temp;
    //以递归的方式继续进行左半的快速排序
    quick_start(left, right_idx - 1,data);
    //以递归的方式继续进行右半的快速排序
    quick_start(right_idx + 1, right,data);
    }
  }
  }
};
class merge :public sort {
public:
  void merge_start(int data_1[],int data_2[],int data_3[]) {
  int i = 0, j = 0, k = 0;
  //进行数据的合并排序
  while (i<size_1&&j<size_2)
  {
    if (data_1[i] <= data_2[j])
    data_3[k++] = data_1[i++];
    else
    data_3[k++] = data_2[j++];
  }
  //再次检查判断,是否合并完成
  while (i < size_1)
    data_3[k++] = data_1[i++];
  while (j < size_2)
    data_3[k++] = data_2[j++];
  }
};
void text()
{
  sort s;
  quick q;
  merge g;
  cout << "请输入数列1中的" << size_1 << "个数据:";
  for (int i = 0; i < size_1; i++)
  cin >> s.data_1[i];
  cout << "请输入数列2中的" << size_2 << "个数据:";
  for (int i = 0; i < size_2; i++)
  cin >> s.data_2[i];
  //先利用最佳的快速排序法对两组数据进行分别排序
  q.quick_start(0,size_1-1,s.data_1);
  q.quick_start(0,size_2-1,s.data_2);
  cout << "排序后的数列1:"; s.showresult(size_1, s.data_1);
  cout << "排序后的数列2:"; s.showresult(size_2, s.data_2);
  //再利用合并排序法去将1,2两个数据列合并到数据列3中
  g.merge_start(s.data_1,s.data_2,s.data_3);
  cout << "合并后的数列:"; s.showresult(size_1 + size_2,s.data_3);
}
int main()
{
  text();
}

③代码展示:

ccae1d1531a7a34ffe4d2e8d7fcee8db_e3beea9d1cb14203af2b4319629cf73d.png


总结

       以上就是合并排序法的讲解,合并排序法其实更广泛的用于多个已经经过排序法排序好的数列,然后将多个数列进行合并的问题。我也在上面的案例实现中,刻意的去举了这样的一个案例,让大家去更好的去理解多个排序算法的综合应用,从而提高我们对算法的综合使用能力。


相关实践学习
基于MaxCompute的热门话题分析
本实验围绕社交用户发布的文章做了详尽的分析,通过分析能得到用户群体年龄分布,性别分布,地理位置分布,以及热门话题的热度。
SaaS 模式云数据仓库必修课
本课程由阿里云开发者社区和阿里云大数据团队共同出品,是SaaS模式云原生数据仓库领导者MaxCompute核心课程。本课程由阿里云资深产品和技术专家们从概念到方法,从场景到实践,体系化的将阿里巴巴飞天大数据平台10多年的经过验证的方法与实践深入浅出的讲给开发者们。帮助大数据开发者快速了解并掌握SaaS模式的云原生的数据仓库,助力开发者学习了解先进的技术栈,并能在实际业务中敏捷的进行大数据分析,赋能企业业务。 通过本课程可以了解SaaS模式云原生数据仓库领导者MaxCompute核心功能及典型适用场景,可应用MaxCompute实现数仓搭建,快速进行大数据分析。适合大数据工程师、大数据分析师 大量数据需要处理、存储和管理,需要搭建数据仓库?学它! 没有足够人员和经验来运维大数据平台,不想自建IDC买机器,需要免运维的大数据平台?会SQL就等于会大数据?学它! 想知道大数据用得对不对,想用更少的钱得到持续演进的数仓能力?获得极致弹性的计算资源和更好的性能,以及持续保护数据安全的生产环境?学它! 想要获得灵活的分析能力,快速洞察数据规律特征?想要兼得数据湖的灵活性与数据仓库的成长性?学它! 出品人:阿里云大数据产品及研发团队专家 产品 MaxCompute 官网 https://www.aliyun.com/product/odps&nbsp;
目录
相关文章
|
2月前
|
编译器 C++
【C++核心】指针和引用案例详解
这篇文章详细讲解了C++中指针和引用的概念、使用场景和操作技巧,包括指针的定义、指针与数组、指针与函数的关系,以及引用的基本使用、注意事项和作为函数参数和返回值的用法。
37 3
|
2月前
|
C++
【C++案例】一个项目掌握C++基础-通讯录管理系统
这篇文章通过一个通讯录管理系统的C++项目案例,详细介绍了如何使用C++实现添加、显示、删除、查找、修改和清空联系人等功能。
42 3
|
3月前
|
存储 C++
【C++】C++ 基于QT实现散列表学生管理系统(源码+数据+课程论文)【独一无二】
【C++】C++ 基于QT实现散列表学生管理系统(源码+数据+课程论文)【独一无二】
【C++】C++ 基于QT实现散列表学生管理系统(源码+数据+课程论文)【独一无二】
|
3月前
|
存储 算法 C++
C++ STL应用宝典:高效处理数据的艺术与实战技巧大揭秘!
【8月更文挑战第22天】C++ STL(标准模板库)是一组高效的数据结构与算法集合,极大提升编程效率与代码可读性。它包括容器、迭代器、算法等组件。例如,统计文本中单词频率可用`std::map`和`std::ifstream`实现;对数据排序及找极值则可通过`std::vector`结合`std::sort`、`std::min/max_element`完成;而快速查找字符串则适合使用`std::set`配合其内置的`find`方法。这些示例展示了STL的强大功能,有助于编写简洁高效的代码。
50 2
|
3月前
|
编译器 C++
virtual类的使用方法问题之C++类中的非静态数据成员是进行内存对齐的如何解决
virtual类的使用方法问题之C++类中的非静态数据成员是进行内存对齐的如何解决
|
2月前
|
JavaScript 前端开发 测试技术
一个google Test文件C++语言案例
这篇文章我们来介绍一下真正的C++语言如何用GTest来实现单元测试。
20 0
|
3月前
|
存储 数据挖掘 C语言
【C/C++】C/C++车辆交通违章管理系统(源码+数据文件)【独一无二】
【C/C++】C/C++车辆交通违章管理系统(源码+数据文件)【独一无二】
|
3月前
|
存储 安全 数据处理
【C++】C++ 超市会员卡管理系统(面向对象)(源码+数据)【独一无二】
【C++】C++ 超市会员卡管理系统(面向对象)(源码+数据)【独一无二】
|
4月前
|
存储 C++ 容器
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
开发与运维数组问题之C++标准库中提供数据容器作为数组的替代如何解决
54 5
|
4月前
|
设计模式 监控 Go
开发与运维C++问题之C++部分原有的数据发送能力如何解决
开发与运维C++问题之C++部分原有的数据发送能力如何解决
26 1