数据结构和算法14 之归并排序-阿里云开发者社区

开发者社区> shy丶gril> 正文

数据结构和算法14 之归并排序

简介:
+关注继续查看

  归并算法的中心是归并两个已经有序的数组。归并两个有序数组A和B,就生成了第三个数组C,数组C包含数组A和B的所有数据项,并且使它们有序的排列在数组C中。首先我们来看看归并的过程,然后看它是如何在排序中使用的。

        假设有两个有序数组,不要求有相同的大小。设数组A有4个数据项,数组B有6个数据项,它们要被归并到数组C中,开始时数组C有10个存储空间,归并过程如下图所示:


        归并排序的思想是把一个数组分成两半,排序每一半。然后用merge方法将数组的两半归并成一个有序的数组。被分的每一半使用递归,再次划分排序,直到得到的子数组只含有一个数据项为止。正如上面所说的,归并排序需要额外的一个和AB两个数组总和相等的空间,如果初始数组几乎沾满了整个存储器,那么归并排序就不能工作了。

        归并排序的思想很简单,下面我们来看看具体实现:

[java] view plain copy
 在CODE上查看代码片派生到我的代码片
  1. public void mergeSort(int[] source) {  
  2.     int[] workSpace = new int[source.length];  
  3.     recMergeSort(source,workSpace, 0, source.length-1);  
  4. }  
  5.   
  6. private void recMergeSort(int[] source, int[] workSpace, int lowerBound, int upperBound) {  
  7.     if(lowerBound == upperBound) {  
  8.         return;  
  9.     }  
  10.     else {  
  11.         int mid = (lowerBound + upperBound) / 2;  
  12.         recMergeSort(source, workSpace, lowerBound, mid); //左边排  
  13.         recMergeSort(source, workSpace, mid+1, upperBound); //右边排  
  14.         merge(source, workSpace, lowerBound, mid+1, upperBound);//归并  
  15.     }  
  16. }  
  17.   
  18. private void merge(int[] a, int[] workSpace, int lowPtr, int highPtr, int upperBound) {  
  19.     int j = 0;  
  20.     int lowerBound = lowPtr;  
  21.     int mid = highPtr - 1;  
  22.     int n = upperBound - lowerBound + 1;  
  23.     while(lowPtr <= mid && highPtr <= upperBound) {  
  24.         if(a[lowPtr] < a[highPtr]) {  
  25.             workSpace[j++] = a[lowPtr++];  
  26.         }  
  27.         else {  
  28.             workSpace[j++] = a[highPtr++];  
  29.         }  
  30.     }  
  31.     while(lowPtr <= mid) {  
  32.         workSpace[j++] = a[lowPtr++];  
  33.     }  
  34.       
  35.     while(highPtr <= upperBound) {  
  36.         workSpace[j++] = a[highPtr++];  
  37.     }  
  38.       
  39.     for(j = 0; j < n; j++) {  
  40.         a[lowerBound + j] = workSpace[j];  
  41.     }  
  42. }  

        算法分析:归并排序的运行时间最差、最好和平均都是O(NlogN),但是它需要额外的存储空间,这在某些内存紧张的机器上会受到限制。归并算法是由分割和归并两部分组成的,对于分各部分,如果我们使用二分查找,时间是O(NlogN),在最后归并的时候时间是O(N),所以总时间是O(NlogN)。空间复杂度为O(N)。

        归并排序是稳定的,由于没有发生数据交换,所有当a=b的时候,a一开始如果在b前面,则其每一次合并后仍然在b前面,故该排序算法是稳定的。

        归并排序就写这么多,如有错误之处,欢迎留言指正~


转载:http://blog.csdn.net/eson_15/article/details/51193139

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
使用 TiDB Lightning 恢复 Kubernetes 上的集群数据
本文介绍了如何使用 TiDB Lightning 快速恢复 Kubernetes 上的 TiDB 集群数据。 TiDB Lightning 包含两个组件:tidb-lightning 和 tikv-importer。在 Kubernetes 上,tikv-importer 位于单独的 Helm chart 内,被部署为一个副本数为 1 (replicas=1) 的 StatefulSet;tidb-lightning 位于单独的 Helm chart 内,被部署为一个 Job。 为了使用 TiDB Lightning 恢复数据,tikv-importer 和 tidb-lightning
14 0
排序算法大数据量测试代码
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Collections; using System.Diagnostics; using System.IO; namespace Sort { class Program
813 0
二路归并排序 代码实例
  感觉好久没有写排序程序了,C语言有qsort()函数,C++有sort()函数,java语言有Arrays类(主要这个不是Array)。今天写了一下归并排序还有点费劲呀。晚上回来写写。   归并排序就是采用分治法进行排序:   (1)将一个数组分成小的2个数组分别进行排序;   (2)之后...
825 0
排序算法(四):归并排序
归并排序是通过分治的方式,将待排序集合拆分为多个子集合,对子集合排序后,合并子集合成为较大的子集合,不断合并最终完成整个集合的排序。 以下所讲归并都是指二路归并: 之前的冒泡、选择和插入排序都是维持一个待排序集合和一个已排序集合,在每次的迭代过程中从待排序集合中移动一个元素到已排序集合中,通过不断的迭代来完成排序,所以需要进行的迭代次数一般都是 级别。
777 0
数据智能,触手可及!袋鼠云数栈推出 数据科学平台 DTinsight.Science
一句话了解DTinsight.Science DTinsight.Science是「可视化建模与交互式代码编写于一体的机器学习作业探索平台」,实现数据接入、可视化实验建模、Notebook编程、模型训练、模型部署、任务运维等开发场景,帮助企业构建算法服务能力,提供高效、安全、稳定的算法运行环境。
2411 0
+关注
1878
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载