402v

最近在刷LeetCode，顺便把之前不会、掌握的不熟练的算法都看一遍，今天要说的是归并排序。

首先说明一下算法的实现环境：

算法实现：递归实现和迭代实现两种

算法语言：Ruby

数据结构：数组

###归并排序的基本思路归并排序与快速排序和堆排序有所不同，排序过程中不进行元素交换，而进行Merge，即所谓的归并。

基本思路：先将数组内的元素两两组合排序，然后再将排好序的各个分组继续两两组合直到最终完成整个数组的排序。

由此可见：归并排序是分治法（Divide and Conquer）非常典型的应用，采用递归实现较为方便，且各层分治递归可以同时进行。

###归并排序的Ruby实现

####递归版本及时间复杂度分析

# @param {Integer[]} nums 	- 目标数组
# @param {Integer[]} reg	- 用于插入的缓冲区
# @param {Integer[]} head	- 当前递归归并的头部索引
# @param {Integer[]} tail	- 当前递归归并的尾部索引
# @return {Integer[]} nums
def merge_sort(nums, reg, head, tail)
	# 递归出口：头部大于等于尾部时终止当前递归，即步长为0时
	if head >= tail then
#		puts("in return: head:#{head} tail:#{tail}")
		return
	end
	
#	puts("in recursive: head:#{head} tail:#{tail}")
	
	# -- 递归步长：将当前归并List拆成两个子List
	mid = ((tail - head)>>1) + head # 第一个步长数组尾部（第二个步长数组头部的上一个元素），右移一位相当于除以2
	
	# 第一个子List
	head1 = head
	tail1 = mid
	
	# 第二个子List
	head2 = mid + 1
	tail2 = tail
	
	# -- 递归调用
	merge_sort(nums, reg, head1, tail1)
	merge_sort(nums, reg, head2, tail2)
	
	# -- 递归基本操作，对当前的两个数组做merge
	# 当前元素插入到临时数组中的位置
	i = head
	
	# 处理当前组内两个数组的共有部分
	while head1 <= tail1 && head2 <= tail2 do
		if nums[head1] < nums[head2] then
			reg[i] = nums[head1]
			head1 += 1
		else
			reg[i] = nums[head2]
			head2 += 1
		end
		i += 1
	end
	
	# 其中一个数组的剩余部分
	while head1 <= tail1 do
		reg[i] = nums[head1]
		head1 += 1
		i += 1
	end
	
	while head2 <= tail2 do
		reg[i] = nums[head2]
		head2 += 1
		i += 1
	end
	
	(head..tail).each do |i|
		nums[i] = reg[i]
	end
	
	nums
end

nums = [1,2000,3,6,3,2,9,0,1000,29,2]
t_nums = Array.new(nums.length)
merge_sort(nums, t_nums, 0, nums.length-1)
puts("result:#{nums}")

递归版本的算法平均时间复杂度简要分析：

记目标数组长度nums.length为n

归并排序中的基本操作有：比较和插入，由算法可知比较操作的次数要少于插入操作的次数。因此分析时间复杂度时以插入操作为基本操作。

用递归树来分析插入次数比较简单。具体的分析可以看这里，后续再想想有没有什么更好的理解方法。

归并排序的迭代版本实现思路和递归版本稍有不同，这里也实现了一下。

####迭代版本及时间复杂度分析

def merge_sort(nums)
	if nums.length < 2 then return nums end
	
	step = 1 # 初始步长
	
	t_nums = Array.new(nums.length)
	
	# 确定当次步长，每次for循环完成整个数组的一趟归并
	while step < nums.length do
	
#		puts("current step:#{step}")
	
		# 根据当前步长，对当前数组进行两两分组归并，每次for循环完成相邻两个步长数组的归并
		(0...nums.length).step(2*step).each do |start|
		
			low = start # 第一个步长数组头部
			mid = [start + step, nums.length].min # 第二个步长数组头部（第一个步长数组尾部的下一个元素）
			high = [start + 2*step, nums.length].min # 第二个步长数组尾部，长度不能超过nums的长度，即当前数组可能不足step长度
			
			# 两个数组当前归并元素的索引
			start1 = low
			start2 = mid
			
			# 两个数组当前归并元素索引的边界值
			end1 = mid
			end2 = high
			
			# 当前元素插入到临时数组中的位置
			i = start
			
			# 处理当前组内两个数组的共有部分
			while start1 < end1 && start2 < end2 do
				if nums[start1] < nums[start2] then
					t_nums[i] = nums[start1]
					start1 += 1
				else
					t_nums[i] = nums[start2]
					start2 += 1
				end
				i += 1
			end
			
			# 其中一个数组的剩余部分
			while start1 < end1 do
				t_nums[i] = nums[start1]
				start1 += 1
				i += 1
			end
			
			while start2 < end2 do
				t_nums[i] = nums[start2]
				start2 += 1
				i += 1
			end
		end
		
		# 一趟归并完成，更新nums
		nums,t_nums = t_nums,nums
		
#		puts("current nums:#{nums}")
		
		# 更新下一次步长
		step += step
	end
end

nums = [1,2000,3,6,3,2,9,0,1000,29,2]
merge_sort(nums)
puts("result:#{nums}")

迭代版本时间复杂度分析更直接一些：

将数组长度nums.length记为n

基本操作仍然是插入；
第一层while循环确定步长，循环次数是logn；
接下来的each循环和while循环看似两层，实际上是对nums中的每个元素做一次插入操作，因此执行次数为n。

综上，平均时间复杂度为O(nlogn)。

###归并排序的空间时间复杂度

归并排序的效率也是比较高的，平均时间复杂度和最坏时间复杂度都为O(nlogn)。

使用数组存储下空间复杂度为O(n)，使用链表存储下空间复杂度可以降到O(1)。

###与其他算法的比较经验上讲，归并排序的效率要低于随机化的快速排序，数据量越大，差异越明显。归并排序后期合并的操作所花费的时间随着数据量增大而增加。

LeetCode实战 - 归并排序

评论 · 0