问题

归并排序

思路说明

归并操作过程：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

上述说法是理论表述，下面用一个实际例子说明： 例如一个无序数组[6,2,3,1,7] 首先将这个数组通过递归方式进行分解，直到：[6],[2],[3],[1],[7] 然后开始合并排序，也是用递归的方式进行：

  1. 两个两个合并排序，得到：[2,6],[1,3],[7]
  2. 上一步中，其实也是按照本步骤的方式合并的，只不过由于每个list中一个数，不能完全显示过程。下面则可以完全显示过程。 初始：
    a = [2,6]
    b = [1,3]
    c = []
    第1步，顺序从a,b中取出一个数字：2,1
    比较大小后放入c中，并将该数字从原list中删除，结果是：
    a = [2,6]
    b = [3]
    c = [1]
    第2步，继续从a,b中按照顺序取出数字，也就是重复上面步骤，这次是：2,3
    比较大小后放入c中，并将该数字从原list中删除，结果是：
    a = [6]
    b = [3]
    c = [1,2]
    第3步,再重复前边的步骤,结果是：
    a = [6]
    b = []
    c = [1,2,3]
    最后一步，将6追加到c中，结果形成了：
    a = []
    b = []
    c = [1,2,3,6]
  3. 通过反复应用上面的流程，实现[1,2,3,6]与[7]的合并
  4. 最终得到排序结果[1,2,3,6,7]

本文列举了三种python的实现方法。

解决(Python)

  1.   1. #! /usr/bin/env python
  2.     2. #coding:utf-8
  3.     3.   4. #方法1：将前面讲述的过程翻译过来了，略先拙笨
  4.     5.   6. def merge_sort(seq):
  5.     7.     if len(seq) ==1:
  6.     8.         return seq
  7.     9.     else:
  8.     10.         middle = len(seq)/2
  9.     11.         left = merge_sort(seq[:middle])
  10.     12.         right = merge_sort(seq[middle:])
  11.     13.   14.         i = 0   #left 计数
  12.     15.         j = 0   #right 计数
  13.     16.         k = 0   #总计数
  14.     17.   18.         while i < len(left) and j < len(right):
  15.     19.             if left[i] < right [j]:
  16.     20.                 seq[k] = left[i]
  17.     21.                 i +=1
  18.     22.                 k +=1
  19.     23.             else:
  20.     24.                 seq[k] = right[j]
  21.     25.                 j +=1
  22.     26.                 k +=1
  23.     27.   28.         remain = left if i<j else right
  24.     29.         r = i if remain ==left else j
  25.     30.   31.         while r<len(remain):
  26.     32.             seq[k] = remain[r]
  27.     33.             r +=1
  28.     34.             k +=1
  29.     35.   36.         return seq
  30.     37.   38. #方法2：在按照顺序取数值方面，应用了list.pop()方法，代码更紧凑简洁
  31.     39. #此方法来[自维基百科：归并操作](http://zh.wikipedia.org/zh/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F)
  32.     40.   41. def merge_sort(lst):   #此方法来自维基百科：http://zh.wikipedia.org/zh/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F
  33.     42.     if len(lst) <= 1:
  34.     43.         return lst
  35.     44.   45.     def merge(left, right):
  36.     46.         merged = []
  37.     47.   48.         while left and right:
  38.     49.             merged.append(left.pop(0) if left[0] <= right[0] else right.pop(0))
  39.     50.   51.         while left:
  40.     52.             merged.append(left.pop(0))
  41.     53.   54.         while right:
  42.     55.             merged.append(right.pop(0))
  43.     56.   57.         return merged
  44.     58.   59.     middle = int(len(lst) / 2) 
  45.     60.     left = merge_sort(lst[:middle])
  46.     61.     right = merge_sort(lst[middle:])
  47.     62.     return merge(left, right)
  48.     63.   64. #方法3：原来在python的模块heapq中就提供了归并排序的方法，只要将分解后的结果导入该方法即可
  49.     65. #强大。
  50.     66. #以下方法来自[resettacode](http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Python),并稍作修改
  51.     67.   68. from heapq import merge
  52.     69.   70. def merge_sort(seq):
  53.     71.     if len(seq) <= 1:
  54.     72.         return m
  55.     73.     else:              
  56.     74.         middle = len(seq)/2
  57.     75.         left = merge_sort(seq[:middle])
  58.     76.         right = merge_sort(seq[middle:])
  59.     77.         return list(merge(left, right))         #heapq.merge()
  60.     78.   79. if __name__=="__main__":
  61.     80.     seq = [1,3,6,2,4]
  62.     81.     print merge_sort(seq)

整理人：豆包AI助手