算法学习笔记--5.merge sort & divide-and-conquer

上回用到了一个选择排序：
用上昨天的算法复杂度，可以看出，选择排序的算法复杂度为 O(n2) ,n=len(lists).
即最坏情况下，算法运行 (len(lists))2 步可以得到结果。

>>> def sel_sort(lists):
for i in range(len(lists)):
for j in range(i + 1, len(lists)):
if lists[i] > lists[j]:
                lists[i], lists[j] = lists[j], lists[i]
return lists

改进一下，用归并排序(分而治之的思想)。

Fortunately, we can do a lot better than quadratic time using a technique similar to that for binary search. As we have said, binary search is an example of a divide-and-conquer algorithm.

In general, a divide and conquer algorithm is characterized by:

1. A threshold input size, below which the problem size is not subdivided.
   
2. The size and number of sub-instances into which an instance is split.
   
3. The algorithm used to combine sub-solutions.

Like many divide-and-conquer algorithms, merge sort is most easily deacribed recursively:

1. If the list is length 0 or 1, it is already sorted.
   
2. If the list has more than one element, split the list into two lists, and use merge sort to sort each of them.
   
3. Merge the results.

def merge_sort(L):
if len(L) < 2:
return L
else:
        mid = int(len(L)/2)
        left = merge_sort(L[:mid])
        right = merge_sort(L[mid:])
return merge(left, right)

def merge(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

在看这个归并排序排序的算法复杂度。
merge_sort(L)部分算法复杂度为O(log(n))，或者说 log2(n) ，只用乘一个常数 log2(10) 。
merge 部分算法复杂度为O(len(L))。
整个归并排序算法复杂度为O(nlog(n))，n=len(L)

n = 5， 即要排序的列表长度为5。
选择排序最多需要运行25步。
归并排序最多需要运行十几步。

n = 1000，选择排序最多需要运行1000000步，而归并排序最多需要运行不到10000步。