当前位置: 首页 > news >正文

c++ 归并排序

        归并排序是一种遵循分而治之方法的排序算法。它的工作原理是递归地将输入数组划分为较小的子数组并对这些子数组进行排序,然后将它们合并在一起以获得排序后的数组。

        简单来说,归并排序的过程就是将数组分成两半,对每一半进行排序,然后将已排序的两半合并在一起。重复这个过程,直到整个数组排序完毕。

归并排序算法

归并排序是如何工作的?
        归并排序是一种流行的排序算法,以其高效和稳定而闻名。它遵循分而治之的方法对给定的元素数组进行排序。

以下是合并排序如何工作的分步说明:
        1、划分:递归地将列表或数组划分为两半,直到不能再划分为止。
        2、征服:使用合并排序算法对每个子数组进行单独排序。
        3、合并:已排序的子数组按排序顺序合并在一起。该过程将继续,直到两个子数组中的所有元素都已合并。

归并排序示意图:
让我们使用归并排序对数组或列表[38, 27, 43, 10]进行排序 

让我们看看上面例子的工作原理:
划分:
        [38, 27, 43, 10]分为[38, 27 ] 和[43, 10]。
        [38, 27]分为[38]和[27]。
        [43, 10]分为[43]和[10]。

征服:
        [38]已经排序。
        [27]已经排序。
        [43]已经排序。
        [10]已经排序。

合并:
        合并[38]和[27]得到[27, 38]。
        合并[43]和[10]得到[10,43]。
        合并[27, 38]和[10,43]得到最终的排序列表[10, 27, 38, 43]

因此,排序列表为[10, 27, 38, 43]。

归并排序的实现:
// C++ program for Merge Sort
#include <bits/stdc++.h>
using namespace std;

// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
           int const right)
{
    int const subArrayOne = mid - left + 1;
    int const subArrayTwo = right - mid;

    // Create temp arrays
    auto *leftArray = new int[subArrayOne],
         *rightArray = new int[subArrayTwo];

    // Copy data to temp arrays leftArray[] and rightArray[]
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;

    // Merge the temp arrays back into array[left..right]
    while (indexOfSubArrayOne < subArrayOne
           && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne]
            <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray]
                = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray]
                = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray]
            = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray]
            = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
    delete[] leftArray;
    delete[] rightArray;
}

// begin is for left index and end is right index
// of the sub-array of arr to be sorted
void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
        return;

    int mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
    for (int i = 0; i < size; i++)
        cout << A[i] << " ";
    cout << endl;
}

// Driver code
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Given array is \n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nSorted array is \n";
    printArray(arr, arr_size);
    return 0;
}

// This code is contributed by Mayank Tyagi
// This code was revised by Joshua Estes

输出
给定数组是
12 11 13 5 6 7

排序后的数组是
5 6 7 11 12 13

归并排序的复杂度分析:

时间复杂度:
最佳情况: O(n log n),当数组已经排序或接近排序时。
平均情况: O(n log n),当数组随机排序时。
最坏情况: O(n log n),当数组按相反顺序排序时。
空间复杂度: O(n),合并时使用的临时数组需要额外的空间。

归并排序的优点:
稳定性:归并排序是一种稳定的排序算法,这意味着它保持输入数组中相等元素的相对顺序。
保证最坏情况下的性能:归并排序的最坏情况时间复杂度为O(N logN),这意味着即使在大型数据集上它也能表现良好。
易于实现:分而治之的方法很简单。

归并排序的缺点:
空间复杂度:归并排序在排序过程中需要额外的内存来存储合并后的子数组。 
非就地:合并排序不是就地排序算法,这意味着它需要额外的内存来存储排序后的数据。这对于关注内存使用的应用程序来说可能是一个缺点。

归并排序的应用:
对大型数据集进行排序
外部排序(当数据集太大而无法容纳在内存中时)
反转计数(计算数组中反转的次数)
查找数组的中位数

