您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

归并排序「从入门到放弃」

时间:2019-11-01 10:48:08  来源:  作者:

归并排序

归并排序,是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数。

归并操作

归并操作,也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。

归并排序原理

既然归并排序采用的是分治法,并且依托于归并操作,那么其思想肯定是分而治之。我们知道归并操作是将两个有序的数列合并到一个有序的序列,那么对于一个无序的长序列,可以把它分解为若干个有序的子序列,然后依次进行归并。如果我们说每一个数字都是单独有序的序列,那么只要把原始长序列依次分解,直到每个子序列都只有一个元素的时候,再依次把所有的序列进行归并,直到序列数为1

归并排序「从入门到放弃」

 

归并排序的实现方法

递归法

原理如下(假设序列共有n个元素):

  1. 将原始序列从中间分为左、右两个子序列,此时序列数为2
  2. 将左序列和右序列再分别从中间分为左、右两个子序列,此时序列数为4
  3. 重复以上步骤,直到每个子序列都只有一个元素,可认为每一个子序列都是有序的
  4. 最后依次进行归并操作,直到序列数变为1

参考代码

void Merge(int r[],int r1[],int s,int m,int t)
{
 int i=s;
 int j=m+1;
 int k=s;
 while(i<=m&&j<=t)
 {
 if(r[i]<=r[j])
 r1[k++]=r[i++];
 else
 r1[k++]=r[j++];
 }
 while(i<=m)
 r1[k++]=r[i++];
 while(j<=t)
 r1[k++]=r[j++];
 for(int l=0; l<8; l++)
 r[l]=r1[l];
}
 
void MergeSort(int r[],int r1[],int s,int t)
{
 if(s==t)
 return;
 else
 {
 int m=(s+t)/2;
 MergeSort(r,r1,s,m);
 MergeSort(r,r1,m+1,t);
 Merge(r,r1,s,m,t);
 }
}

迭代法

原理如下(假设序列共有n个元素):

  1. 将序列每相邻两个数进行归并操作,形成ceil(n/2)个序列,排序后每个序列包含两/一个元素
  2. 将序列每相邻的两个有序子序列进行归并操作,形成ceil(n/4)个序列,每个序列包含四/三个元素
  3. 重复步骤2,直到所有元素排序完毕,即序列数为1个

参考代码

void Merge(int*a,int low,int mid,int high)
{
 inti=low,j=mid+1,k=0;
 int *temp=(int*)malloc((high-low+1)*sizeof(int));
 while(i<=mid&&j<=high)
 a[i]<=a[j]?(temp[k++]=a[i++]):(temp[k++]=a[j++]);
 while(i<=mid)
 temp[k++]=a[i++];
 while(j<=high)
 temp[k++]=a[j++];
 memcpy(a+low,temp,(high-low+1)*sizeof(int));
 free(temp);
}
void MergeSort(int*a,int n)
{
 int length;
 for(length=1; length<n; length*=2)
 {
 int i;
 for(i=0; i+2*length-1<=n-1; i+=2*length)
 Merge(a,i,i+length-1,i+2*length-1);
 if(i+length<=n-1)
  Merge(a,i,i+length-1,n-1);
 }
}


Tags:归并排序   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关推荐
归并排序归并排序,是创建在归并操作上的一种有效的排序算法,效率为O(nlogn)。1945年由约翰&middot;冯&middot;诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非...【详细内容】
2019-11-01  Tags: 归并排序  点击:(32)  评论:(0)  加入收藏
冒泡排序时间之所以效率低,就是因为将所有数都一视同仁不做区分挨个比较,这是最普通的做事方法,所以效率也是最普通的,时间复杂度为N的平方;而归并排序效率高,则是采用了分治的思...【详细内容】
2019-10-22  Tags: 归并排序  点击:(40)  评论:(0)  加入收藏
▌简易百科推荐
架构头条 作者 | theinsaneapp.com译者 | 张健欣策划 | 万佳今天,我们会讨论一些不同的东西,例如 Spotify、YouTube、Signal Messenger、Amazon 等科技巨头的推荐算法,以及像 U...【详细内容】
2021-07-15  技术联盟总坛    Tags:推荐算法   点击:(2)  评论:(0)  加入收藏
说起区块链,似乎大家都懂一点,再往细里一问,似乎又都不懂了。比如,你问一个人:为什么要挖矿,挖的到底是啥。怕是没几个明白人。本文就是要给你讲明白!前言人们一说起区块链,就常常说...【详细内容】
2021-07-13  暖男在奋斗的路上    Tags:加密算法   点击:(6)  评论:(0)  加入收藏
2021年5月26日,极狐阿尔法S 华为HI版正式下线,标志着华为进军自动驾驶迈出关键一步,实现了量产。...【详细内容】
2021-07-08  佐思汽车研究    Tags:自动驾驶算法   点击:(9)  评论:(0)  加入收藏
今天讲的是最有深度的抖音算法机制的剖析,解密平台核心算法机制。主要深度讲下抖音是算法机制到底是怎么工作的,我们的帐号标签原型到底是怎么建立起来的,字节跳动的人工智能AI...【详细内容】
2021-07-05  国阜电商    Tags:抖音平台算法   点击:(11)  评论:(0)  加入收藏
RSA非对称加密RSA是一种常用的非对称加密算法,加密和加密使用不同的密钥,常用于要求安全性较高的加密场景,比如接口的验签和接口数据的加密与解密。与非对称加密算法对比,其安全...【详细内容】
2021-07-04  Java架构学习指南  简书  Tags:接口   点击:(12)  评论:(0)  加入收藏
导读:用户标签是个性化推荐、计算广告、金融征信等众多大数据业务应用的基础,它是原始的用户行为数据和大数据应用之间的桥梁,本文会介绍用户标签的构建方法,也就是用户画像技术...【详细内容】
2021-07-02  华章科技    Tags:用户画像   点击:(16)  评论:(0)  加入收藏
随机红包算法,每个人都有自己的实现思路。package com.jmmq.load.jim.algorithm;import java.math.BigDecimal;import java.util.Arrays;import java.util.List;import java....【详细内容】
2021-07-02  非鸽传书  今日头条  Tags:算法   点击:(10)  评论:(0)  加入收藏
在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念、常见算法以及原理、在信息安全的应用等等。 一、概念哈希...【详细内容】
2021-06-25  C语言编程    Tags:哈希算法   点击:(26)  评论:(0)  加入收藏
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Linux天神    Tags:红黑树   点击:(19)  评论:(0)  加入收藏
1. 线性表线性表是一类最简单、最常用的数据结构。简单来说,一个线性表是n个元素的有限序列,其中n&ge;0,通常表示为(a1,a2,...,an)。其特点是,在非空的数据元素集合中:(1)存在唯一的一个...【详细内容】
2021-06-09  数据人plus  今日头条  Tags:数据结构   点击:(37)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条