add algorithm

rieuse · rieuse · commit c1cc3b26ea8c · 2018-04-16T20:43:09.000+08:00
diff --git a/Python算法学习/归并排序.py b/Python算法学习/归并排序.py
@@ -0,0 +1,32 @@
+"""
+平均,最好,最坏 都是 O(nlogn)
+"""
+
+
+def merge_sort(ls):
+    mid = len(ls) // 2
+    if len(ls) <= 1:
+        return ls
+    left = merge_sort(ls[:mid])
+    right = merge_sort(ls[mid:])
+    return merge(left, right)
+
+
+def merge(left, right):
+    l, r = 0, 0
+    result = []
+    while l < len(left) and r < len(right):
+        if ls[l] < ls[r]:
+            result.append(ls[l])
+            l += 1
+        else:
+            result.append(ls[r])
+            r += 1
+    result += left[l:]
+    result += right[r:]
+    return result
+
+
+ls = [1, 4, 68, 34, 66, 99, 312]
+merge_sort(ls)
+print(ls)
diff --git a/Python算法学习/快速排序.py b/Python算法学习/快速排序.py
@@ -0,0 +1,29 @@
+'''
+通过一趟排序将要排序的数据分割成独立的两部分，
+其中一部分的所有数据都比另外一部分的所有数据都要小，
+然后再按此方法对这两部分数据分别进行快速排序，
+整个排序过程可以递归进行，以此达到整个数据变成有序序列。
+'''
+
+
+def quick_sort(lists, left, right):
+    if left >= right:
+        return lists
+    key = lists[left]
+    low = left
+    high = right
+    while left < right:
+        while left < right and lists[right] >= key:
+            right -= 1
+        lists[left] = lists[right]
+        while left < right and lists[left] <= key:
+            left += 1
+        lists[right] = lists[left]
+    lists[right] = key
+    quick_sort(lists, low, left - 1)
+    quick_sort(lists, left + 1, high)
+    return lists
+
+
+arr = [2, 645, 1, 344, 546, 442, 89, 99, 76, 90]
+print(quick_sort(arr, 0, len(arr) - 1))
diff --git a/Python算法学习/快速排序二.py b/Python算法学习/快速排序二.py
@@ -0,0 +1,19 @@
+def quick_sort(ls, left, right):
+    if left < right:
+        mid = (left + right) // 2
+        pivot = ls[mid]
+        ls[mid], ls[right] = ls[right], ls[mid]
+        boundary = left
+        for index in range(left, right):
+            if ls[index] < pivot:
+                ls[index], ls[boundary] = ls[boundary], ls[index]
+                boundary += 1
+        ls[right], ls[boundary] = ls[boundary], ls[right]
+        quick_sort(ls, left, boundary - 1)
+        quick_sort(ls, boundary + 1, right)
+
+
+ls = [1, 3, 56, 23, 34, 99, 532, 4, 59]
+print('before:', ls)
+quick_sort(ls, 0, len(ls) - 1)
+print('after :', ls)
