Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

shell sort实现错了 #4

Open
Baobaobear opened this issue Oct 17, 2019 · 6 comments
Open

shell sort实现错了 #4

Baobaobear opened this issue Oct 17, 2019 · 6 comments

Comments

@Baobaobear
Copy link

路过发现错误发个issue

@ZQPei
Copy link
Owner

ZQPei commented Dec 19, 2019

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

@Baobaobear
Copy link
Author

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

@AlterWL
Copy link

AlterWL commented Feb 7, 2020

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

   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 # 列数减半

@Baobaobear
Copy link
Author

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

@AlterWL
Copy link

AlterWL commented Feb 7, 2020

改了一下,这样对吗?

    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 # 列数减半

@Baobaobear
Copy link
Author

这个看起来是对的

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants