数据结构与算法-插入排序

💝💝💝首先，欢迎各位来到我的博客，很高兴能够在这里和您见面！希望您在这里不仅可以有所收获，同时也能感受到一份轻松欢乐的氛围，祝你生活愉快！

引言

插入排序是一种简单直观的排序算法，它的工作原理类似于人们整理手中的一叠卡片。该算法通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常使用in-place排序（即只需用到O(1)的额外空间），其时间复杂度为O(n^2)，其中n是待排序数组的长度。

一、插入排序的基本思想

插入排序的基本思想是：

1. 将数组分为已排序和未排序两个部分。
2. 初始时，已排序部分只包含数组的第一个元素，其余元素视为未排序部分。
3. 从未排序部分取出一个元素，与已排序部分的元素依次比较，找到合适的位置插入。
4. 重复上述步骤，直到所有元素都被插入到已排序部分。

二、插入排序的步骤

假设有一个数组 arr 需要进行排序。

1. 初始化：将第一个元素视为已排序部分，剩余元素视为未排序部分。
2. 遍历：从未排序部分选取第一个元素 arr[j]。
3. 比较与交换：将 arr[j] 与已排序部分的元素 arr[i] 进行比较，如果 arr[j] 更小，则交换位置，否则继续与前面的元素比较。
4. 重复：重复上述步骤，直到 arr[j] 被正确插入到已排序部分。
5. 完成：当所有元素都被正确插入到已排序部分时，排序完成。

三、插入排序的实现

接下来，我们将通过一个示例来详细了解插入排序的实现步骤。

1. 示例数组

考虑一个整数数组 arr = [5, 2, 4, 6, 1, 3]。

2. 伪代码

以下是插入排序的基本伪代码：

for i = 1 to n-1 do
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key do
        arr[j+1] = arr[j]
        j = j - 1
    end while
    arr[j+1] = key
end for

3. Python 实现

下面是一个使用Python编写的插入排序算法的具体实现：

def insertion_sort(arr):
    # 获取数组的长度
    n = len(arr)

    # 从第二个元素开始遍历数组
    for i in range(1, n):
        # 保存当前元素，它将被插入到已排序的部分
        key = arr[i]

        # 初始化j为当前元素的前一个位置
        j = i - 1

        # 将大于key的元素向右移动一位
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        # 将key插入到正确的位置
        arr[j + 1] = key

    return arr

# 示例数组
arr = [5, 2, 4, 6, 1, 3]
# 调用函数
sorted_arr = insertion_sort(arr)
print(sorted_arr)

四、插入排序的时间复杂度分析

• 最好情况：当输入数组已经是排序好的时候，算法的时间复杂度为O(n)，因为不需要进行任何交换。
• 最坏情况：当输入数组是逆序的时候，算法的时间复杂度为O(n^2)，因为每插入一个元素都需要与之前的所有元素比较。
• 平均情况：插入排序的平均时间复杂度也是O(n^2)。

五、插入排序的空间复杂度分析

• 插入排序是原地排序算法，只需要常数级别的额外空间，因此其空间复杂度为O(1)。

六、总结

插入排序是一种简单有效的排序方法，尤其适用于小规模数组或者基本有序的数组。虽然它的平均和最坏时间复杂度较高，但在实际应用中，特别是当数据量不大时，它的性能是可以接受的。此外，插入排序还可以作为其他更复杂的排序算法的基础组成部分，比如希尔排序。