基于Python3.7的排序算法--插入排序

插入排序（Insertion Sort）

概念：
插入排序（Insertion Sort）是一种简单直观的排序算法。它通过构建有序序列，对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。

分析：
1、将数据分成两半，前一半是已排好序的，后一半是待排序的；
2、每次取后一半中的第一个数，在已排序的一半中，逆序依次比较，找到要插入的位置。

def insert_sort(blist):
    n = len(blist)

    #从第二个元素开始遍历所有元素，因为第一个元素已经有序了
    for i in range(1, n):
        #alist[i]之前是已排序的数列，逆序依次比较
        for j in range(i, 0, -1): 
           if blist[j] < blist[j-1]:
               blist[j], blist[j-1] = blist[j-1], blist[j]
    return blist

arr = [11, 22, 100, 99, 89, 33, 66, 101, 2000, 0, -90]
print('排序后：', insert_sort(arr))

输出结果：

排序后： [-90, 0, 11, 22, 33, 66, 89, 99, 100, 101, 2000]