稳定排序方法

1.插入排序
思想：将一个数字序列引申为两部分，第一部分为原始序列除去首数字，第二部分为变长序列，初始值为原始序列的首数字，并不断将原始序列的值逐一添入。将第一部分的每一个数字分别与第二部分比较，若结果偏小，则交换数字位置。

import random
random.seed(12)
num = []
for i in range(10):
    num.append(random.randint(1, 100))
print('原始序列：', num)

for j in range(1, len(num)):
    key = num[j]
    n = j - 1
    print('第一部分：', key, ' 第二部分：', num[:n+1])
    while n >= 0:
        if key < num[n]:
            num[n+1], num[n] = num[n], key
        n -= 1
print('最终序列：', num)

结果：
原始序列： [61, 35, 85, 68, 86, 45, 19, 49, 2, 48]
第一部分： 35 第二部分： [61]
第一部分： 85 第二部分： [35, 61]
第一部分： 68 第二部分： [35, 61, 85]
第一部分： 86 第二部分： [35, 61, 68, 85]
第一部分： 45 第二部分： [35, 61, 68, 85, 86]
第一部分： 19 第二部分： [35, 45, 61, 68, 85, 86]
第一部分： 49 第二部分： [19, 35, 45, 61, 68, 85, 86]
第一部分： 2 第二部分： [19, 35, 45, 49, 61, 68, 85, 86]
第一部分： 48 第二部分： [2, 19, 35, 45, 49, 61, 68, 85, 86]
最终序列： [2, 19, 35, 45, 48, 49, 61, 68, 85, 86]

2.冒泡排序
思想：比较相邻元素，如果顺序错误则交换元素位置。

def bubble_sort(num):
    for m in range(len(num)):
        for n in range(m+1, len(num)):
            if num[n] < num[m]:
                num[m], num[n] = num[n], num[m]
    return num

3.归并排序
思想：