经典算法巡礼(五) -- 排序之归并排序

归并排序是创建在归并操作上的一种有效排序算法。所谓归并操作,指的是将两个已经排序的序列合并成一个序列的操作。归并排序是分治思想的典型示范。

归并排序具体步骤如下:

  1. 申请大小等于两个已排序序列之和的空间,该空间用来存放合并后的序列;
  2. 设定两个指针,初始位置分别为两个已排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择较小的元素放入合并的空间中(若进行升序排序),并移动指针到下一个位置;
  4. 重复步骤3直至其中某一指针到达序列尾;
  5. 将另一序列剩下的元素直接复制到合并序列中。

golang实现如下:

	// merge方法实现归并排序中的归并操作,将两个已排序数组归并操作成一个已排序数组
	func (this *MergeSort) merge(a []Comparable, compare Compare, lo int, mid int, hi int) {
		i := lo
		j := mid + 1

		arrayBak := make([]Comparable, len(a))
		copy(arrayBak, a)

		for k := lo; k <= hi; k++ {
			if i > mid {
				a[k] = arrayBak[j]
				j++
			} else if j > hi {
				a[k] = arrayBak[i]
				i++
			} else if this.less(arrayBak[i], arrayBak[j], compare) {
				a[k] = arrayBak[i]
				i++
			} else {
				a[k] = arrayBak[j]
				j++
			}
		}
	}

	// Sort1采用自顶向下方法进行归并排序
	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *MergeSort) sort1(a []Comparable, compare Compare, lo int, hi int) {
		if lo >= hi {
			return
		}

		mid := (lo + hi) / 2

		this.sort1(a, compare, lo, mid)
		this.sort1(a, compare, mid+1, hi)
		this.merge(a, compare, lo, mid, hi)
	}

	// Sort2采用自底向上方法进行归并排序,先从子数组为1开始归并操作,逐渐递增,直到归并成完整数组为止
	// Sort中参数类型Comparable为统一的可比较接口,若为整数数组排序,则Comparable为int即可
	// Sort中参数类型Compare为配合Comparable接口的比较方法,若为整数数组排序,则Compare即满足a int < a int即可
	func (this *MergeSort) sort2(a []Comparable, compare Compare) {
		for sz := 1; sz < len(a); sz += sz {
			for lo := 0; lo < len(a)-sz; lo += sz + sz {
				this.merge(a, compare, lo, lo+sz-1, int(math.Min(float64(lo+sz+sz-1), float64(len(a)-1))))
			}
		}
	}

下面我们来考虑下归并排序的效率问题。首先我们假设数组有N个元素,而N的值为2^n,所以采用归并排序的过程,可以用如下图的树状图表示:

图中每一个结点都表示一个merge()方法归并而成的一个数组。这棵树正好有n层。对于0到n-1之间的任意k,自顶向下的第k层有2^k个子数组,每个子数组又包含有2^(n-k)元素,所以归并操作最多需要2^(n-k)次比较。因此,每层的比较操作次数为2^n次,所以n次总共需要n2^n次比较操作。又由于N=2^n,所以归并排序整个数组最多需要n2^n=NlogN次比较操作。当然,每次归并操作最少需要2^(n-k)/2次比较,所以归并排序整个数组的话,最小需要NlogN/2次比较操作。综合上述分析,归并排序需要NlogN/2至NlogN次比较操作,因此其时间复杂度是线性对数型的,即O(NlogN)

可见,归并排序是适合用于大规模数据排序的算法。但不要忘了,归并排序有个明显的缺陷,即她需要申请与排序数组相同大小的数组进行归并操作,在空间利用方面并不是十分理想,因此可能不适合用于空间不宽裕的场合

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

Python dict(字典)

Python dict即字典,是一种非常有用的数据结构,相当于其他语言的Map,这种数据结构采用键值对(key-value)形式存储,具有非常快的查询速度...

3019
来自专栏企鹅号快讯

每周四更面试题:True+True=?

面试题:True + Ture == ? Python 的 “+” 号会根据操作对象数据类型的不同而进行重载,操作对象为数字类型时,它是算术运算符;操作对象为序...

1917
来自专栏lhyt前端之路

js的this、call、apply、bind、继承、原型链0.前言1.this2.call、apply、bind3.从call到继承

这些都是js基础进阶的必备了,有时候可能一下子想不起来是什么,时不时就回头看看基础,增强硬实力。

941
来自专栏有趣的Python

6-Java常用工具类-集合排序

http://www.runoob.com/java/java-generics.html

833
来自专栏Rovo89

JavaScript闭包与箭头函数

862
来自专栏河湾欢儿的专栏

第五节正则

832
来自专栏cs

c++13.0 STL[stack,queue,set,dequeue]

set相关知识点: ---- set:集合,红黑树实现 特点: 1.0 内部的元素根据其值自动排序。 2.0 内部元素只能出现一次。 set数据结...

2316
来自专栏积累沉淀

Python快速学习第四天

第四天: 条件 、循环和其他语句 1、    print 使用逗号输出 - 打印多个表达式也是可行的,但要用逗号隔开 >>> print 'tanggao ',...

18810
来自专栏北京马哥教育

Python 运算符,你了解多少?

? 文 | 云豆 图 | 来源网络 ? 云豆贴心提醒,本文阅读时间6分钟,文末有秘密! 什么是运算符? 本章节主要说明Python的运算符。举个简单的...

4148
来自专栏C/C++基础

字符数组的初始化与赋值

C语言中表示字符串有两种方式,数组和指针,字符数组是我们经常使用的方式。变量的定义包括指明变量所属类型、变量名称、分配空间以及初始化。可以看出,变量的初始化是变...

1552

扫码关注云+社区