希尔排序-python版

最新推荐文章于 2025-04-11 18:34:05 发布

csdn_persist

最新推荐文章于 2025-04-11 18:34:05 发布

阅读量176

点赞数

分类专栏：笔试+面试

本文链接：https://blog.csdn.net/CSDN_persist/article/details/94649704

版权

笔试+面试专栏收录该内容

10 篇文章

订阅专栏

希尔排序是一种基于插入排序的快速排序算法，通过设置不同的增量序列来分组元素，对每组进行排序，然后逐渐减少增量直到为1，完成排序过程。通常初始增量选择序列的一半，之后每次减半，直至增量为1。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

希尔排序思想：
算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。

  
def shell_sort(list):
    n = len(list)
    gap = n//2
    new_list =[]
    while gap > 1:
        for i in range(gap):
            if list[i] > list[i+gap]:
                list[i], list[i+gap] = list[i+gap], list[i]
        gap = gap // 2;
    if gap == 1:
        for j in range(n):
            if j == 0:
                new_list.append(list[j])
            else:
                new_list.append(list[j])
                for k in range(j, 0, -1):
                    if new_list[k] < new_list[k-1]:
                        new_list[k], new_list[k-1] = new_list[k-1], new_list[k]
    return new_list




if __name__ == '__main__':
    a = [58,89,56,3,4,5,79879,263536,45215,4543]
    b = shell_sort(a)
    print(b)