算法-插入排序

插入排序是一种稳定性排序！

什么叫稳定性：相同的元素在排序后没有发生位置的变化我们称这种算法为稳定排序（这个性质针对多属性排序是由意义的）

插入排序算法有两种方式

# 方法1 
# 思路：分为两个序列，有序序列[arr0],无序序列arr[1:]
# 然后不断的和有序对比，当小于有序序列的最后个数时，就交换位置，以此类推完成排序

def insert_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
            else:
                break
    return arr

# 方法2
# 思路：分为两个序列，有序序列[arr0],无序序列arr[1:]
# 然后不断的和有序对比，当小于有序的最后一个时，这里就把最后个数的坑空出来，把最后个数放在对比这个数的位置上，这样以此类推，最后把比较的这个数来把坑填上就完成了排序


def insert_sort_two(arr):
    for i in range(1, len(arr)):
        temp =  arr[i]
        j = i-1
        while j >=0:
            if temp < arr[j]:
                arr[j+1] = arr[j]
                j -= 1
            else:
                break
        arr[j+1] = temp
    return arr