算法学习：归并排序

1、概念

归并排序使用了二分法，归根到底的思想还是分而治之。

拿到一个长数组，将其不停的分为左边和右边两份，然后以此递归分下去。

将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

归并排序是一种稳定的排序方法。

2、举例

1）合并两个有序数组，伪代码

    arr_a = [1,4,5,6]
    arr_b = [4,4,8,10]
伪代码如下：
    result = []
    idx_a,idx_b
    while idx_a<len(arr_a) and idx_b<len(arr_b):
        if arr_a[idx_a]<=arr_b[idx_b]:
            result[arr_a[idx_a]]
            idx_a+=1
        elif arr_a[idx_a]>arr_b[idx_b]
            result[arr_b[idx_b]]
            idx_b+=1
    if idx_a==len(arr_a):
        result.extend(arr_b[idx_b:])

2）对于没有顺序的数组排序

思想：拆拆拆，合合合

将一个无序的数组从数组的中间部分无限的拆分，形成前后两部分（循环拆分）当我们拆分到数组只有一个元素的时候，这个数组就可以看作是一个有序数组，然后再将前后2个部分合并起来，这样整个数组就有序了。

[11,2,3,43,23,5,6,9,10] len==9 mid =4
拆：拆分到最有只有一个元素
[11,2,3,43] [23,5,6,9,10]
[11,2] [3,43] [23,5] [6,9,10]
[11] [2] [3] [43] [23] [5] [6] [9,10]
[11] [2] [3] [43] [23] [5] [6] [9] [10]
------------------------------------------------
合并
[2,11] [3,43] [5,23] [6,9]
[2,3,11,43] [5,6,9,23]
[2,3,5,6,9,11,23,43]

3、代码1：合并两个有序数组

def mergerArr(arr_a,arr_b):
    """这个是合并2个有序数组的合并算法"""
    result = []
    idx_a =0
    idx_b =0
    #idx_a和idx_b分别执行数组a和数组b的第一个元素，一次比较两个指针指向的元素值，取较小元素放入result,然后挪动指针进行比较
    while idx_a<len(arr_a) and idx_b<len(arr_b):
        if arr_a[idx_a]<=arr_b[idx_b]:
            result.append(arr_a[idx_a])
            idx_a+=1
        elif arr_a[idx_a]>arr_b[idx_b]:
            result.append(arr_b[idx_b])
            idx_b+=1
    #比较结束完了以后，其中一个数组已经取完值了，另外一个数组还没有
    print("idx_a = %s idx_b = %s"%(idx_a,idx_b))
    if idx_a==len(arr_a):
        result.extend(arr_b[idx_b:])
    else:
        result.extend(arr_a[idx_a:])
    return result
arr_b = [1,4,5,6]
arr_a = [4,4,8,10]
print(mergerArr(arr_a,arr_b))
#结果
idx_a = 2 idx_b = 4
[1, 4, 4, 4, 5, 6, 8, 10]

4、代码2：无序数组拆分过程

def mergeSort(arr):
    if len(arr)<=1:
        return arr
    mid = len(arr)//2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    print("left=%s
right=%s"%(left,right))
        #拆分后，到只剩下一个元素了mid和left才返回值了，才能做合并的过程
    return mergerArr(left,right)
    
arr = [11,2,3,43,23,5,6,9]
print(mergeSort(arr))

5、最终代码

def mergerArr(arr_a,arr_b):
    """这个是合并2个有序数组的合并算法"""
    result = []
    idx_a =0
    idx_b =0
    #idx_a和idx_b分别执行数组a和数组b的第一个元素，一次比较两个指针指向的元素值，取较小元素放入result,然后挪动指针进行比较
    while idx_a<len(arr_a) and idx_b<len(arr_b):
        if arr_a[idx_a]<=arr_b[idx_b]:
            result.append(arr_a[idx_a])
            idx_a+=1
        elif arr_a[idx_a]>arr_b[idx_b]:
            result.append(arr_b[idx_b])
            idx_b+=1
    #比较结束完了以后，其中一个数组已经取完值了，另外一个数组还没有
    print("idx_a = %s idx_b = %s"%(idx_a,idx_b))
    if idx_a==len(arr_a):
        result.extend(arr_b[idx_b:])
    else:
        result.extend(arr_a[idx_a:])
    return result

def mergeSort(arr):
    if len(arr)<=1:
        return arr
    mid = len(arr)//2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    print("left=%s
right=%s"%(left,right))
    #拆分后，到只剩下一个元素了mid和left才返回值了，才能做合并的过程
    return mergerArr(left,right)
    
arr = [11,2,3,43,23,5,6,9]
print(mergeSort(arr))

结果：

6、时间复杂度

由于递归拆分的时间复杂度是logN

然而，进行两个有序数组排序的方法复杂度是N

该算法的时间复杂度是N*logN

所以是O(NlogN)

7、快速排序和归并排序

归并和快排都是用到递归的处理方式。

归并排序的处理过程是由下到上的，先解决子问题然后再合并的；

快排和归并正好相反，快排的处理是由上到下的,是先分区然后再去处理子问题。

归并是稳定排序，快排不是稳定排序；

特殊情况归并的性能比快排稍微好一点。