阳光沙滩
让学习编程变得简单
插入排序算法讲解(InsertionSort)
发表于 2020-05-09    阅读次数 174

1.引例

打牌习惯性地将牌按照一定大小顺序排列,在摸牌过程中,每摸到一张牌,就会按照大小规则将它插入到手中的牌,这就是插入排序。

2.算法描述

插入排序分为两组数据,已经排序的数据。等待排序的数据,从等待排序的数据,向已经排序的数据中对比插入。

3.算法示图

图片描述

4.代码实现

def InsertionSort(array):
    # 从第二个元素开始遍历
    for i in range(1,len(array)):
        # 需要排序的元素
        target = array[i]
        # j表示已经排序好的数量
        j = i-1
        # 所有元素向后移动,直至target找到合适的位置
        while(j>=0 and target<array[j]):
            # 数据右移
            array[j+1] = array[j]
            j -= 1
            # 如果j=0,说明target需要插入第一位。注意:此时while中判断为array[-1],在某些编译器中会出现数组值错误
            # 避免错误的解决方式(在pythona中无需添加这段代码,fortran中需要添加,否则报错越界,需要注意的是在java中while判断中会出现array[-1]的情形,array[-1]不被准许,但由于j>=0已经为False,所以程序不再往后读取,直接退出循环,但某些编译器可能会出现问题)
            if j==0:
                break;
        array[j+1] = target
        print(array)
    return array

if __name__ == '__main__':
    arr = [344,4,345,78,5,68,9,4879,1548,44,23,99,14785,457,233]
    InsertionSort(arr)

5.运行结果

[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 344, 345, 78, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 78, 344, 345, 5, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 78, 344, 345, 68, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 68, 78, 344, 345, 9, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 4879, 1548, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 68, 78, 344, 345, 1548, 4879, 44, 23, 99, 14785, 457, 233]
[4, 5, 9, 44, 68, 78, 344, 345, 1548, 4879, 23, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 344, 345, 1548, 4879, 99, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 1548, 4879, 14785, 457, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 344, 345, 457, 1548, 4879, 14785, 233]
[4, 5, 9, 23, 44, 68, 78, 99, 233, 344, 345, 457, 1548, 4879, 14785]

6.来源——阳光沙滩微信公众号

链接:阳光沙滩插入排序算法