相关文章:

c++ 归并排序

归并排序是一种遵循分而治之方法的排序算法。它的工作原理是递归地将输入数组划分为较小的子数组并对这些子数组进行排序&#xff0c;然后将它们合并在一起以获得排序后的数组。 简单来说&#xff0c;归并排序的过程就是将数组分成两半&#xff0c;对每一半进行排序&#xff0c…...

基于vs和C#的WPF应用之动画3

注&#xff1a;1、在内部和外部使用缓动函数 <Grid.Resources> <PowerEase x:Key"powerease" Power"3" EasingMode"EaseInOut"/> </Grid.Resources> <DoubleAnimation EasingFunction"{StaticResource powerease}&quo…...

Python import 必看技巧:打造干净利落的代码结构

大家好,学习Python你肯定绕不过一个概念import,它是连接不同模块的桥梁,是实现代码复用和模块化的关键。本文将带你深入探索Python中import的原理,并分享一些实用的导入技巧。 1. import 原理 导入机制概述 在Python中,模块(module)是一种封装Python代码的方式,它允许…...

计算机视觉(CV)(Computer Vision)

计算机视觉技术&#xff08;Computer Vision&#xff09;&#xff0c;解决的是什么&#xff1f; 图片和视频是非结构化数据&#xff0c;机器如果要理解某一图片或视频表达的内容&#xff0c;是无法直接分析的&#xff0c;这种情况&#xff0c;就需要有计算机视觉技术&#xff…...

python:画折线图

import pandas as pd import matplotlib.pyplot as plt from matplotlib.font_manager import FontProperties# 设置新宋体字体的路径 font_path D:/reportlab/simsun/simsun.ttf# 加载新宋体字体 prop FontProperties(fnamefont_path)""" # 读取 xlsx 文件 d…...

Spring Data JPA 与 MyBatisPlus的比较

前言 JPA&#xff08;Java Persistence API&#xff09;和MyBatis Plus是两种不同的持久化框架&#xff0c;它们具有不同的特点和适用场景。 JPA是Java官方的持久化规范&#xff0c;它提供了一种基于对象的编程模型&#xff0c;可以通过注解或XML配置来实现对象与数据库的映射…...

【C++】STL-list的使用

目录 1、list的使用 1.1 list的构造 1.2 list的遍历 1.3 list capacity 1.4 list element access 1.5 容量相关 list是一个带头双向循环链表 1、list的使用 1.1 list的构造 1.2 list的遍历 list只有两种遍历方式&#xff0c;因为没有operator[] 因为list的双向链表&am…...

进度条(小程序)

缓冲区的概念 缓冲区是内存中的一个临时存储区域&#xff0c;用来存放输入或输出数据。在标准 I/O 库中&#xff0c;缓冲区的使用可以提高数据处理的效率。例如&#xff0c;当向终端输出文本时&#xff0c;字符通常存储在缓冲区中&#xff0c;直到缓冲区满或者遇到特定条件时才…...

PyCharm安装教程(超详细图文教程)

一、下载和安装 1.进入PyCharm官方下载&#xff0c;官网下载地址&#xff1a; https://www.jetbrains.com/pycharm/download/ 专业版安装插件放网盘了&#xff0c;网盘下载即可&#xff1a;itcxy.xyz/229.html2.安装 1.下载后找到PyCharm安装包&#xff0c;然后双击双击.ex…...

金蝶BI应收分析报表:关于应收,这样分析

这是一张出自奥威-金蝶BI方案的BI应收分析报表&#xff0c;是一张综合运用了筛选、内存计算等智能分析功能以及数据可视化图表打造而成的BI数据可视化分析报表&#xff0c;可以让企业运用决策层快速知道应收账款有多少&#xff1f;账龄如何&#xff1f;周转情况如何&#xff1f…...

salmon使用体验

