博客

插入排序算法

插入排序是一种基于比较的排序算法，其基本思想是将一个未排序的元素依次插入已排序的区间中，直到所有元素都被插入到已排序的区间中。

算法步骤

1. 从第一个元素开始，将其视为已排序区间。
2. 取下一个元素，在已排序区间中从后往前扫描。
3. 如果已排序元素大于新元素，则将已排序元素后移一位。
4. 重复步骤3，直到找到已排序元素小于或等于新元素的位置，插入新元素。
5. 重复步骤2~4，直到最后一个元素被插入到已排序区间。

代码实现

以下是用Python实现插入排序的代码：

def insertionSort(arr):
    for i in range(1, len(arr)):
        for j in range(i-1, -1, -1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
            else:
                break
    return arr

算法分析

插入排序算法的时间复杂度为O(n^2)，其中n是待排序元素的个数。对于小规模的数据集，该算法的效率比其他高级排序算法（如快速排序、归并排序）更高，但对于大规模的数据集，效率会显著下降。

示例说明

示例1

输入：[3,2,1]

输出：[1,2,3]

解释：通过插入排序算法，将未排序的元素依次插入到已排序的区间中，得到排序后的结果为[1,2,3]。

示例2

输入：[4,3,2,1]

输出：[1,2,3,4]

解释：通过插入排序算法，将未排序的元素依次插入到已排序的区间中，得到排序后的结果为[1,2,3,4]。