Sorting_Visualization icon indicating copy to clipboard operation
Sorting_Visualization copied to clipboard

shell sort实现错了

Open Baobaobear opened this issue 4 years ago • 6 comments

路过发现错误发个issue

Baobaobear avatar Oct 17 '19 16:10 Baobaobear

您好,可以说一下错在哪里吗?

ZQPei avatar Dec 19 '19 03:12 ZQPei

内循环步长是D没有问题,但外循环步长是1才对,请参阅 Shellsort wiki

Baobaobear avatar Dec 24 '19 08:12 Baobaobear

我认为应该是这样,运行没问题:

   Length = ds.length
    D = Length // 2
    while D > 0:
        c = 0
        while c < D:
            i = c + D
            while i < Length:
                tmp = ds.data[i]
                j = i
                while j>c and ds.data[j-D]>tmp:
                    ds.SetVal(j, ds.data[j-D])
                    j -= D
                ds.SetVal(j, tmp)
                i+=D
            c += 1
        D//=2

但是建议用更简洁的形式:

Length = ds.length
    col_num = Length // 2 # 初始列数
    # print(ds.data)
    while col_num > 0: # 逐渐减少列数,最后减少到1列
        for c in range(col_num): # 对第c列进行插入排序
            for cp in range(c+col_num,Length,col_num):
                tmp = ds.data[cp]
                j=cp
                while j>c and ds.data[j-col_num]>tmp: # 寻找插入位置
                    ds.SetVal(j, ds.data[j-col_num])
                    j -= col_num
                ds.SetVal(j, tmp)
        # print(ds.data)
        col_num //= 2 # 列数减半

AlterWL avatar Feb 07 '20 01:02 AlterWL

@AlterWL 你写成三重循环更不对了,请看我给的链接

Baobaobear avatar Feb 07 '20 02:02 Baobaobear

改了一下,这样对吗?

    Length = ds.length
    col_num = Length // 2 # 初始列数
    while col_num > 0: # 逐渐减少列数,最后减少到1列
        for cp in range(col_num,Length):
            tmp = ds.data[cp]
            j=cp
            while j>=col_num and ds.data[j-col_num]>tmp: # 寻找插入位置
                ds.SetVal(j, ds.data[j-col_num])
                j -= col_num
            ds.SetVal(j, tmp)
        col_num //= 2 # 列数减半

AlterWL avatar Feb 07 '20 02:02 AlterWL

这个看起来是对的

Baobaobear avatar Feb 07 '20 04:02 Baobaobear