C++归并排序算法详解

目录
  • 一.算法简介
  • 二.实现过程
  • 总结

一.算法简介

归并排序算法的平均时间复杂度是O(nlogn)，归并算法的实现就是通过分冶法，将一个待排序列分成一个个小的序列，然后对这些小的序列进行排序，然后进行合并，合并的时候也会进行排序，这样，从整体拆成小块，再从小块合成整体的一个过程。

二.实现过程

1）拆分待排序列

2）进行排序合并

给大家写了一个简单的过程以便大家理解。

这基本就是归并排序的实现原理了，那么代码是怎么实现的呢，下面给大家展示下代码实现。

//时间复杂度是nlogn
#include <iostream>

using namespace std;

void Merge(int a[],int s,int mid,int e,int tmp[]);//归并
void Merge_Sort(int a[],int s,int e,int tmp[]);//有序

int main(){
    int a[1000],tmp[1000];
    int n;
    cin >> n;
    for(int i=0;i<n;i++)cin >> a[i];
    Merge_Sort(a,0,n-1,tmp);//对数组进行排序
    for(int i=0;i<n;i++)cout << a[i] << " ";
    system("pause");
    return 0;
}

void Merge_Sort(int a[],int s,int e,int tmp[]){
    if(s<e){
        int m=(s+e)/2;
        Merge_Sort(a,s,m,tmp);//左边有序
        Merge_Sort(a,m+1,e,tmp);//右边有序
        Merge(a,s,m,e,tmp);//归并
    }
}

void Merge(int a[],int s,int mid,int e,int tmp[]){
    int p1,p2,p=0;
    p1=s,p2=mid+1;
    //判断大小，得到排列顺序
    while(p1<=mid&&p2<=e){
        if(a[p1]<a[p2]){
            tmp[p++]=a[p1++];
        }
        else{
            tmp[p++]=a[p2++];
        }
    }
    //剩余数据自动放到末尾
    while(p1<=mid){
        tmp[p++]=a[p1++];
    }
    while(p2<=e){
        tmp[p++]=a[p2++];
    }
    //将tmp中排好序的数组拷贝到a中
    for(int i=0;i<e-s+1;++i){
        a[s+i]=tmp[i];
    }
}

大家看注释行事，注释基本在关键点都注明了，希望对大家有帮助

总结

