漫画:什么是归并排序?

2019 年 10 月 17 日 程序人生

作者 | 小灰
责编 | 伍杏玲

—————  第二天  —————

————————————

举个例子,有A、B、C、D、E、F、G、H一共8个武术家参考参加比武大会。

第一轮,两两一组,有4名选手胜出(四分之一决赛)

第二轮,两两一组,有两名选手胜出(半决赛)

第三轮,仅剩的两人一组,冠军胜出(总决赛)

归并排序和擂台赛,有什么相同和不同之处呢?让我们以下面这个数组来举例说明:

归并排序就像是组织一场元素之间的“比武大会”,这场比武大会分成两个阶段:

1.分组

假设集合一共有n个元素,算法将会对集合进行逐层的折半分组。

第一层分成两个大组,每组n/2个元素;

第二层分成4个小组,每组n/4个元素;

第三层分成8个更小的组,每组n/8个元素;

......

一直到每组只有一个元素为止。

这样一来,整个数组就分成了一个个小小的“擂台”。

2.归并

既然分了组,接下来就要开始“比武”了。

归并排序和擂台赛有一个很大的不同,就是擂台赛只需要决定谁是老大,而并不关心谁做老二和老三;归并排序的要求复杂一些,需要确定每一个元素的排列位置。

因此,当每个小组内部比较出先后顺序以后,小组之间会展开进一步的比较和排序,合并成一个大组;大组之间继续比较和排序,再合并成更大的组......最终,所有元素合并成了一个有序的集合。

这个比较与合并的过程叫做归并,对应英文单词merge,这正是归并排序名字的由来。

归并操作需要哪三个步骤呢?我们以两个长度为4的集合为例:

第一步,创建一个额外大集合用于存储归并结果,长度是两个小集合之和。(p1,p2,p是三个辅助指针,用于记录当前操作的位置)

第二步,从左到右逐一比较两个小集合中的元素,把较小的元素优先放入大集合。

由于1<2,所以把元素1放入大集合,p1和p各右移一位:

由于2<3,所以把元素2放入大集合,p2和p各右移一位:

由于3<7,所以把元素3放入大集合,p1和p各右移一位:

由于5<7,所以把元素5放入大集合,p1和p各右移一位:

由于6<7,所以把元素6放入大集合,p1和p各右移一位:

此时左侧的小集合已经没有元素可用了。

第三步,从另一个还有剩余元素的集合中,把剩余元素按顺序复制到大集合尾部。

这样一来,两个有序的小集合就归并成了一个有序的大集合。

   
   
     
static public void mergeSort(int[] arrayint start, int end){

if(start < end){

//折半成两个小集合,分别进行递归

int mid=(start+end)/ 2;

        mergeSort( array, start, mid);

        mergeSort( array, mid+ 1, end);

//把两个有序小集合,归并成一个大集合

        merge( array, start, mid, end);

}

}

static private void merge(int[] arrayint start, int mid, int end){

//开辟额外大集合,设置指针

int[] tempArray =  new  int[end-start+ 1];

int p1=start, p2=mid+ 1, p= 0;

//比较两个小集合的元素,依次放入大集合

while(p1<=mid && p2<=end){

if( array[p1]<= array[p2])

            tempArray[p++]= array[p1++];

else

            tempArray[p++]= array[p2++];

}

//左侧小集合还有剩余,依次放入大集合尾部

while(p1<=mid)

        tempArray[p++]= array[p1++];

//右侧小集合还有剩余,依次放入大集合尾部

while(p2<=end)

        tempArray[p++]= array[p2++];

//把大集合的元素复制回原数组

for ( int i= 0; i<tempArray.length; i++)

         array[i+start]=tempArray[i];

}

public static void main(String[] args) {

int[]  array = {  58639217 };

    mergeSort( array0array.length -1);

System.out.println(Arrays.toString( array));

}

 热 文 推 荐 
在办公室装警报、参加杨超越编程大赛——“开发者之友”声网Agora团队是怎样炼成的?
高级软件工程师教会我的那些事儿
面向 DeadLine 编程?软件项目老延期怎么破

巨头垂涎却不能染指,loT 数据库风口已至

