Python实现插入排序算法

插入排序是一种简单直观的排序算法，其基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数量增加1的有序表。该算法的时间复杂度为O(n^2)。

下面是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循环，将比当前元素大的元素依次向后移动，直到找到合适的位置插入。

最后，我们将当前元素插入到合适的位置。

下面是一个使用插入排序算法的例子，从小到大对一个数组进行排序：

arr = [5, 2, 4, 6, 1, 3]

sorted_arr = insertion_sort(arr)

print("排序后的数组：", sorted_arr)

输出结果为：

排序后的数组： [1, 2, 3, 4, 5, 6]

通过这个例子，我们可以看到插入排序算法能够将一个无序的数组按照从小到大的顺序进行排序。

插入排序算法相对于其他排序算法来说，实现较为简单，代码量较少。但是它的效率相对较低，尤其是在处理大规模数据时的性能明显不足。因此在实际使用中，更多地会选择快速排序、归并排序等更高效的排序算法。