插入排序（Python实现）

一句话概括：取一个元素，排一个元素。

原理（按从小到大的顺序排列）：

（1）将第一个元素视为已知（此时第一个排序已排序），第二个元素开始到最后一个元素视为未知（此时第二个元素开始 至 最后一个元素未排序）。

（2）在未知元素中取第一个元素，插入到已知元素序列中。

将未排序的第一个元素和已排序的最后一个元素进行比较，如果“未 < 已”，则交换位置，然后再与交换位置后的未 的前一个元素进行比较，直到不能交换为止，此时插入元素。

（3）特别地，经过这样 *** 作后，已知元素的顺序，都是从小到大排列的。

（4）重复 *** 作。

每插入一次，已排序的元素长度+1，未排序的元素长度-1。

例子：

[1, 4, 2, 8, 5, 7, 3, 9, 0]，将其按照从小到大的顺序排列。

def insertion_sort(ls):
    for i in range(0,len(ls)):
        current_index = i
        while ls[current_index - 1] > ls[current_index] and current_index - 1 >= 0:
            ls[current_index] , ls[current_index - 1] = ls[current_index - 1] , ls[current_index]
            current_index -= 1
    return ls

ls = [1, 4, 2, 8, 5, 7, 3, 9, 0]
print(insertion_sort(ls))