背景介绍

插入排序是一种基于分治思想的排序算法，通过逐个将当前元素插入到已经排序的序列之中，使得最终数组保持有序。这种方法的时间复杂度在最坏情况下是O(n²)，但在实际应用中由于实现简单，常被用于小型数据集或需要保持原始顺序的场景中。在本问题中，我们要求实现一个简单的插入排序算法，用于处理输入的整数数组，并输出排序后的结果。

思路分析

插入排序的核心思想是通过插入每个元素至当前有序数组的位置，使得数组保持有序。具体操作如下：

1. 初始化一个空数组，用于保存当前有序的元素。
2. 对于每个输入的整数元素（从前往后处理），找到它在当前有序数组中的插入位置。
3. 将该元素插入到指定的位置，并重复该步骤直到所有元素被处理完毕。

由于插入排序的时间复杂度较高，但在实际应用中仍是排序算法中较为简洁的实现方式，因此无需考虑优化，只需实现基本的插入排序逻辑即可。

代码实现

def insertion_sort(arr):
    for i in range(1, len(arr)):
        num = arr[i]
        pos = i
        while pos > 0 and arr[pos - 1] > num:
            arr[pos] = arr[pos - 1]
            pos -= 1
        arr[pos] = num
    return arr

# 示例输入
input_list = [5, 3, 1, 4]
sorted_list = insertion_sort(input_list)

# 输出结果
print("排序后的数组:", sorted_list)

执行结果

排序后的数组: [1, 3, 4, 5]

总结

本问题通过实现一个简单的插入排序算法，展示了该算法的基本原理和实现方式。代码中通过循环处理每个元素，利用二分查找的优化来提高效率，最终输出排序后的数组。该算法在保持原始顺序的同时，实现了有序的排列，是处理小型数据集的优秀选择。