python 插入排序

插入排序是一种简单直观的排序算法，它通过构建有序序列，对未排序的数据在已排序序列中从后向前扫描，找到相应位置并插入。

在 Python 中，可以使用以下代码实现插入排序：

def insertion_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, 8, 10, 1]
insertion_sort(arr)
print("排序后的数组：", arr)

这段代码定义了一个 `insertion_sort` 函数，它接受一个数组作为输入，并对其进行插入排序。算法首先从数组的第二个元素开始遍历，将当前元素标记为 `key`。然后，将 `key` 与其前一个元素进行比较，如果前一个元素较大，则将其向后移动一位，直到找到合适的位置将 `key` 插入。最后，整个数组就会按照升序排列。

示例中的输出结果为：`排序后的数组： [1, 2, 5, 8, 10]`。

相关问题

python 插入排序

Python的插入排序可以通过以下代码实现：

def insertionSort(arr):
    for i in range(len(arr)):
        preIndex = i-1
        current = arr[i]
        while preIndex >= 0 and arr[preIndex] > current:
            arr[preIndex + 1] = arr[preIndex]
            preIndex -= 1
        arr[preIndex + 1] = current
    return arr

这段代码使用了插入排序算法，它的基本思想是将一个待排序的记录，按其关键码值的大小插入到前面已经排序的数组中的适当位置上，直到全部插入完为止。插入排序是一种简单直观且稳定的排序算法，适用于少量数据的排序，时间复杂度为O(n^2)。它通过不断地将未排序的数据插入到已排序序列中，保持相对次序不变，因此是一种稳定的排序算法。[1][2][3]

python插入排序代码

好的，以下是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

这个函数接受一个列表作为输入，并返回一个已排序的列表。它使用插入排序算法对列表进行排序。

相关问题:
1. 插入排序的时间复杂度是多少？
2. 插入排序和冒泡排序有什么区别？
3. 插入排序在哪些情况下表现良好？