排序2:插入排序

原创

用户9955628

发布于 2022-08-09 21:18:00

1370

发布于 2022-08-09 21:18:00

文章被收录于专栏：python3基础算法

插入排序原理：通过构建有序序列，对于未排序的数据，在已排序的序列中从后向前比较，找到位置插入。

算法思想：

第一个元素默认已排序
取出第二个元素，从后向前扫描序列
如果已排序的元素大于新元素，将两者互换
重复步骤3，直到找到已排序元素<= 新元素
将新元素插入
重复2-5步骤

代码实现：

from typing import List
def insert_sort(arr :List[int]):
    """
    插入排序
    arr：待排序list
    return：就地排序，in-place
    """
    length = len(arr)
    if length <= 1:
        return
    for i in range(1,length):
        value = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > value:
            arr[j],arr[j+1] = arr[j+1],arr[j]
            j -= 1
        arr[j+1] = value


if __name__ == '__main__':
    import random
    random.seed(54)
    arr = [random.randint(0,100) for i in range(10)]
    print(arr)
    insert_sort(arr)
    print(arr)
结果：
[17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
[17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

排序