Shell Sort与Insertion/Bubble Sort有什么好处？

Question

我的教授给了我以下Shell Sort的定义.我也包括了Bubble和Insertion Sort算法.

使用Shell Sort与常规插入排序或冒泡排序有gap=1什么好处？最终,壳牌排序归结为无论如何,对吧？

我不是要你做我的作业.我合法地感到困惑,想要了解发生了什么.

此外,我已经访问过维基百科,看过时间复杂度表,我已经知道他们说了什么.我正在寻找原因,而不是什么.

def shell(a, n):
    gap = n / 2

    while gap >= 1:
            insertion(a, n, gap) # or bubble
            gap /= 2

def bubble(a, n, gap=1):
    for i in range(n):
            for j in range(n-i-gap):
                    if a[j] > a[j+gap]:
                            swap(a, j, j+1)

def insertion(a, n, gap=1):
    for i in range(1,n):
            x = a[i]
            j = i-gap

            while j>=0 and  a[j]>x:
                    a[j+gap] = a[j]
                    j-=gap

            a[j+gap]=x

Answer 1

Shell排序允许交换相距很远的索引,其中冒泡排序仅交换相邻的项目.

维基百科上的条目

• http://en.wikipedia.org/wiki/Shell_sort
• http://en.wikipedia.org/wiki/Insertion_sort
• http://en.wikipedia.org/wiki/Bubble_sort

掩盖差异.

编辑:

想象一下,你手里拿着一堆卡片,卡片几乎是有序的,除了第一个和最后一个被交换.冒泡排序会很痛苦,因为有大约2n个交换,插入排序会更好用n个交换,但shell排序可以在1中完成.(交换数量因算法实现而异,这只是一个例子)

Answer 2

shell 排序的逻辑是先对距离较远的条目进行排序。给定一个部分排序的列表，理论上你可以比 O(n^2) 快得多。还给出了一个大的未排序数组，您的最终排序位置远离当前位置的可能性很高。所以从逻辑上讲，使用更大的间隙是有意义的。但是shell排序的重点并不是它的性能，而是算法的简单性和堆栈内存的低使用率。

鉴于平均而言它比 O(n^2)（取决于间隙序列）、小代码大小和堆栈使用更好，它在内存限制是一个因素的嵌入式应用程序中非常流行。