使用Python实现插入排序算法

插入排序是一种简单直观的排序算法，它的基本思想是将一个记录插入到已经排序好的有序表中，使得插入后仍然保持有序。下面我们用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

# 测试例子
arr = [5, 3, 8, 6, 2, 7, 1, 4]
insertion_sort(arr)
print("排序结果：", arr)

在上面的代码中，我们首先定义了一个 insertion_sort 函数来实现插入排序算法。该函数接受一个列表 arr 作为输入，并按照递增顺序对其进行排序。

在主程序中，我们定义了一个测试例子 arr = [5, 3, 8, 6, 2, 7, 1, 4]，然后调用 insertion_sort 函数对其进行排序。最后将排序后的结果打印输出。

运行以上代码，得到的输出结果为：排序结果： [1, 2, 3, 4, 5, 6, 7, 8]，说明插入排序算法成功地将输入列表按照递增顺序进行了排序。

插入排序的时间复杂度为 $O(n^2)$，其中 n 是要排序的元素个数。尽管插入排序的时间复杂度较高，但它却具有以下优点：一是算法简单，实现容易；二是稳定排序，如果两个元素的值相等，排序后它们的相对位置不会改变。这使得插入排序在某些特殊情况下非常有用。

除了上述示例，插入排序还可以应用于其他各种类型的数据，例如字符串、浮点数等。只需要将待排序的数据存储在一个列表中，并传递给 insertion_sort 函数即可。