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

一、希尔排序简介

希尔排序是简单插入排序的一种改进，也称递减增量排序算法，它属于插入排序，但是它是一种更高效的插入排序，而且非常稳定。同时，它是排序算法中时间复杂度冲破O(n^2)的第一批算法之一。

希尔排序与简单插入排序的区别：

eg:[5,4,3,2,1,0] 对于这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后对每个分组进行简单插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。当增量为1时，这时整个数组已经基本有序，大多数数据只需要微调即可。

二、希尔排序基本思想

希尔排序是把数据按某一增量(这个增量是变化的，可以理解为跨度或者访问数据的步长)进行分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序示例：

三、希尔排序步骤 1、首先选择一个增量序列(增量序列的选择对算法会有很大的影响，但是对于具体怎么选择增量序列是一个很难解决的问题。希尔排序有一个建议的增量gap=length/2，称为希尔增量，这个增量序列虽然很常用但其实它不是最优的) 2、对于增量序列中的数进行直接插入排序 3、根据新的增量重新对数据分组，然后再进行排序，直至增量为1，整个序列一起排序

注意：在数据进行连续交换时，并不一定是真的交换，只需先把交换一方的值存入temp变量，做单向覆盖，循环结束后，再把temp的值存入交换后的位置。

四、代码实现

def shellSort(arr):    import math    gap=1    while(gap
   
    0:    # 以下其实就是以gap为间隔的直接插入排序        for i in range(gap,len(arr)):            temp=arr[i] #用一个变量把arr[i]的值存下来，要不然之后比较数据时会把arr[i]的实际值覆盖掉            j=i-gap            while j>=0 and arr[j]>temp:                arr[j+gap]=arr[j]                j -= gap            arr[j+gap]=temp        gap=math.floor(gap/3)    return arrif __name__=='__main__':    array=[3,44,38,5,15,36,46,2,48,19]    print(shellSort(array))