ZMonster's Blog 巧者劳而智者忧，无能者无所求，饱食而遨游，泛若不系之舟

排序算法——归并排序

2014-01-11

归并排序

归并排序也是一种使用分治法来实现的有效排序算法，它是现代计算机创始人John von Neumann于1945年发明的。

归并排序在众多排序算法中既是稳定排序，又有不错的效率，同时，归并排序不仅可以用于内排序，还可以用于外排序。所以说归并排序是非常值得学习的。

本文将对归并排序的思想进行阐释，并给出完整的实现，然后对外排序进行探讨。

算法思想

归并排序的思路如下(以二路归并为例)：

  1. 将数组划均分为两个子数组；
  2. 对两个字数组进行排序；
  3. 将排序好的两个字数组归并。

所谓 N路归并 是指将数组均分为N个子数组，将字数组排序后再归并。因此二路归并是归并排序的最一般的情况。

这里是二路归并排序的一个图示： merge-sort.png

二路归并排序用python描述如下： 

1: def msort(array):
2:     length = len(array)
3:     if length == 1:
4:         return array
5:     else:
6:         mid = length / 2
7:         left = msort(array[0: mid])
8:         right = msort(array[mid: length])
9:         return merge(left, right)

当然，这里描述的是递归版本的算法，实际情况中有时候也会为了效率而使用循环而不是递归来实现归并排序。下面是使用循环的算法描述： 

 1: def msort(array):
 2:     length = len(array)
 3:     step = 1
 4:     while step < length:
 5:         for left in range(0, length - step, 2 * step):
 6:             result = merge(array[left:left + step],
 7:                            array[left + step: min(left + 2 * step,
 8:                                                   length)])
 9:             array = array[0:left] + result + array[min(left + 2 *
10:                                                        step, length)]
11:         step = step * 2
12:     return array

msort中的归并部分(merge)的思想是：分别取出字数组中最小的元素，取它们中较小的放入原数组中，然后重复这个过程。《算法导论》中将这个过程类比为整理扑克牌的过程，非常形象。想象一下，桌面上有两堆扑克，它们都朝下扣着，并且按照牌面点数从小到大放置，我们要的是把这两堆扑克都拿到手里，并且按照从小到大的顺序排好序，这个时候要怎么做？

归并的思想可以用python描述如下： 

 1: def merge(left, right):
 2:     llen = len(left)
 3:     lcur = 0
 4:     rlen = len(right)
 5:     rcur = 0
 6:     result = []
 7:     while lcur < llen and rcur < rlen:
 8:         lone = left[lcur]
 9:         rone = right[rcur]
10:         result.append(min(lone, rone))
11:         if lone < rone:
12:             lcur += 1
13:         else:
14:             rcur += 1
15:     result += left[lcur:]
16:     result += right[rcur:]
17:     return result

完整实现

下面是综合了非递归与递归版本的二路归并排序的完整实现，结果由org-babel对代码块求值得到。 

 1: # -*- coding: utf-8 -*-
 2: def merge(left, right):
 3:     llen = len(left)
 4:     lcur = 0
 5:     rlen = len(right)
 6:     rcur = 0
 7:     result = []
 8:     while lcur < llen and rcur < rlen:
 9:         lone = left[lcur]
10:         rone = right[rcur]
11:         result.append(min(lone, rone))
12:         if lone < rone:
13:             lcur += 1
14:         else:
15:             rcur += 1
16:     result += left[lcur:]
17:     result += right[rcur:]
18:     return result
19: 
20: def msort_rec(array):
21:     length = len(array)
22:     if length == 1:
23:         return array
24:     else:
25:         mid = length / 2
26:         left = msort_rec(array[0: mid])
27:         right = msort_rec(array[mid: length])
28:         return merge(left, right)
29: 
30: def msort_iter(array):
31:     length = len(array)
32:     step = 1
33:     while step < length:
34:         for left in range(0, length - step, 2 * step):
35:             result = merge(array[left:left + step],
36:                            array[left + step: min(left + 2 * step,
37:                                                   length)])
38:             array = array[0:left] + result + array[min(left + 2 *
39:                                                        step, length):]
40:         step = step * 2
41:     return array
42: 
43: if __name__ == '__main__':
44:     L = [1, 4, 2, 6, 3, 5, 8, 7]
45:     print "排序前: %r" %(L)
46:     R = msort_rec(L)
47:     print "排序后(递归): %r" %(R)
48:     I = msort_iter(L)
49:     print "排序后(非递归): %r" %(I)

