排序算法之 '插入排序'

插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序

算法稳定性

插入排序中相同元素的前后顺序不会发生改变，所以插入排序是一种稳定的排序算法。

Python实现

def inset_sort(lst):
    length = len(lst)
    for i in range(1, length):
        while i > 0:
            if lst[i] < lst[i - 1]:
                lst[i], lst[i - 1] = lst[i - 1], lst[i]
                i -= 1
            else:
                break
    return lst

if __name__ == '__main__':
    lst = [3, 4, 5, 7, 1, 2, 6, 9, 0]
    print(inset_sort(lst))

# [0, 1, 2, 3, 4, 5, 6, 7, 9]