【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】

简介: 本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括:- **任务描述**:实现二路归并算法。- **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。- **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。- **通关代码**:提供了完整的 C++ 实现代码。- **测试结果**:展示代码运行后的排序结果。开始你的任务吧,祝你成功!

目录😋

任务描述

相关知识

1. 二路归并算法的基本概念

2. 算法步骤

3. 代码示例(以 C++ 为例

4. 时间复杂度和空间复杂度

测试说明

通关代码

测试结果


任务描述

本关任务:实现二路归并算法

相关知识

为了完成本关任务,你需要掌握:

  1. 二路归并算法的基本概念
  2. 二路归并算法步骤
  3. 代码示例(以 C++ 为例)
  4. 时间复杂度和空间复杂度

1. 二路归并算法的基本概念

二路归并算法旨在将两个已经有序的序列合并成为一个新的有序序列。打个比方,就如同有两列分别按照从小到大顺序排好队的人,现在要把这两列人合并成一列,并且依旧保持从小到大的顺序,这就是二路归并算法要完成的任务。它也是归并排序算法中的关键基础操作,归并排序整体思路就是不断地把待排序数组划分成多个子数组,先对子数组排序(常常通过递归调用归并排序来实现),之后再将这些排好序的子数组合并起来。

2. 算法步骤

  • 输入:提供两个已经排好序的数组(或者序列),这里假设为AB
  • 输出:生成一个将AB合并后的新的有序数组。
  • 具体合并操作流程如下

       首先,定义三个指针,分别指向两个输入数组AB的起始位置,以及用于存储合并结果的新数组C的起始位置。通常可以用整型变量来表示这些指针,比如i指向A数组,j指向B数组,k指向C数组(初始时,k为 0)。

       接着,开始循环比较AB指针所指向元素的大小:

  • A[i]小于等于B[j]时,把A[i]放入C[k]这个位置,然后i指针向后移动一位(即i++),同时k指针也向后移动一位(即k++),代表已经向结果数组C中成功放入了一个元素,并且准备放入下一个元素的位置。
  • 反之,要是A[i]大于B[j],则把B[j]放入C[k]中,之后j指针和k指针分别后移一位(执行j++k++操作)。

       持续进行上述的比较和放入操作,一直到A或者B其中一个数组的所有元素都已经被放入到C数组中为止。

       最后,把还没处理完的那个数组(也就是A或者B中剩余的元素),按照顺序依次放入C数组当中。

3. 代码示例(以 C++ 为例)

#include <iostream>
#include <vector>
using namespace std;
// 二路归并函数,将两个有序数组A和B合并为一个有序数组C
vector<int> merge(vector<int>& A, vector<int>& B) {
    vector<int> C;
    int i = 0, j = 0;
    // 循环比较A和B数组的元素,将较小的元素放入C数组
    while (i < A.size() && j < B.size()) {
        if (A[i] <= B[j]) {
            C.push_back(A[i]);
            i++;
        } else {
            C.push_back(B[j]);
            j++;
        }
    }
    // 将A数组剩余的元素放入C数组(如果有剩余)
    while (i < A.size()) {
        C.push_back(A[i]);
        i++;
    }
    // 将B数组剩余的元素放入C数组(如果有剩余)
    while (j < B.size()) {
        C.push_back(B[j]);
        j++;
    }
    return C;
}
image.gif

在上述代码中:

  • 定义了一个名为merge的函数,它接受两个vector类型(可以类比于数组)的参数AB,分别代表两个已经有序的输入序列。
  • 在函数内部,首先创建了一个名为Cvector,用于存放合并后的结果。然后通过两个嵌套的while循环来实现归并操作,第一个while循环用于比较AB当前位置的元素,并把较小的元素放入C中;后面两个while循环分别用于处理A或者B有剩余元素的情况,将剩余元素依次添加到C数组中。最后返回合并好的有序数组C

4. 时间复杂度和空间复杂度

  • 时间复杂度:假设两个输入数组AB的长度分别是mn,在最坏的情况下,需要对两个数组中的每一个元素都进行一次比较操作,总共需要比较m + n - 1次左右,所以时间复杂度为
  • 空间复杂度:由于代码中创建了一个新的数组(vectorC来存储合并后的结果,其长度是m + n,所以空间复杂度同样为 。不过,在一些特殊的实现场景中,如果允许直接在原有的存储空间上进行合并操作(例如原地归并),那么空间复杂度可以经过优化降低到 ,但这种实现方式的代码逻辑会相对复杂很多。

测试说明

平台会对你编写的代码进行测试:

测试输入示例:(第一行是元素个数,第二行是待排序的原始关键字数据。)

11
18 2 20 34 12 32 6 16 5 8 1
image.gif

输出示例:

排序前:18 2 20 34 12 32 6 16 5 8 1 
第1趟归并:2 18 20 34 12 32 6 16 5 8 1 
第2趟归并:2 18 20 34 6 12 16 32 1 5 8 
第3趟归并:2 6 12 16 18 20 32 34 1 5 8 
第4趟归并:1 2 5 6 8 12 16 18 20 32 34 
排序后:1 2 5 6 8 12 16 18 20 32 34
image.gif

开始你的任务吧,祝你成功!


通关代码

#include <malloc.h>
#include <stdio.h>
#define MAXL 100     //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;
typedef struct {
  KeyType key;   //关键字项
  InfoType data; //其他数据项,类型为InfoType
} RecType;       //查找元素的类型
int count = 1; //全局变量,记录第几趟归并
void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{
  for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录
    R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{
  for (int i = 0; i < n; i++)
    printf("%d ", R[i].key);
  printf("\n");
}
//一次归并:将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {
  /********** Begin *********/
  RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));
  int i = low, j = mid + 1, k = 0;
  while (i <= mid && j <= high) {
    if (R[i].key <= R[j].key)
      R1[k++] = R[i++];
    else
      R1[k++] = R[j++];
  }
  while (i <= mid)
    R1[k++] = R[i++];
  while (j <= high)
    R1[k++] = R[j++];
  for (k = 0, i = low; i <= high; i++, k++)
    R[i] = R1[k];
  free(R1);
  /********** End **********/
}
void MergePass(RecType R[], int length, int n) //实现一趟归并
{
  /********** Begin *********/
  int i;
  for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
    Merge(R, i, i + length - 1, i + 2 * length - 1);
  if (i + length - 1 < n)
    Merge(R, i, i + length - 1, n - 1);
  /********** End **********/
}
void MergeSort(RecType R[], int n) //二路归并排序算法
{
  /********** Begin *********/
  int length = 1;
  printf("排序前:");
  DispList(R, n);
  while (length < n) {
    MergePass(R, length, n);
    printf("第%d趟归并:", count++);
    DispList(R, n);
    length *= 2;
  }
  printf("排序后:");
  DispList(R, n);
  /********** End **********/
}
int main() {
  /********** Begin *********/
  int n;
  scanf("%d", &n);
  KeyType keys[MAXL];
  RecType R[MAXL];
  for (int i = 0; i < n; i++)
    scanf("%d", &keys[i]);
  CreateList(R, keys, n);
  MergeSort(R, n);
  /********** End **********/
  return 0;
}

image.gif


测试结果

image.gif

image.gif

目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
23天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
4天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
1天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
1天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
1天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。