排序算法——插入，希尔和归并

如有错误，请指出，多谢。

动图来自菜鸟教程，多谢。

一：插入排序

插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止

import random
def InsertSort(arr):
    for i in range(1,len(arr)):
        #获取前一个下标和当前数字
        index = i - 1
        num = arr[i]
        #当满足条件时，执行此while语句
        while index >= 0 and arr[index] > num:
            #如果前一个数大于当前数，交换
            arr[index+1] = arr[index]
            #把下标减1，继续判断，如果满足，继续执行while循环
            index -= 1
        arr[index+1] = num
    print("排序后:",arr)

if __name__ == '__main__':
    arr = []
    x = random.randint(2,20)
    for i in range(0,x):
        arr.append(random.randint(1,1000))
    print("排序前:",arr)
    InsertSort(arr)

二：希尔排序 

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

它实际上是插入排序的进阶，分组插入排序

import math
import random
def ShellSort(arr):
    #立个flag
    flag = 1
    #用于获取flag数
    while(flag < len(arr)/3):
        #1*3+1,4*3+1,7*3+1
        flag = flag*3+1

    while flag > 0:
        #插入排序
        for i in range(flag,len(arr)):
            index = i - flag
            num = arr[i]
            while index >= 0 and arr[index] > num:
                arr[index+flag] = arr[index]
                index -= flag
            arr[index+flag] = num

        flag = math.floor(flag/3)

    print("排序后:",arr)

if __name__ == '__main__':
    arr = []
    x = random.randint(2,20)
    for i in range(0,x):
        arr.append(random.randint(1,1000))
    print("排序前:",arr)
    ShellSort(arr)

三：归并排序

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

import random
def MergeSort(arr):
    #递归出口
    if len(arr) < 2:
        return arr
    #将传入的数组分为两部分，放入新的数组
    middle = int(len(arr)/2)
    left_arr = arr[0:middle]
    right_arr = arr[middle:]
    #递归调用
    return Merge(MergeSort(left_arr),MergeSort(right_arr))

def Merge(left_arr,right_arr):
    # print(left_arr,right_arr)
    result = []
    #当两个数组均不空时，将小的放入新数组
    while left_arr and right_arr:
        if left_arr[0] < right_arr[0]:
            result.append(left_arr.pop(0))
        else:
            result.append(right_arr.pop(0))
    #当其中一个数组空时
    while right_arr:
        result.append(right_arr.pop(0))
    while left_arr:
        result.append(left_arr.pop(0))
    # print(result)
    return result

if __name__ == '__main__':
    arr = []
    x = random.randint(2,20)
    for i in range(0,x):
        arr.append(random.randint(1,1000))
    print("排序前:",arr)
    print("排序后:",MergeSort(arr))