文章目录 salmon转录本定量brief模式一&#xff1a;fastq作为输入文件需要特别注意得地方 模式二&#xff1a; bam文件作为输入 salmon转录本定量 brief 第一点是&#xff0c;通常说的转录组分析其中有一项是转录本定量&#xff0c;这是一个很trick的说话&#xff0c;说成定量…...

Ubuntu 20.04 安装 Ansible

使用官方的 Ubuntu PPA 更新包列表&#xff1a; apt update安装软件属性常用命令 apt install software-properties-common添加 Ansible PPA 到系统&#xff1a; add-apt-repository --yes --update ppa:ansible/ansible再次更新包列表以包括新添加的 PPA&#xff1a; apt …...

TypeScript学习笔记:强类型JavaScript的优雅之旅

在前端开发领域&#xff0c;JavaScript以其灵活性和广泛的支持度成为无可争议的王者。然而&#xff0c;随着项目规模的增长&#xff0c;JavaScript的动态类型特性开始暴露出一些问题&#xff0c;比如代码的可维护性、类型错误难以提前发现等。为了解决这些问题&#xff0c;Micr…...

监控异地组网怎么组网?

监控异地组网是指在不同地域的网络环境下&#xff0c;实现对监控设备的远程访问和管理。在传统的网络环境下&#xff0c;由于网络限制和设备配置等问题&#xff0c;监控设备的远程访问往往受到一定的限制和困扰。为了解决这个问题&#xff0c;引入了天联组网技术&#xff0c;实…...

将本地托管模型与 Elastic AI Assistant 结合使用的好处

作者&#xff1a;来自 Elastic James Spiteri, Dhrumil Patel 当今公共部门组织利用生成式人工智能解决安全挑战的一种方式。 凭借其筛选大量数据以发现异常模式的能力&#xff0c;生成式人工智能现在在帮助团队保护其组织免受网络威胁方面发挥着关键作用。 它还可以帮助安全专…...

Linux的内核态和用户态

一、Linux操作系统运行在两种不同的运行模式下&#xff1a;内核态&#xff08;Kernel Mode&#xff09;和用户态&#xff08;User Mode&#xff09; 内核态&#xff08;Kernel Mode&#xff09;&#xff1a; 内核态也称为特权模式或系统模式&#xff0c;是操作系统内核执行代码…...

springboot利用Redis的Geo数据类型,获取附近店铺的坐标位置和距离列表

文章目录 GEO介绍GEO命令行应用添加地理坐标位置获取指定单位半径的全部地理位置列表springboot 的实际应用 GEO介绍 在Redis 3.2版本中&#xff0c;新增了一种数据类型&#xff1a;GEO&#xff0c;它主要用于存储地理位置信息&#xff0c;并对存储的信息进行操作。 GEO实际上…...

Vitis HLS 学习笔记--理解串流Stream(2)

目录 1. 简介 2. 极简的对比 3. 硬件模块的多次触发 4. 进一步探讨 do-while 5. 总结 1. 简介 在这篇博文中《Vitis HLS 学习笔记--AXI_STREAM_TO_MASTER-CSDN博客》&#xff0c;我分享了关于 AXI Stream 接口的实际应用案例。然而&#xff0c;尽管文章中提供了代码示例&…...

Golang | Leetcode Golang题解之第80题删除有序数组中的重复项II

题目&#xff1a; 题解&#xff1a; func removeDuplicates(nums []int) int {n : len(nums)if n < 2 {return n}slow, fast : 2, 2for fast < n {if nums[slow-2] ! nums[fast] {nums[slow] nums[fast]slow}fast}return slow }...

uniapp自定义websocket类实现socket通信、心跳检测、连接检测、重连机制

uniapp自定义websocket类实现socket通信、心跳检测、检测连接、重连机制&#xff0c;仿vue-socket插件功能实现发送序列号进行连接检测&#xff0c;发送消息时42【key,value】格式&#xff0c;根据后端返回数据和需要接收到的数据做nsend与onSocketMessage的修改 //使用socket…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...