Python 算法基础篇：插入排序和希尔排序

Python 算法基础篇：插入排序和希尔排序

引言

插入排序和希尔排序是两种常用的排序算法，用于将一个无序列表按照特定顺序重新排列。本篇博客将介绍插入排序和希尔排序的基本原理，并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 插入排序算法概述

插入排序是一种简单直观的排序算法，它将列表分成已排序部分和未排序部分。在每次遍历中，插入排序会将未排序部分的第一个元素插入到已排序部分的适当位置，使得已排序部分继续保持有序。

插入排序的主要优点是实现简单，代码量较小，并且在处理小规模数据时效率较高。然而，在处理大规模数据时，插入排序的时间复杂度较高，为 O ( n ^ 2 )，效率相对较低。

2. 插入排序算法实现

实例1：插入排序

def insertion_sort(arr):
    n = len(arr)

    # 从第二个元素开始遍历未排序部分
    for i in range(1, n):
        key = arr[i]  # 当前要插入的元素
        j = i - 1     # 已排序部分的最后一个元素的索引

        # 将大于key的元素向右移动，为key腾出插入位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

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

# 测试插入排序
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("插入排序结果：", arr)

代码解释：上述代码演示了使用插入排序对一个列表进行排序的实例。插入排序将列表分成已排序部分和未排序部分，在每次遍历时，将未排序部分的第一个元素插入到已排序部分的适当位置。通过使用 while 循环找到正确的插入位置，实现了插入排序算法。

3. 希尔排序算法概述

希尔排序是一种改进的插入排序算法，它通过设置一个增量序列，对列表进行多次分组排序。希尔排序会不断缩小增量序列的长度，直到增量序列为 1 ，此时就变为普通的插入排序。

希尔排序的主要优点是对于中等大小的列表，它的性能较好。希尔排序的时间复杂度介于 O ( n )和 O ( n ^ 2 )之间，取决于增量序列的选择。虽然希尔排序相对于插入排序有所改进，但在处理大规模数据时仍然不如快速排序和归并排序等高效的排序算法。

4. 希尔排序算法实现

实例2：希尔排序

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量，可根据实际情况调整

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

            # 插入排序，但是步长为gap
            while j >= gap and arr[j - gap] > key:
                arr[j] =

 arr[j - gap]
                j -= gap

            arr[j] = key

        gap //= 2  # 缩小增量

# 测试希尔排序
arr = [64, 34, 25, 12, 22, 11, 90]
shell_sort(arr)
print("希尔排序结果：", arr)

代码解释：上述代码演示了使用希尔排序对一个列表进行排序的实例。希尔排序通过设置增量序列，对列表进行多次分组排序。在每次遍历时，使用插入排序对分组的元素进行排序。通过不断缩小增量序列的长度，最终将列表排序完成。

5. 插入排序与希尔排序的对比

插入排序和希尔排序都是通过插入元素到已排序部分来完成排序，但希尔排序在插入排序的基础上进行了改进。

• 插入排序的增量序列为 1 ，每次只能将相邻元素进行比较和交换，因此时间复杂度较高。
• 希尔排序的增量序列由用户指定，可以对列表进行多次分组排序，使得每次插入排序的步长较大，从而减少了比较和交换的次数，提高了效率。

虽然希尔排序相对于插入排序有所改进，但在处理大规模数据时仍然不如快速排序和归并排序等高效的排序算法。

总结

本篇博客介绍了插入排序和希尔排序两种排序算法。插入排序通过比较相邻元素并插入到合适的位置，使得已排序部分继续保持有序；希尔排序通过设置增量序列对列表进行多次分组排序，减少了比较和交换的次数，提高了效率。

插入排序适用于小规模数据的排序，而希尔排序适用于中等规模的数据排序。在实际应用中，选择合适的排序算法对于提高程序性能非常重要。