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

方法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 lstlst = [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] = lastlst = [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_arrlst = [8, 6, 18, 3, 9]print("当前列表：", lst)sorted_lst = insertion_sort(lst)print("排序列表：", sorted_lst)

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

❝

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

❞