插入排序 python

### 回答1：
下面是 Python 实现的插入排序代码：

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

其中，`arr` 是待排序的数组。该算法的时间复杂度为 $O(n^2)$。

### 回答2：
插入排序是一种简单直观的排序算法，适用于小规模数据的排序。其基本思想是将数组分为已排序和未排序两个部分，每次从未排序部分选择第一个元素，插入到已排序部分的正确位置，直到所有元素都被插入完成。

在Python中实现插入排序的代码如下：

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

    return arr

在上述代码中，我们使用了一个循环来遍历未排序部分，从第二个元素开始（索引为1），将当前元素赋值给`key`变量。接着，我们使用一个内层循环，从已排序部分的最后一个元素开始比较，如果比`key`大，则将该元素后移一位，直到找到合适的位置将`key`插入。最后，将`key`插入到正确的位置上，完成一轮插入。

最终，函数返回经过插入排序后的数组。

例如，对于输入数组`[3, 1, 4, 2]`，经过插入排序后的结果为`[1, 2, 3, 4]`。

插入排序的时间复杂度为O(n^2)，可以通过一些优化措施（如二分查找）来提高性能。但由于插入排序的效率较低，仅推荐对小规模的数据进行排序。

### 回答3：
插入排序是一种简单直观的排序算法，它将一个待排序的序列分为已排序和未排序两部分。

算法的思想是，假设第一个元素是已排序的，然后将第二个元素插入到已排序的序列中的合适位置。然后将第三个元素插入到新的已排序序列中的合适位置，依此类推，直到所有元素都插入到已排序序列中。

Python代码实现插入排序如下：

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

arr = [5, 2, 4, 6, 1, 3]
insert_sort(arr)
print("插入排序后的结果：", arr)

以上代码中，我们首先获取待排序序列的长度n，然后从第二个元素开始遍历，将当前元素存储在key中，然后将key与前面的已排好序的元素逐个比较并进行移位操作，直到找到合适的插入位置。

在内部的while循环中，我们将arr[j]的值向后移一位，直到找到合适的位置将key插入到arr[j + 1]中。

最后，我们得到的arr就是排好序的序列。

插入排序的时间复杂度为O(n^2)，当序列已经有序时，时间复杂度可以降为O(n)。在实际应用中，插入排序比较适用于序列较小且基本有序的情况。