排序2:插入排序

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

算法思想：

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

代码实现：

代码语言：javascript复制

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]

排序 数据 算法 原理

0 人点赞