插入排序算法详解：原理、实现和Python代码示例

插入排序是一种常见的排序算法，其思路是将一个未排序的元素插入到已排序的元素的合适位置，从而完成排序。

实现步骤

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5，直到排序完成。

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 = [3, 2, 1, 5, 4]
print(insertion_sort(arr))  # [1, 2, 3, 4, 5]

时间复杂度

插入排序的时间复杂度为$O(n^2)$，在数据规模较小的情况下表现良好，但是对于大规模数据排序效率较低。

总结

插入排序算法是一种简单易懂的排序算法，适合用于数据规模较小的场景。在实际应用中，可以根据数据规模选择更合适的排序算法。