到此这篇关于C++归并排序算法详解的文章就介绍到这了,更多相关C++归并排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现归并排序（MergeSort）

    本文实例为大家分享了C++实现归并排序的具体代码,供大家参考,具体内容如下 一.思路:稳定排序 (1)划分:一直调用划分过程,直到子序列为空或只有一个元素为止,共需log2(n): (2)归并:将两个子序列从小到大合并为一个序列 二.实现程序: // 归并排序:(二路归并) // (1)递归分解数组: // (2)合并有序的序列 #include <iostream> using namespace std; // 合并两个有序的序列 template <typename T> v

  • C++编程归并排序算法实现示例

    归并算法开始首先要对一段要有序的数字进行排序 void merg_sort(int* a, int fbegin, int fend, int sbegin, int send, int* b) { int L = fbegin; int R = sbegin; int cursize = fbegin;//z这里不能重0开始 递归后面是按对应开始位置进行赋值的 while (L <= fend && R <= send) { if (a[L] > a[R]) { b[c

  • C++实现归并排序算法

    归并 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 算法描述 归并操作的工作原理如下: 1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置 3.比较两个指针所指向的元素,选择相对小

  • c++归并排序详解

    c++归并排序详解

    说一说归并排序 归并排序:归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n).1945年由约翰·冯·诺伊曼首次提出.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行. 归并排序的核心思想是将两个有序的数列合并成一个大的有序的序列.通过递归,层层合并,即为归并. 如图,从下到上,每一步都需要将两个已经有序的子数组合并成一个大的有序数组,如下是实现合并的具体代码,请

  • C++ 归并排序(merge sort)案例详解

    核心思想:"分"与"合". 主体流程 先将一个序列分成很多个不能再分割的子序列,将各个子序列分别排序后再将子序列合并.其实就是重复两个步骤:[1]分[2]合并. 首先是第一个小问题,怎么分? 比如说一个序列:12 ,23,1,44,233,10,9,8.我们先分成两段:12 ,23,1,44 和 233,10,9,8, 发现还能再分成4段:12 ,23 和 1,44------233,10 和 9,8. 再分成8段:12--23--1--44 和233--10--9

  • C++实现归并排序

    定义:归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 简单的来说,归并排序主要分为三步,一是对数组的划分,二是对数组的排序,三是对数组的合并.划分的大小是可以随自己的想法而设置,但是一般都是以2为单位,这样最小的一组的排序就比较方便. 具体一个简单的例子: 设有数

  • java 中归并排序算法详解

    java 中归并排序算法详解

    java 中归并排序算法详解 归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其

  • C++归并排序算法详解

    C++归并排序算法详解

    目录 一.算法简介 二.实现过程 总结 一.算法简介 归并排序算法的平均时间复杂度是O(nlogn),归并算法的实现就是通过分冶法,将一个待排序列分成一个个小的序列,然后对这些小的序列进行排序,然后进行合并,合并的时候也会进行排序,这样,从整体拆成小块,再从小块合成整体的一个过程. 二.实现过程 1)拆分待排序列 2)进行排序合并 给大家写了一个简单的过程以便大家理解. 这基本就是归并排序的实现原理了,那么代码是怎么实现的呢,下面给大家展示下代码实现. //时间复杂度是nlogn #includ

  • C++实现的归并排序算法详解

    本文实例讲述了C++实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列: 即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程 1.比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到temp[k]中,并令i

  • 可能是你看过最全的十大排序算法详解(完整版代码)

    可能是你看过最全的十大排序算法详解(完整版代码)

    目录 前言 交集排序 冒泡 简单 快速排序 插入排序 直接插入排序 希尔排序 选择排序 简单选择排序 堆排序 归并排序 二路 多路 非比较类 计数排序 桶排序 基数排序 最后 前言 兄弟们,应上篇数据结构的各位要求,今天我开始工作了,开始肝算法,剑指offer还在路上,我真想开车去接它,奈何码神没有驾照的开车,算了,弄排序算法吧,有点长,耐心看啊,原创不易,你们懂的,先上一张图 可以看出排序算法,还是比较多的,算了,不多说了,你我肝完就是出门自带4年实习经验的! 交集排序 冒泡 冒泡我一般也将它

  • python查找与排序算法详解(示图+代码)

    python查找与排序算法详解(示图+代码)

    目录 查找 二分查找 线性查找 排序 插入排序 快速排序 选择排序 冒泡排序 归并排序 堆排序 计数排序 希尔排序 拓扑排序 总结 查找 二分查找 二分搜索是一种在有序数组中查找某一特定元素的搜索算法.搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束:如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较.如果在某一步骤数组为空,则代表找不到.这种搜索算法每一次比较都使搜索范围缩小一半. # 返回 x 在 ar

  • python算法演练_One Rule 算法(详解)

    这样某一个特征只有0和1两种取值,数据集有三个类别.当取0的时候,假如类别A有20个这样的个体,类别B有60个这样的个体,类别C有20个这样的个体.所以,这个特征为0时,最有可能的是类别B,但是,还是有40个个体不在B类别中,所以,将这个特征为0分到类别B中的错误率是40%.然后,将所有的特征统计完,计算所有的特征错误率,再选择错误率最低的特征作为唯一的分类准则--这就是OneR. 现在用代码来实现算法. # OneR算法实现 import numpy as np from sklearn.da

  • python实现决策树C4.5算法详解(在ID3基础上改进)

    python实现决策树C4.5算法详解(在ID3基础上改进)

    一.概论 C4.5主要是在ID3的基础上改进,ID3选择(属性)树节点是选择信息增益值最大的属性作为节点.而C4.5引入了新概念"信息增益率",C4.5是选择信息增益率最大的属性作为树节点. 二.信息增益 以上公式是求信息增益率(ID3的知识点) 三.信息增益率 信息增益率是在求出信息增益值在除以. 例如下面公式为求属性为"outlook"的值: 四.C4.5的完整代码 from numpy import * from scipy import * from mat

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • python中实现k-means聚类算法详解

    python中实现k-means聚类算法详解

    算法优缺点: 优点:容易实现 缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢 使用数据类型:数值型数据 算法思想 k-means算法实际上就是通过计算不同样本间的距离来判断他们的相近关系的,相近的就会放到同一个类别中去. 1.首先我们需要选择一个k值,也就是我们希望把数据分成多少类,这里k值的选择对结果的影响很大,Ng的课说的选择方法有两种一种是elbow method,简单的说就是根据聚类的结果和k的函数关系判断k为多少的时候效果最好.另一种则是根据具体的需求确定,比如说进行衬衫尺寸的聚

  • Python编程实现蚁群算法详解

    Python编程实现蚁群算法详解

    简介 蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值. 定义 各个蚂蚁在没有事先告诉

随机推荐