新增归并排序算法演示

zhanghe06 · zhanghe06 · commit 68b6fa813f5e · 2017-03-29T21:53:55.000+08:00
diff --git a/test/algorithm/merge_sort.py b/test/algorithm/merge_sort.py
@@ -0,0 +1,114 @@
+#!/usr/bin/env python
+# encoding: utf-8
+
+"""
+@author: zhanghe
+@software: PyCharm
+@file: merge_sort.py
+@time: 2017/3/27 下午11:40
+"""
+
+from collections import deque
+from copy import copy
+
+
+def merge_sort(lst):
+    if len(lst) <= 1:
+        return lst
+
+    def merge(left, right):
+        merged, left, right = deque(), deque(left), deque(right)
+        while left and right:
+            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  # deque popleft is also O(1)
+        merged.extend(right if right else left)
+        return list(merged)
+
+    middle = int(len(lst) // 2)
+    left_lst = merge_sort(lst[:middle])
+    right_lst = merge_sort(lst[middle:])
+    return merge(left_lst, right_lst)
+
+
+def test_merge_simple():
+    """
+    测试简单归并
+    :return:
+    """
+    test_list_a = [1, 3, 4, 5, 9]
+    test_list_b = [1, 2, 3, 6, 8, 10, 11]
+    test_list = copy(test_list_a)
+    test_list.extend(test_list_b)
+
+    print test_list_a
+    print test_list_b
+    print test_list
+    print merge_sort(test_list)
+
+
+def g_next(g_l):
+    """
+    获取生成器元素
+    :param g_l:
+    :return:
+    """
+    try:
+        r = int(g_l.next())
+    except StopIteration:
+        r = None
+    return r
+
+
+def merge_sort_t(m, n):
+    """
+    归并排序两个迭代器
+    :param m:
+    :param n:
+    :return:
+    """
+    # 去除换行并转生成器
+    g_a = (a.strip() for a in m)
+    g_b = (b.strip() for b in n)
+
+    n_a = g_next(g_a)
+    n_b = g_next(g_b)
+    while 1:
+        print n_a, n_b
+        if not (n_a or n_b):
+            return
+        elif n_a is None and n_b is not None:
+            yield '+', n_b
+            n_b = g_next(g_b)
+        elif n_b is None and n_a is not None:
+            yield '-', n_a
+            n_a = g_next(g_a)
+        elif n_a <= n_b:
+            print '-', n_a
+            yield n_a
+            n_a = g_next(g_a)
+        else:
+            print '+', n_b
+            yield n_b
+            n_b = g_next(g_b)
+
+
+def test_merge_big_file():
+    """
+    测试大文件归并
+    :return:
+    """
+
+    # 打开文件（文件本身就是迭代器）
+    f_a = open('a.log', 'r')
+    f_b = open('b.log', 'r')
+
+    for i in merge_sort_t(f_a, f_b):
+        print i
+
+    # 关闭文件
+    f_a.close()
+    f_b.close()
+
+
+if __name__ == '__main__':
+    # test_merge_simple()
+    test_merge_big_file()
diff --git a/test/algorithm/readme.md b/test/algorithm/readme.md
@@ -0,0 +1,26 @@
+## 归并排序
+
+归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
+归并排序算法依赖归并操作。
+
+
+参数对比 | 双端队列 | 列表
+| --- | --- | --- |
+数据操作 | 头部，尾部 | 任意部位
+时间复杂度 | O(1) | O(n)
+
+为了降低时间复杂度，这里采用双端队列作为存储结构
+
+递归拆分的时间复杂度是log n
+
+进行两个有序数组排序的方法复杂度是n
+
+整体复杂度为 O(n log n)
+
+
+## 对数符号
+对数无论什么时候都必须有底数，底数为10时log10()可写为lg()，底数为e时loge()可写为ln()
+但也有些时候会看见直接写成log（）的，
+这种情况下的底数：一般普通应用都是10，
+计算机学科是2，编程语言里面是e；
+当然log（）这样的写法并不准确，知道在什么情况下表示什么就可以了，写的时候最好加上底数。
diff --git a/test/algorithm/tools_data.py b/test/algorithm/tools_data.py
@@ -0,0 +1,40 @@
+#!/usr/bin/env python
+# encoding: utf-8
+
+"""
+@author: zhanghe
+@software: PyCharm
+@file: tools_data.py
+@time: 2017/3/28 上午12:41
+"""
+
+
+from random import randint
+
+
+data_type_list = ['odd', 'even']
+
+
+def write_file(file_name, data_type=None):
+    """
+    写文件
+    :param file_name:
+    :param data_type:
+    :return:
+    """
+    c = 0
+    num = 0
+    if data_type == 'odd':  # 奇数
+        num = 1
+    if data_type == 'even':  # 偶数
+        num = 2
+    while c < 100000:
+        c += 1
+        num += randint(0, 4)*2
+        with open(file_name, 'a') as f:
+            f.write('%s\n' % num)
+
+
+if __name__ == '__main__':
+    write_file('a.log', 'odd')
+    write_file('b.log', 'even')
