归并排序

当前位置:首页D88尊龙集团官方唯一网站 >

D88尊龙集团官方唯一网站

归并排序

时间:2019-06-10本站浏览次数:355

       

本篇是讲述数据结构的经典排序算法-归并排序。大约只占用5分钟时间,本篇讲述方式将不同于其他博客方式,希望大家可以对归并排序有更深的了解(起码进大公司,可以手写出归并排序)。

一、准备食材

所谓归并就是将两个已经排好序的队列,合成为一个有序队列。英文中一般用merge来形容。

下面是一个待排序数据

1376254

我们可以把这些数值,看成若干个独立的队列,而每个队列只含有一个队列,含有一个数据的队列当然是有序的。

现在我们准备两个相邻的两个队列合成一个队列,最后一组不用合并;结果如下:

我们得到的数据在每一个数组内都是有序的,现在每个小组有两个元素,只有最后一个小组有一个元素。然后我们再把相邻的一组进行合并,以此类推……结果如下:

上面是手动的解释归并的大概思想,相信大家有点了解啦。

 

二、下锅

1.思想

图中已经给出了两个有序的队列,我们把它放在数组中。我们要得到一个新的有序队列,归并的结果需要一个新的存储空间,来存储归并好的这个队列。

(1)首先我们要开辟一个大小为两个待归并之和空间的数组存储空间,如下图

(2)然后两个指针,分别指向待排队列的第一个元素,如下图

然后比较两个指针指向位置值的大小,较小的元素放在新建的队列中,并相应的移动指针,如下图

这个过程可以一直重复下去,直到某一个队列元素耗尽,则另一个队列的剩余元素都拷贝到新队列尾部。如下图

 

下面我们直接敲代码,用OC的方式。(演示的代码是将两个有序的数组变成一个有序的数组)可以直接运行(里面讲解了思路)

#import "ViewController.h"@interface ViewController ()@property (nonatomic,strong)NSMutableArray *arrC;@end@implementation ViewController- (NSMutableArray *)arrC{ if (!_arrC) { _arrC = [NSMutableArray array]; } return _arrC;}- (void)viewDidLoad { [super viewDidLoad]; NSMutableArray *arrA = [[NSMutableArray alloc]initWithObjects:@(1),@(4),@(5),@(8),@(9),@(15), nil]; NSMutableArray *arrB = [[NSMutableArray alloc]initWithObjects:@(2),@(7),@(11),@(14), nil]; self.arrC = [self mergeArrWithArrA:arrA withArrB:arrB]; NSLog(@"%@",self.arrC); }- (NSMutableArray *) mergeArrWithArrA:(NSMutableArray *)arrA withArrB:(NSMutableArray *)arrB{ int a_i = 0;//代表数组A指针下标 int b_i = 0;//代表数组B指针下标 int c_i = 0;//代表数组C指针下标 //下面是核心代码,请先看第一部分,再看第二部分,最后第三部分 //第二部分:确定循环条件 while (a_i < arrA.count && b_i <arrB.count) { //第一部分:主要是比较 //分别取出数组A和数组B对应的值比较 if ([arrA[a_i] integerValue] <= [arrB[b_i]integerValue]) { self.arrC[c_i++] = arrA[a_i++];//意思是当小于时,arrA下标递进,继续比较 }else{ self.arrC[c_i++] = arrB[b_i++];//意思是当大于时,arrB下标递进,继续比较 } } //第三部分:处理余下数据 while (a_i < arrA.count) { self.arrC[c_i++] = arrA[a_i++];//数组A没有排完,直接插入尾部(因为数组A有序) } while (b_i < arrB.count) { self.arrC[c_i++] = arrB[b_i++];//数组B没有排完,直接插入尾部(因为数组A有序) } return self.arrC; }

运行结果如下

 以上就是归并排序的思想和代码实现,当然还有其他方式思路(感觉这个比较容易吧)欢迎大家指正!!!

如果想直接下载代码,github地址:https://github.com/zxy1829760/-Demo




公司地址:经营地址:广西桂平市郁江桥头美国埃孚润滑油
联系人:郭志宏 15272889964
杨四平 15861750868
电话:13532690182 传真:9wi559@sina.com
邮箱:tnduk9o@sohu.com

粤公网安备 44030702001579号

尊龙集团官方备用客户端@