插入排序算法是最简单的排序算法之一，其中每个元素都插入到排序列表中的适当位置，称为插入排序算法。在现实生活中，我们玩扑克牌时就是使用插入排序算法进行排序。

方法1：

「算法：」

• 从第二个元素开始（假设第一个元素已排序）。
• 将与前面的元素进行比较。
• 如果当前元素小于前一个元素，继续与再前一个元素进行比较。
• 重复此过程，知道当前元素不小于前一个元素或到达列表的开头。
• 将当前元素插入正确的位置，使列表保持排序状态。
• 对列表中的所有元素重复上述步骤。

def insertion_sort(lst):
    for i in range(1, len(lst)):
        key = lst[i]
        j = i - 1
        while j >= 0 and key < lst[j]:
            lst[j + 1] = lst[j]
            j -= 1
        lst[j + 1] = key
    return lst
lst = [8, 6, 18, 3, 9]
print("当前列表：", lst)
sorted_lst = insertion_sort(lst)
print("排序列表：", sorted_lst)

插入排序在对小列表或已经大部分排序的列表进行排序时非常有用。

方法2：

插入排序可以递归方式实现。

def insertion_Sort(arr, n):
    if n <= 1:
        return
    insertion_Sort(arr, n - 1)
    last = arr[n - 1]
    j = n - 2
    while (j >= 0 and arr[j] > last):
        arr[j + 1] = arr[j]
        j = j - 1
    arr[j + 1] = last

lst = [8, 6, 18, 3, 9]
print("当前列表：", lst)
n = len(lst)
insertion_Sort(lst, n)
print("排序列表：", lst)

def insertion_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = insertion_sort(arr[:mid])
    right_half = insertion_sort(arr[mid:])
    i, j = 0, 0
    sorted_arr = []
    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            sorted_arr.append(left_half[i])
            i += 1
        else:
            sorted_arr.append(right_half[j])
            j += 1
    sorted_arr += left_half[i:]
    sorted_arr += right_half[j:]
    return sorted_arr
lst = [8, 6, 18, 3, 9]
print("当前列表：", lst)
sorted_lst = insertion_sort(lst)
print("排序列表：", sorted_lst)

在大型列表上，插入排序算法的效率远低于其他高级算法，例如快速排序、堆排序或合并排序。但是，对于小型数据集，由于其简单性，可以更快的完成排序。

?

文章创作不易，如果您喜欢这篇文章，请关注、点赞并分享给朋友。如有意见和建议，请在评论中反馈。

?