本文共 1587 字，大约阅读时间需要 5 分钟。

一、背景

加深自己对经典排序算法的理解，并且探索更多简化的写法和优化的表现。

二、算法介绍

1. 插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动 。

2. 希尔排序(Shell's Sort)是的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，便终止。

三、经典代码实现：

def insert_sort(random_list: list) -> list:    """    插入排序 保证前面的队列是一个有序的  每次从后面找一个插入到有序的里面去  当后面的数比前面小才需要进行插入  否则跳过当前数    :param random_list:    :return:    """    length = len(random_list)    if length <= 1:        return random_list    for i in range(1, length):        for j in range(i,0,-1):            if random_list[j-1] > random_list[j]:                random_list[j-1], random_list[j] = random_list[j], random_list[j-1]            else:                break    return random_listdef shell_sort(random_list: list) -> list:    """    希尔排序 插入排序的优化  按照步长进行多次插入排序  每次把步长缩短一半  直到步长为1    :param random_list:    :return:    """    length = len(random_list)    if length <= 1:        return random_list    gap = length//2    while gap > 0:        for i in range(gap, length):            for j in range(i, 0, -gap):                if random_list[j-gap] > random_list[j]:                    random_list[j], random_list[j-gap] = random_list[j-gap], random_list[j]        if gap == 1:            break        gap = gap//2    return random_list

四、优化思考

插入排序的方法很容易理解，依次将未排序的插入到已排序的列表中，而希尔排序则是宏观上对插入排序进行多次调控后，最后再按照插入排序进行排序，这样看起来操作次数增加了，但是减少了在插入的时候寻找到合适位置的次数，因此算法效率得到了提升。

转载地址：https://blog.csdn.net/wenq_yang/article/details/109162256 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！