结果 

排序前: [1, 4, 2, 6, 3, 5, 8, 7]
排序后(递归): [1, 2, 3, 4, 5, 6, 7, 8]
排序后(非递归): [1, 2, 3, 4, 5, 6, 7, 8]

发散：外排序应用

归并排序的思想可以用于外排序。外排序是相对内排序而言的。在常规的小规模排序过程中，都是直接在内存中对数据进行排序处理的，而对于数据量极大的排序问题，这种方式是不现实的。这个时候就要通过外排序来进行，先将数据划分成多个规模能在内存中处理的子集，对各个子集排序后存放在临时的磁盘文件上，然后再将这些子集归并到输出文件中。这个过程要使用到多路归并，如下图所示：

external-sort.png

注：该图来自 References 中第一篇文章。

那么来实现一下吧。

首先要创建一个大文件，往里面写入大量的数据，该函数实现如下(因为python不方便读取单个数字，下面的东西都是用C写的): 

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: #include <time.h>
 4: 
 5: int rand_file(char *file, int num)
 6: {
 7:     int i = 0;
 8:     int now;
 9:     FILE *f = fopen(file, "w");
10: 
11:     if (f == NULL) {
12:         perror("fopen");
13:         return 0;
14:     }
15: 
16:     for (; i < num; ++i) {
17:         srand((int)time(0));
18:         now = rand();
19:         fprintf(f, "%d ", now);
20:     }
21: 
22:     fclose(f);
23:     return num;
24: }

然后，我们需要一个将文件读入数组的函数和一个将数组内容写入文件的函数，实现如下： 

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: 
 4: int read_to_mem(FILE *file, int *arr, int len)
 5: {
 6:     int i = 0;
 7:     if (file != NULL) {
 8:         for (; !feof(file) && i < len; ++i) {
 9:             fscanf(file, "%d", arr + i);
10:         }
11:         return i;
12:     }
13:     else
14:         return 0;
15: }
16: 
17: int write_from_mem(FILE *file, int *arr, int len)
18: {
19:     int i = 0;
20:     if (file != NULL) {
21:         for ( ; i < len; ++i) {
22:             fprintf(file, "%d ", arr[i]);
23:         }
24: 
25:         return i;
26:     }
27: 
28:     else
29:         return 0;
30: }

完成这些准备工作后，就可以开始实现外排序了。循环将大文件读入一部分到内存，然后对这一部分进行排序——此时的排序可以使用快速排序、归并排序等各种排序算法，并无限制。

将各部分都排好序并保存为临时文件后的归并步骤是外排序的核心所在。多路归并的思路和二路归并是类似的。可以将归并模块实现为： 

 1: #include <stdlib.h>
 2: 
 3: void merge(File *out, File **flist, int fnum)
 4: {
 5:     int i = 0;
 6:     int now = 0;                /* 用于保存当前最小的值 */
 7:     int *fstaus = (int *)calloc(fnum, sizeof(int)); /* 记录文件状态 */
 8:     int *farr =(int *)calloc(fnum, sizeof(int));    /* 记录从各个文件中取出的数 */
 9:     int min = 0;                /* 记录当前值最小的文件索引 */
10: 
11:     for (; i < fnum; ++i) {     /* 检查各个文件指针的状态 */
12:         if (feof(fscanf(flist[i], "%d", farr + i))) {
13:             fstatus[i] = 0;
14:         }
15:         else {
16:             fstatus[i] = 1;
17:         }
18:     }
19: 
20:     while (1) {
21:         now = 0;
22:         for (i = 0; i < fnum && !fstatus[i]; ++i) {}
23:         if (i >= fnum) {     /* 如无可用文件，则退出 */
24:             break;
25:         }
26: 
27:         for (; i < fnum; ++i) { /* 从第一个可用的文件开始读 */
28:             if (fstatus[i] && farr[i] < now) {
29:                 now = farr[i];
30:                 min = i;
31:             }
32:         }
33: 
34:         fprintf(out, "%d ", now); /* 将最小值写入输出文件 */
35: 
36:         /* 读取该文件下一个数，并检查是否读完 */
37:         if (feof(fscanf(flist[min], "%d", farr + min))) {
38:             fstatus[min] = 0;
39:         }
40:     }
41: 
42:     free(farr);                 /* 释放内存 */
43:     free(fstatus);
44: }

完整的实现我就不写了，太累……写这篇文章就用了一整天。

嗯，大概就是这个样子。

Naringu is designed by Rizky Ariestiyansyah
Copyright © 2024