算法系列之-插入排序(二)

插入排序就跟我们玩扑克牌有点像，每次摸取一张牌就插入到对应的位置，最后这手牌就是有序的；
其主要思想是：例如数组arr=[3,1,2,4] 从第一个脚标位置取数arr[1]=1,和它前面的数据进行比较
如果比前面的数小就交换位置变成[1,3,2,4],前面没有元素了，跳出二层循环，第二轮开始arr[2]=2,
2比3小，交换位置[1,2,3,4], 2比1大，二层循环结束.....依次重复

下为python实现代码

class InsertSort():
    def insertSort(self, list):
        for i in range(1, len(list)):
            for j in range(i, 0, -1):
                if list[j] < list[j - 1]:
                    list[j], list[j - 1] = list[j - 1], list[j] #这里平凡交换导致效率不高，可以有优化的空间。
                else:
                    break
        return list

#优化后这个交换变成赋值，可以提升效率
    def insertSort1(self, list):
        for i in range(1, len(list)):
            e = list[i]
            for j in range(i, -1, -1):
                if list[j - 1] > e:
                    list[j] = list[j - 1]
                else:
                    break
            list[j] = e

        return list

我们可以看到，插入排序在二层循环的时候有结束循环的条件，因此它的速度会优于选择排序，选择排序必须每次走完二层循环，但插入排序可提交终止二层循环，特别在近乎有序的排序时，插入排序优势更为明显。