归并排序的非递归实现
非递归的实现一直想不明白，直到看了这位大哥的博客，茅塞顿开。非常感谢这位大哥。博客地址：博客地址
递归实现是将复杂问题一步一步细分为简单的子问题，直到最小子问题的时候，开始合并。
image.png
非递归刚好相反：从最小子问题开始一步一步解决，直到复杂的问题。
image.png
由图片可知：
第一次：我们将数组分为 8个子数组 每个数组 1 个元素，对相邻的两个数组进行排序合并。
第二次：我们将数组分为 4个子数组 每个数组 2 个元素，对相邻的两个数组进行排序合并。
第三次：我们将数组分为 2个子数组 每个数组 4 个元素，对相邻的两个数组进行排序合并。
至此：排序完毕。
因此：
第一步：划分每个子数组元素的个数（也就是子数组的长度)
1. 第一次 每个子数组元素 个数 为 1.
2. 第二次 每个子数组元素 个数 为 2.
3. 第三次 每个子数组元素 个数 为 4.
可以看出来 每个子数组元素个数 以2的倍数递增
i = 1 #子数组长度
while i < len(seq):
i *= 2
第二步：对每个相邻的数组进行排序合并。
假设 seq = [5,4,0,3,1,6,2,7]
首先：求得要合并的两个相邻数组的区间 [low:mid) [mid:height)
1. 当子数组长度为 1 的时候 要合并的相邻两个数组的区间为：
[0,1) [1,2) [2,3) [3,4) [4,5) [5,6) [6,7) [7,8) 子数组长度为 1
2. 子数组长度为 2 要合并的相邻两个数组的区间为：
[0,2) [2,4) [4,6) [6,8) 子数组长度为 2
3. 子数组长度为 4 要合并的相邻两个数组的区间为：
[0,4) [4,8) 子数组长度为 4
下面来求 区间中的 low mid height:
1. 当子数组为1的时候：
low mid height 分别等于：
0：1：2 i = 1 low = 0 mid = low + 1 height = low + 2
2：3：4 i = 1 low = 2 mid = low + 1 height = low + 2
4：5：6 i = 1 low = 4 mid = low + 1 height = low + 2
6：7：8 i = 1 low = 6 mid = low + 1 height = low + 2
抽象为： i = 1 low = low + 2 * i mid = low + i height = low + 2i
2. 当子数组为2的时候：
low mid height 分别等于：
0：2：4 i = 2 low = 0 mid = low + 2 height = low + 4
4：6：8 i = 2 low = 4 mid = low + 2 height = low + 4
抽象为： i = 2 low = low + 2 * i mid = low + i height = low + 2 * i
3. 当子数组为4的时候：
low mid height 分别等于：
0：4：8 i = 4 low = 0 mid = low + 4 height = low + 2 i
抽象为： i = 4 low = low + 2i mid = low + 4 height = low + 2i
综上所述：抽象出求low mid height 通用公式：
low = low + 2 x i
mid = low + i
height = low + 2 x i
seq = [5, 4, 3, 0, 1, 2, 7, 5]
i = 1
while i < len(seq):
print '子数组 长度 : ',i
low = 0
while low < len(seq):
mid = low + i
height = low + 2*i
print 'low ',low,'mid:',mid,'height:',height
low += 2*i
i *= 2
运行结果如下：
image.png
我们此时的猜想，以及抽象出来的通用公式 在len(seq) == 2的N次方的时候是对的。
我们在换一组不同的数试试 非len(seq) == 2的N的数试试
seq = [5, 4, 3, 0, 1, 2, 7, 5, 11,9]
i = 1
while i < len(seq):
print '子数组 长度 : ',i
low = 0
while low < len(seq):
mid = low + i
height = low + 2*i
print 'low ',low,'mid:',mid,'height:',height
low += 2*i
i *= 2
运行结果如下：
image.png
这时候就出错了。我们数组seq 一共才10个元素，height 已经达到了 12，16.mid 达到了 12.很明显数组下标越界了。
我们需要做一些调整。
首先解决height 越界的问题。
当数组终结时候 height 最大达到了16，而我们的数组最大才10个元素。
所以我们 从 height 与 len（seq）中选择一个最小的元素，来作为数组的右边界。因为数组seq 长度是 10 ，height肯定不能超过 数组长度呀，不然就数组下标越界咯。
改版后的代码如下：
seq = [5, 4, 3, 0, 1, 2, 7, 5, 11,9]
i = 1
while i < len(seq):
print '子数组 长度 : ',i
low = 0
while low < len(seq):
mid = low + i
height = min(low + 2 * i, len(seq))
print 'low ',low,'mid:',mid,'height:',height
low += 2*i
i *= 2
运行结果如下：
image.png
现在height的问题已经解决了。
现在解决 mid 的问题。
mid是用来将一个数组拆分为两个部分的：[low,mid) [mid,height)
当mid>height的时候，很明显嘛 [mid,height)已经没有了，也就是说 数组已经不能再拆分了。不能拆分了我们就不拆分呗，直接pass，总有一天能轮到他，如下图：
image.png
原谅我画的丑·····
代码如下：
seq = [5, 4, 3, 0, 1, 2, 7, 5, 11,9]
i = 1
while i < len(seq):
print '子数组 长度 : ',i
low = 0
while low < len(seq):
mid = low + i
height = min(low + 2 * i, len(seq))
if mid < height:
print 'low ',low,'mid:',mid,'height:',height
low += 2*i
i *= 2
运行结果如下：
image.png
这不 mid越界的问题 已经没了。
len(seq) 为奇数的时候 同样适用这样的处理方式。
下面进行 合并排序。
合并与递归模式的合并是一样的。
代码如下：
def merge(seq,low,mid,height):
"""合并两个已排序好的列表，产生一个新的已排序好的列表"""
# 通过low,mid height 将[low:mid) [mid:height)提取出来
left = seq[low:mid]
right = seq[mid:height]
print 'left:', left, 'right:', right
k = 0 #left的下标
j = 0 #right的下标
result = [] #保存本次排序好的内容
#将最小的元素依次添加到result数组中
while k < len(left) and j < len(right):
if left[k] <= right[j]:
result.append(left[k])
k += 1
else:
result.append(right[j])
j += 1
#将对比完后剩余的数组内容 添加到已排序好数组中
result += left[k:]
result += right[j:]
#将原始数组中[low:height)区间 替换为已经排序好的数组
seq[low:height] = result
print "seq:", seq
完整代码如下：
seq = [5, 4, 3, 0, 1, 2, 7, 5, 11,9]
i = 1
while i < len(seq):
print '子数组 长度 : ',i
low = 0
while low < len(seq):
mid = low + i
height = min(low + 2 * i, len(seq))
if mid < height:
print 'low ',low,'mid:',mid,'height:',height
merge(seq,low,mid,height)
low += 2*i
i *= 2
运行结果如下：
image.png
image.png
网友评论