归并排序可以是一种外排序， 外排序是指利用外存也就是磁盘进行排序的一种简称。
典型的应用是hadoop 的 mapreduce 的merge 阶段
归并排序的： 假设有n 个元素， 将n 个元素分程x 组, 然后对每一组的元素进行排序， 然后将这 x 组已经排好序的序列合并起来。
说一下分成x 组的方式， 大概有两种：
第一种： 递归的方式, 这种情况你可能都不会去关心 x 大小。
第二种： 每组 m 个元素， x = n/m。这种方法常用在内存不够的情况下。
所以归并排序的步骤分两步：
第一步： 分x 组， 对每组的元素进行排序
第二部： 合并， 将已经排序好的 x 组元素合并起来。
先说第一种递归的方式吧， 就是你可能会做到的归并排序的题目：
我们先写第二步的代码：合并已经排序好的数组
def merge_sorted_list(l1, l2): i, j = 0, 0 result = [] while i < len(l1) and j < len(l2): if l1[i] <= l2[j]: result.append(l1[i]) i += 1 else: result.append(l2[j]) j += 1 result += l1[i:] result += l2[j:] return result
再说第一步：
def merge_sort(l): if len(l) <= 1: return l num = len(l) / 2 l1 = merge_sort(l[:num]) l2 = merge_sort(l[num:]) return merge_sorted_list(l1, l2)
全部代码：
def merge_sort(l): if len(l) <= 1: return l num = len(l) / 2 l1 = merge_sort(l[:num]) l2 = merge_sort(l[num:]) return merge_sorted_list(l1, l2) def merge_sorted_list(l1, l2): i, j = 0, 0 result = [] while i < len(l1) and j < len(l2): if l1[i] <= l2[j]: result.append(l1[i]) i += 1 else: result.append(l2[j]) j += 1 result += l1[i:] result += l2[j:] return result a = [219, 9527, 211, 9218]print a b = merge_sort(a)print b
总的来说这种归并排序理解起来以及代码写起来都是很简单的。
接下来说一下第二种吧，纯粹的外排序。用栗子的方式理解起来比较简单。
问题： 假设有２G的文件，里面是数字，一行一个数字，内存只有500Ｍ。让你排序，咋整？
其实思路很简单，一次只读一点点，排序好，然后再将将文件合并起来。然后最终保存为一个大文件。
先说下python open(filepath).readline()，一次只会返回一行，不必担心大文件，相信各个语言都有对应的方式。
首先第一步，大文件拆分成 x 个 block_size 大的小文件，每个小文件排好序
def split_file(file_path, block_size): f = open(file_path, 'r') fileno = 1 files = [] while True: lines = f.readlines(block_size) if not lines: break lines = [int(i.strip()) for i in lines] lines.sort() files.append(save_file(lines, fileno)) fileno += 1 return files
第二部：将拆分成的小文件合并起来，然后将归并的东西写到大文件里面去， 这里用到的是多路归并的方法。多路归并在我的这篇文章里面有写到：http://www.cnblogs.com/dream-of-cambridge/articles/8046031.html
def nw_merge(files):
fs = [open(file_) for file_ in files]
min_map = {}
out = open("/home/hrs/demo/files/out", "a") for f in fs:
read = f.readline() if read:
min_map[f] = int(read.strip())
while min_map:
min_ = min(min_map.items(), key = lambda x: x[1])
min_f, min_v = min_
out.write("{}".format(min_v))
out.write("\n")
nextline = min_f.readline() if nextline:
min_map[min_f] = int(nextline.strip()) else: del min_map[min_f]全部代码：
= = open(filepath, i = [open(file_) file_ == open(, f === min(min_map.items(), key = x: x[1==== open(file_path, = 1== = [int(i.strip()) i += 1 == = = 500*1024*1024 num_blocks = os.stat(file_path).st_size/=
《本文》有 0 条评论