归并排序

python3
算法

数据结构和算法动态可视化工具:VisuAlgo

递归:
函数的自我调用(重复做同一件事,也可以用迭代语句),适用于如果你可以写一个函数,并让它调用自己,只是每次减少参数值,这时就可以用递归思想
但不断的递归可能会造成内存耗尽,所以合法的检查(基本条件)是正确解决整个问题的关键所在.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sigma(int):
    if int <= 0:return 0
    sum = 0
    for i in range(int+1):
        sum+=i
    print(sum)
sigma(100)
# 递归
def sigma1(int):
    if int <=0:return 0 # 终止条件
    else:
        return int+sigma1(int-1)
print(sigma1(100))

归并排序:
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并

归并排序的算法我们通常用递归实现,先把待排序区间[s,t]以中点二分,接着把左边子区间排序,再把右边子区间排序,最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]

归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def merge(left, right):
    i, j = 0, 0
    result = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    print(result)
    return result
def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    num = int((len(lists) / 2)+0.5)
    # 二分查找 logN 拆分成单个元素
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    print(left,right,sep='下面')
    return merge(left, right) # 合并之后就是有序的了
print(merge_sort([1,6,4,2,9,7,5,8,3]))
    # 归并排序 (合并过程的次数也是N)N*logN
    # T(n) = 0,if n < 2  #合法的检查 基本条件
    # T(n) = T(n/2) +T(n/2)+n ,if n >1
    # 算法的核心:拆分        合并
    # T(4) = 2 * T(2) + 4
    # T(2) = 2 * T(1) + 2
    # T(1) = 0
    # 8个元素排序需要8×log8 = 24

递归和合并过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 1
merge( merge_sort([1,6,4,2,7]),merge_sort([7,5,8,3])
     )
# 2
merge( merge( merge_sort([1,6,4]),merge_sort([2,7])),
       merge( merge_sort([7,5]),merge_sort([8,3]))
     )
# 3
merge( merge(
           merge( merge_sort([1,6]),merge_sort(4)),
           merge( merge_sort([2]),merge_sort([7]))
           ),
       merge(
           merge( merge_sort([7]),merge_sort([5])),
           merge( merge_sort(8),merge_sort(3))
           )
     )
# 4
merge( merge(
            merge(
                merge( merge_sort([1]),merge_sort([6])),
                merge_sort(4)
                ), 
            merge( merge_sort([2]), merge_sort([7]))
            ),
      merge(
            merge( merge_sort([7]), merge_sort([5])),
            merge( merge_sort(8), merge_sort(3))
            )
      )

如图:
归并排序

Share Comments