【排序算法】插入排序_直接插入排序、希尔排序

排序算法是计算机科学中一项重要的基本操作，它支持数据的组织和检索。插入排序和希尔排序都是常用的排序算法，下面我们将详细介绍这两种算法，并给出相应的代码示例。

一、插入排序

插入排序是一种简单的排序算法，它的基本思想是将一个未排序的元素插入到已排序的部分中，以构建一个有序的序列。插入排序的过程可以分为两个部分：已排序部分和未排序部分。

具体步骤如下： 1. 从第二个元素开始，将其与前面的已排序部分进行比较。 2. 如果当前元素小于已排序部分的某个元素，就把已排序部分的元素向后移动一个位置，以为当前元素腾出空间。 3. 将当前元素插入到合适的位置，继续下一轮比较，直到所有元素都插入完成。

下面是插入排序的 Python 代码示例：

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

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

        # 插入 key
        arr[j + 1] = key

# 测试插入排序
 arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("插入排序后的数组：", arr)

时间复杂度： - 最坏和平均时间复杂度为 O(n^2)，最好的情况为 O(n)。

空间复杂度： - O(1)，因为它是原地排序算法。

二、希尔排序

希尔排序是对插入排序的一种改进。它的基本思想是将整个待排序的数组分成若干个子序列（由相隔一定间隔的元素组成），先对每个子序列进行插入排序。随着间隔逐渐减小，最终变为最终的插入排序。这种算法在一定情况下会显著减少元素移动的次数。

具体步骤如下： 1. 选择一个增量（间隔），把数组分为多个子数组。 2. 对每个子数组分别进行插入排序。 3. 减小增量，重复步骤 1 和 2，直到增量为 1。

下面是希尔排序的 Python 代码示例：

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i

            # 对各个子数组进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        gap //= 2  # 减小增量

# 测试希尔排序
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("希尔排序后的数组：", arr)

时间复杂度： - 根据增量的选择不同，希尔排序的时间复杂度在 O(n^2) 到 O(n log n) 之间。

空间复杂度： - O(1)，因为它是原地排序算法。

总结

插入排序和希尔排序都是易于实现的排序算法，适合小规模数据或基本有序的数组。插入排序简单易懂，但在处理大规模数据时效率较低，而希尔排序通过减少比较和移动次数来提高效率，适用于更大规模的数据集。选择合适的排序算法可以提高程序的性能，这对于编程和算法设计非常重要。