首页
登录 | 注册

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

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

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

 

一、合并两个有序数组

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

 

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

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

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

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

 

2.代码实现

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

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

 

 

二、归并排序

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

 

1.归并排序示意图

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

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

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

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

2、上述过程的代码实现

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

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

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

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

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

 

 

三、测试用例

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

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

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

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

 

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

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

 


相关文章

  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • Spring的历史及哲学
    Spring的历史和哲学 1.Spring 历史 时间回到2002年,当时正是 Java EE 和 EJB 大行其道的时候,很多知名公司都是采用此技术方案进行项目开发.这时候有一个美国的小伙子认为 EJB 太过臃肿,并不是所有的项目都需要使 ...
  • 算法推导过程参见[dijkstra算法推导详解] 此文为[dijkstra算法代码实现] https://www.cnblogs.com/Halburt/p/10767389.html package a; import java.util ...
  • Android6.0 源码修改之 Contacts应用
    一.Contacts应用的主界面和联系人详情界面增加顶部菜单添加退出按钮 通过Hierarchy View 工具可以发现 主界面对应的类为 PeopleActivity 联系人详情界面对应的类为 QuickContactActivity 左 ...
  •   计算属性是基于响应式依赖进行缓存的,只有在相关响应式依赖发生改变时才会重新求值,这种缓存机制在求值消耗比较大的情况下能够显著提高性能. 一.计算属性初始化   Vue 在做数据初始化时,通过 initComputed() 方法初始化计算 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.076 s.
京ICP备10005923号