排序算法：
python实现基数排序
python实现归并排序
python实现交换排序
python实现选择排序
python实现插入排序

归并排序
“归并”是将两个或者两个以上的有序表组成一个新的有序表。假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为一，然后两两归并，得到n//2个长度为2或1的有序表；再两两归并，…直到合并成一个长度为n的有序表为止，这种方法称为2-路归并排序。

归并算法动态实现：

实现代码如下：

#merge的功能是将前后相邻的两个有序表归并为一个有序表的算法。
def merge(left, right):
    ll, rr = 0, 0
    result = []
    while ll < len(left) and rr < len(right):
        if left[ll] < right[rr]:
            result.append(left[ll])
            ll += 1
        else:
            result.append(right[rr])
            rr += 1
    result+=left[ll:]
    result+=right[rr:]
    return result

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
    num = len(alist) // 2   # 从中间划分两个子序列
    left = merge_sort(alist[:num]) # 对左侧子序列进行递归排序
    right = merge_sort(alist[num:]) # 对右侧子序列进行递归排序
    return merge(left, right) #归并

tesl=[1,3,45,23,23,12,43,45,33,21]
print(merge_sort(tesl))
#[1, 3, 12, 21, 23, 23, 33, 43, 45, 45]

• 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

空间效率：需要n个辅助空间,因此空间复杂度为O(n)
时间效率：归并时间复杂度为O(n),一共进行log2 N趟，因此时间复杂度为O(nlog2 N)
它是一种稳定的排序算法。