大规模1.4亿中文知识图谱数据,我把它开源了

太鸡冻了!我用Python偷偷查到暗恋女生的名字

【建议收藏】数据中心服务器基础知识大全

☞“国家队”入局! 中移动、银联等宣布区块链服务网络(BSN)正式内测!

为什么北京西二旗的程序员从不点外卖?
  
  
    
你点的每个“在看”,我都认真当成了喜欢
     
     
       

登录查看更多
0

相关内容

排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
最新《自动微分手册》77页pdf
专知会员服务
95+阅读 · 2020年6月6日
【资源】100+本免费数据科学书
专知会员服务
105+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
335+阅读 · 2020年3月15日
算法与数据结构Python,369页pdf
专知会员服务
160+阅读 · 2020年3月4日
知识神经元网络 KNN(简介),12页pdf
专知会员服务
13+阅读 · 2019年12月25日
【干货51页PPT】深度学习理论理解探索
专知会员服务
58+阅读 · 2019年12月24日
图解NumPy,这是理解数组最形象的一份教程了
机器之心
5+阅读 · 2019年7月12日
深度学习面试100题(第71-75题)
七月在线实验室
5+阅读 · 2018年8月2日
无监督学习才不是“不要你管”
MOOC
4+阅读 · 2018年4月13日
图解机器学习的常见算法
机器学习算法与Python学习
5+阅读 · 2018年4月2日
图解机器学习
深度学习世界
3+阅读 · 2017年11月24日
利用 TensorFlow 实现排序和搜索算法
机器学习研究会
5+阅读 · 2017年11月23日
机器学习(26)之K-Means实战与调优详解
机器学习算法与Python学习
4+阅读 · 2017年11月19日
【直观详解】什么是PCA、SVD
机器学习研究会
4+阅读 · 2017年11月10日
漫画:什么是Bitmap算法?
程序猿
3+阅读 · 2017年8月19日
机器学习(4)之线性判别式(附Python源码)
机器学习算法与Python学习
13+阅读 · 2017年7月11日
Arxiv
33+阅读 · 2019年11月7日
Arxiv
7+阅读 · 2019年10月6日
The Matrix Calculus You Need For Deep Learning
Arxiv
10+阅读 · 2018年7月2日
Arxiv
3+阅读 · 2018年5月21日
Arxiv
4+阅读 · 2018年3月19日
Arxiv
11+阅读 · 2018年1月11日
VIP会员
相关VIP内容
最新《自动微分手册》77页pdf
专知会员服务
95+阅读 · 2020年6月6日
【资源】100+本免费数据科学书
专知会员服务
105+阅读 · 2020年3月17日
机器学习速查手册,135页pdf
专知会员服务
335+阅读 · 2020年3月15日
算法与数据结构Python,369页pdf
专知会员服务
160+阅读 · 2020年3月4日
知识神经元网络 KNN(简介),12页pdf
专知会员服务
13+阅读 · 2019年12月25日
【干货51页PPT】深度学习理论理解探索
专知会员服务
58+阅读 · 2019年12月24日
相关资讯
图解NumPy,这是理解数组最形象的一份教程了
机器之心
5+阅读 · 2019年7月12日
深度学习面试100题(第71-75题)
七月在线实验室
5+阅读 · 2018年8月2日
无监督学习才不是“不要你管”
MOOC
4+阅读 · 2018年4月13日
图解机器学习的常见算法
机器学习算法与Python学习
5+阅读 · 2018年4月2日
图解机器学习
深度学习世界
3+阅读 · 2017年11月24日
利用 TensorFlow 实现排序和搜索算法
机器学习研究会
5+阅读 · 2017年11月23日
机器学习(26)之K-Means实战与调优详解
机器学习算法与Python学习
4+阅读 · 2017年11月19日
【直观详解】什么是PCA、SVD
机器学习研究会
4+阅读 · 2017年11月10日
漫画:什么是Bitmap算法?
程序猿
3+阅读 · 2017年8月19日
机器学习(4)之线性判别式(附Python源码)
机器学习算法与Python学习
13+阅读 · 2017年7月11日
相关论文
Top
微信扫码咨询专知VIP会员