算法与数据结构(十五) 归并排序(Swift 3.0版)

上篇博客我们主要聊了堆排序的相关内容,本篇博客,我们就来聊一下归并排序的相关内容。归并排序主要用了分治法的思想,在归并排序中,将我们需要排序的数组进行拆分,将其拆分的足够小。当拆分的数组中只有一个元素时,则这个拆分的数组是有序的。然后我们将这些有序的数组进行两两合并,在合并过程中进行比较,合并生成的新的数组仍然是有序的。然后再次将合并的有序数组进行合并,重复这个过程,知道整个数组是有序的。

下方我们先给出两个有序数组合并的示意图以及代码,然后给出归并排序的相关内容。归并排序其实就是拆分+合并。废话少说,开始今天的内容。

一、合并两个有序数组

在本篇博客的第一部分我们先给出合并两个有序数组的示意图以及相关代码,在归并排序时,我们会使用到此部分的内容。下方会给出两个有数数组的合并,并且会给出相应的代码实现。

1.有序数组合并的示意图

因为两个有序数组在合并后的新的数组仍然是有序的,所以我们需要对有序数组中的元素进行比较。每次从两个数组中取出最小的那个元素,然后将两个元素进行比较,将最小的那个元素放入到新的数组中。下方就是有序数组合并的示意图。

  • 首先从两个有序数组中取出最小的值,如下所示。我们将9和10取出后进行比较,将较小的9存入我们新的数组中。
  • 重复上个步骤,如果有一个数组中的元素被取完,将另一个数组中剩余的元素直接追加到我们的新的数组中即可。

2.代码实现

根据上述示意图给出相关的代码实现并不困难,下方就是上述过程的代码实现。下方这个mergeArray()函数,就是将两个有序数组合并成一个新的有序数组的具体代码实现。mergeArray()的两个参数就是即将合并的两个有序数组,而返回值就是合并后新的有序的数组。代码比较简单,在此就不做过多赘述了。

二、归并排序

上述实现完两个有序数组合并成新的有序数组完毕后,接下来就该归并排序出场了。在归并排序过程中,会使用到上述的内容。因为我们将无序数列进行分割后,就会不断调用上述的合并代码,将小的有序的数组合并成较大的有序数组,再次合并,直到我们原始的数组是有序的为止。下方会给出相应的示意图以及归并排序的Swift代码实现。

1.归并排序示意图

下方就是我们归并排序的示意图,稍后的代码实现也是根据下方的示意图来写的。所以对下方示意图的充分理解还是很有必要的。在下方示意图中,从上往下就是我们归并排序的整个过程。我们需要排序的序列为[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]。下方是对每一步的解析:

  • 首先我们将需要排序的序列进行拆分,拆分成足够小的数组。也就是拆分的数组中只有一个元素。无序数组拆分的所有数组因为其中只含有一个元素,所以都是有序的。我们就可以对这些有序的小数组进行合并了。
  • 将拆分的多个有序数组调用第一部分实现的mergeArray()函数进行两两合并,合并后的新数组仍然是有序的。我们再次对这些合并产生的数组进行两两合并,直到所有被拆分的数组有重新被合并成一个大数组位置。这个重新合并生成的数组就是有序的,也就是归并排序所产生的有序序列。

下方就是拆分+多次合并的详细过程,最终我们得到的就是一个有序序列。如下所示:

2、上述过程的代码实现

根据上述的示意图,我们给出相应的代码实现应该是比较容易的。就是将我们的无序数组进行拆分,然后进行多次合并,最后合并成一个大的有序数组。下方代码就是对上述过程的描述。

  • 在下方代码中的第一个框中就是将我们的无序数组进行拆分。被拆分的小的有序的数组存入到tempArray中,便于我们下方遍历进行合并。
  • 第二个框就是对tempArray中被拆分的数组进行遍历,在遍历的过程中进行两两合并,将合并的数组再次存入到tempArray中,直到tempArray中只含有一个数组为止。

而tempArray最终的数组就是归并排序的最终结果。下方是整个过程,代码并不复杂。

上述代码的实现在有些数据结构的教程上是使用递归实现的,即使是不使用递归实现也比上述代码要麻烦。

三、测试用例

对上述代码的测试我们仍然会使用到我们之前的测试用例,因为上述排序类仍然遵循我们之前定义的SortType协议。下方就是本篇博客的测试用例,也是所有排序方式的测试用例。这个MergeSort类就是我们归并排序的类。

上述用例的输出结果如下,从输出结果中,我们就能明显的看出拆分和合并的整个过程。如下所示:

本篇博客对堆排序的介绍就先到这儿,下篇博客我们将会介绍“快速排序”的详细内容。本篇博客的相关代码依然会在github上进行分享,下方是github分享地址,如下所示:

github代码分享地址:https://github.com/lizelu/DataStruct-Swift/tree/master/AllKindsOfSort 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大闲人柴毛毛

稳扎稳打JavaScript(四)——闭包

闭包是JS语言的又一大核心,如果要从内存角度充分理解闭包的话,建议大家先预习下先前的几篇讲博客: 稳扎稳打JavaScript(一)——作用域链 稳扎稳...

37760
来自专栏星回的实验室

js重修课[四]:函数

函数有两种定义方法:定义表达式如var f = function(){};和声明语句如function f(){}。须知在变量提前这一现象中,声明语句可被提前,...

15820
来自专栏小樱的经验随笔

Java学习笔记【持续更新】

一个简单的java程序如下: class Sakura {   public static void main(String[] arges)   {     ...

43550
来自专栏Kevin-ZhangCG

[ Java学习基础 ] Java构造函数

29660
来自专栏数据结构笔记

数据结构(四):栈的应用之表达式求值

用户从控制台输入一个数学表达式(所有输入均合法),数学表达式只包含四则运算,程序需输出表达式对应的结果,如:

26020
来自专栏Redis

Redis类型之lists类型

9、rpoplpush 从第一个list的尾部移除元素并添加到第二个list的头部,最后返回被移除的元素值,整个操作是原子的,如果第一个list是空或者不存在...

15900
来自专栏python读书笔记

python 数据分析基础 day2-数值及字符串数值字符串

今天说一下python 的内置的数据类型以及相应的操作方法 数值 数值类型主要有整数(int)、浮点数(flooat)、长整数(long)、复数(complex...

345100
来自专栏和蔼的张星的图像处理专栏

50. 数组剔除元素后的乘积两个遍历

给定一个整数数组A。 定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。...

13340
来自专栏liulun

Nim教程【八】

有序类型 值连续的枚举类型、整型、字符类型、布尔类型(还有这些类型的变种), 都可以称之为有序类型,Nim为有序类型提供了一系列特殊的方法 方法签名 方法...

22860
来自专栏程序生活

Python中defaultdict用法

21960

扫码关注云+社区

领取腾讯云代金券