Python插入排序

插入排序是一种简单的排序算法，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要移动元素以腾出空间。
以下是Python中实现插入排序的示例代码：

1. def insertion_sort(arr):
2.     # 遍历数组中的所有元素，从第二个元素开始
3.     for i in range(1, len(arr)):
4.         key = arr[i]  # 当前要插入的元素
5.         j = i - 1
6.         # 将大于key的元素向后移动
7.         while j >= 0 and key < arr[j]:
8.             arr[j + 1] = arr[j]
9.             j -= 1
10.         # 将key插入到正确的位置
11.         arr[j + 1] = key
13. # 示例
14. arr = [12, 11, 13, 5, 6]
15. insertion_sort(arr)
16. print("排序后的数组:", arr)

复制代码

插入排序的时间复杂度是O(n^2)，其中n是数组的长度。在最好的情况下（输入数组已经是排序的），时间复杂度是O(n)。插入排序对于小数据集或基本有序的数据集来说服从很高，但对于大数据集，服从较低。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。