插入排序python

插入排序是一种简单且有效的排序算法，它的基本思想是将一个未排序的元素插入到已排序的序列中，从而形成一个新的有序序列。在Python中，可以使用以下代码实现插入排序：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr\[i\]
        j = i - 1
        while j >= 0 and arr\[j\] > key:
            arr\[j + 1\] = arr\[j\]
            j -= 1
        arr\[j + 1\] = key
    return arr

在这个代码中，我们使用了一个for循环来遍历未排序的元素，将每个元素插入到已排序的序列中。内部的while循环用于找到插入位置，并将元素逐个向后移动，直到找到合适的位置。最后，我们将当前元素插入到正确的位置。

例如，对于输入列表\[6, 5, 3, 1, 8, 7, 2, 4\]，经过插入排序后，输出为\[1, 2, 3, 4, 5, 6, 7, 8\]。

插入排序是一种稳定的排序算法，它的时间复杂度为O(n^2)，其中n是待排序元素的数量。尽管插入排序在处理大型数据集时效率较低，但对于小型数据集或部分有序的数据集，它是一个不错的选择。
#### 引用[.reference_title]
- *1* [Python实现插入排序](https://blog.csdn.net/csh2388827741/article/details/116696946)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *2* *3* [Python 实现插入排序算法](https://blog.csdn.net/s1t16/article/details/126746547)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]