插入排序python 用python进行排序

插入排序是一种简单直观的排序算法，它的工作原理是将待排序的元素逐个插入已排序序列中的合适位置，从而得到一个有序序列。插入排序的思想类似于我们打扑克牌时整理牌的方法，每次将一张新牌插入到已经有序的牌中。

具体来说，插入排序的步骤如下：

1. 从第二个元素开始，将其与已排序序列进行比较。

2. 如果当前元素小于前一个元素，则将当前元素与前一个元素交换位置，直到找到合适的位置插入。

3. 重复步骤2，直到所有元素都被插入到合适的位置。

下面是用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
# 示例
arr = [5, 2, 8, 9, 1]
insertion_sort(arr)
print(arr)

在上述示例代码中，我们定义了一个名为`insertion_sort`的函数来实现插入排序。函数接受一个待排序的列表作为参数。

在函数内部，我们使用一个`for`循环来遍历待排序列表，从第二个元素开始。我们将当前元素存储在变量`key`中，并将其与已排序序列进行比较。

然后，我们使用一个`while`循环来找到合适的位置插入当前元素。循环条件是`j >= 0`（确保不越界）且`key < arr[j]`（找到合适的位置）。在循环中，我们将比当前元素大的元素向右移动一位，直到找到合适的位置。

我们将当前元素插入到合适的位置，即`arr[j + 1] = key`。

在示例中，我们使用列表`arr = [5, 2, 8, 9, 1]`作为待排序序列。经过插入排序后，列表变为`[1, 2, 5, 8, 9]`，即按照从小到大的顺序排列。

插入排序的时间复杂度为O(n^2)，其中n是待排序序列的长度。虽然插入排序不是最高效的排序算法，但对于小规模的数据集来说，它的性能还是比较不错的。插入排序是稳定的排序算法，即相等元素的相对顺序在排序后不会改变。

插入排序是一种简单且直观的排序算法，适用于小规模数据集的排序。通过逐个将元素插入已排序序列中的合适位置，插入排序可以得到一个有序序列。