插入排序之希尔排序

算法思路：

先取一个小于 n 的整数  作为第一个增量，把文件的全部记录分组。所有距离为  的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量  重复上述的分组和排序，直至所取的增量，即所有记录放在同一组中进行直接插入排序为止。

该方法实质上是一种分组插入方法。

时间复杂度：

希尔排序的平均时间复杂度为

 空间复杂度：

希尔排序使用了插入排序的方法，所以空间复杂度和插入排序相同，

 稳定性：

是不稳定。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

c++代码

void shellSort(int ls[], int len) {
    
    int temp = 1;
    while (temp < len/3) {
        temp = 3*temp+1;
    }
    
    while (temp >= 1) {
        for (int i=temp; i=temp; e 
import math
def shellSort(ls):
   
    temp=1
    while(temp < len(ls)/3):
        temp = temp*3+1
    while temp > 0:
        for i in range(temp,len(ls)):
            gap = ls[i]
            j = i-temp
            while j >=0 and ls[j] > gap:
                ls[j+temp]=ls[j]
                j-=temp
            ls[j+temp] = gap
        temp = math.floor(temp/3)
    return ls
ls = [0,11,52,458,8]
print(shellSort(ls))