1.6 希尔排序

[utterances-bot]

1.6 希尔排序

希尔排序 # 1. 希尔排序算法思想 # 希尔排序（Shell Sort）基本思想： 将整个序列切按照一定的间隔取值划分为若干个子序列，每个子序列分别进行插

https://algo.itcharge.cn/01_array/01_06_array_shell_sort/

[weiyixing]

7 line 需要对间隔为gap的数据进行插入排序 第7行应该为 range（0，size，gap）
如果是range（gap，size） 当进行第二次循环的时候 会重复计算 增加不必要的运算

[itcharge]

7 line 需要对间隔为gap的数据进行插入排序 第7行应该为 range（0，size，gap） 如果是range（gap，size） 当进行第二次循环的时候 会重复计算 增加不必要的运算

这应该是两种写法。
文中写法的意思是：

1. 先按 gap 分组，对应第 4 ~ 6 行
2. 对每组进行插入排序，对应第 7 ~ 20 行
3. 其中每组插入排序的过程为：
   3.1 首先默认每组的第一个数为有序数组。
   3.2 从每组的第二个数开始（也就是第 7 行从 gap 开始的原因）。
   3.3 每一次将当前未排序元素与「该组」已排序元素依次进行比较，找到合适的插入位置，将其插入到排序数组中（对应第 8 ~ 18）行。
   3.4 每一次对分组插入排序之后，缩小 gap（对应 20 行），进行下一轮插入排序。

这里的第 7 ~ 20 行每遍历一次，就是对每组内元素进行了插入排序。并不存在重复计算。

而另一种每次增加 gap 的遍历（即 range(0, size, gap)）则需要再套一层循环（即 range(0, gap)）对分组下进行插入排序。
但这两种方法应该可行的，只是写法不同。

[weiyixing]

理解了 确实是两个思路不一样 谢谢

[NURSERYGENDAY]

public class Solution {
    public int[] shellSort(int[] arr) {
        int size = arr.length;
        int gap = size / 2;
        
        while (gap > 0) {
            for (int i = gap; i < size; i++) {
                int temp = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                
                arr[j] = temp;
            }
            
            gap = gap / 2;
        }
        
        return arr;
    }

    public int[] sortArray(int[] nums) {
        return shellSort(nums);
    }
}

[NURSERYGENDAY]

public class Solution {
    public int[] shellSort(int[] arr) {
        int size = arr.length;
        int gap = size / 2;
        
        while (gap > 0) {
            for (int i = gap; i < size; i++) {
                int temp = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                
                arr[j] = temp;
            }
            
            gap = gap / 2;
        }
        
        return arr;
    }

    public int[] sortArray(int[] nums) {
        return shellSort(nums);
    }
}

[OnlyBrownAnt]

博主，有个问题想请教下，这里的gap参数应该指的是下标位置的固定间隔数是吧？因为我看到过程图中的真实元素间隔数 = gap - 1

[Jiurouqiu8]

总觉得j = i有点奇怪，这样是不是清楚一些。

def shell_sort(lst):
    gap = len(lst) // 2
    while gap >= 1:
        for i in range(gap,len(lst)): # i：抽出固定与其他牌比较的牌
            j = i - gap # 与i进行比较的牌
            temp = lst[i]
            while j >= 0 and lst[j] > temp:
                lst[j+gap] = lst[j]
                j -= gap
            else:
                lst[j+gap] = temp
        gap = gap // 2
    return lst
    
lst = [7,2,6,8,0,4,1,5,9,3]
print(shell_sort(lst))

[Jiurouqiu8]

这个粘贴缩进全没了，铸币啊

[itcharge]

这个粘贴缩进全没了，铸币啊

没事，我帮你改一下

[Jiurouqiu8]

竟然有人看😲好嘞辛苦 ITCharge ***@***.***>于2024年8月2日 周五上午9:01写道：

…

这个粘贴缩进全没了，铸币啊 没事，我帮你改一下 — Reply to this email directly, view it on GitHub <#80 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/BFTAO575LKNEQ6BN23N4HY3ZPLK7FAVCNFSM6AAAAABL243MXKVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTAMRRG44DSNY> . You are receiving this because you commented.Message ID: ***@***.***>

[Jiurouqiu8]

def shell(lst):
    gap = len(lst) // 2
    while gap > 0:
        for i in range(gap,len(lst)):
            temp = lst[i]
            j = i - gap
            while j >= 0 and lst[j] > temp:
                lst[j+gap] = lst[j]
                j -= gap
            else:
                lst[j+gap] = temp
        gap = gap // 2
    return lst
lst = [7,2,6,8,0,4,1,5,9,3]
print(shell(lst))

[Jiurouqiu8]

唉缩进复制就没 作者能改那就谢谢了。。辛苦💦

[Jiurouqiu8]

之前也是这样想的，发了一次 作者改过了感谢 我喜欢你喵
今天想着复盘一遍，这个就不用改了。可能j = i - gap更清楚一点吗，如果根据流程图思路的话
j都是在i的左侧，与i相比。
还是要扣很长时间，哭哭喵

[evilmordy]

python3.9里会报警告：应为类型 [int]，但实际为 list[Literal[5, 4, 3, 2, 1]]
需要把[int]换成list[int]