Shell 排序最小比较

Question

给定 5,1 的间隙列表，shell 排序对 8 项列表进行排序所需的最少比较次数是多少？

我知道最好的案例性能是 n(log(n)) 案例，但我无法通过数学运算来获得将给定数字放入其中以获得最少比较次数所需的完整表达式。

Answer 1

不，当元素的数量任意大时，人们会说渐近时间 n。当你有精确数量的元素时，它们的数量是恒定的。因此是O(1)。

只是在一般情况下它是 BC O(n log n) 用于处理“n”个元素。但是，通常人们对WC更感兴趣。

在这里你需要手工计算或者编写一个简单的程序来计算它们。

来自伪代码：

# Sort an array a[0...7].
gaps = [5, 1]
foreach (gap in gaps) {
    for (i = gap; i < n; i += 1) {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
            a[j] = a[j - gap]

            a[j] = temp
    }
}

插入数字现在很简单。

只是为了做，不知道元素的值只能看WC。从上面的代码中，我们有 5 的间隙 5,6,7 然后内部循环也为它们中的每一个执行一次，因为 j = i; j >= gap; j -= gap。对于间隙 1，您在外部 for 循环中有 1..7，然后每次执行（WC！）都会减少 1。总而言之，您有：

gap(5) + gap(1) = (1 + 1 + 1) + (1 + 2 + 3 + 4 + 5 + 6 + 7) = 31

Answer 2

对于 shellsort 所需的最少比较次数，您需要输入一个几乎排序的向量，该向量专门针对所选的空位序列量身定制。

shellsort 的最后一步是插入排序。输入排序数据时，没有其他排序方法比插入排序更快，它只需要 n-1 次比较。

shellsort 的思想是对相距较远的值进行预排序，以便插入排序的 "ground is paved" 执行尽可能少的比较。反向输入序列是插入排序中比较成本最高的，它需要 n*(n-1)/2 次比较。如果您进行预排序 - 无论间隙序列如何 - 最终插入排序将需要比单独使用插入排序更少的比较。但是，当您总结预排序中的比较次数并将它们添加到最终插入排序中的比较时，您会发现您是否设法改善了基本插入排序的结果。

有两个数据序列 - 给定 n=8 - 在插入排序中需要相同数量的比较：

"01234567" and
"10234567" though this causes a swap of "1" and "0"

无论如何，两者都需要n-1 => 7次比较。

当我们添加 5-gap 时，它会添加 3 个比较：s[0] 与 s[5]、s[1] 与 s[6] 和 s[2] 与 s[7]。给定前面提到的两个插入排序向量，我们发现比较应该如下，为最小比较插入排序铺平道路：

s[0] with s[5] - "0"w"5" and "5"w"0" xor "1"w"5" and "5"w"1"
s[1] with s[6] - "1"w"6" and "6"w"1" xor "0"w"6" and "6"w"0"
s[2] with s[7] - "2"w"7" and "7"w"2"

因为前两个比较案例有共同的“0”和“1”，所以不能同时有“0”或同时有“1”。如果“0”是第一次比较的一部分，那么“1”是第二次比较的一部分，反之亦然。

当 gap = {5,1} 且 n=8 时，这给出了以下序列以实现最小 (3+7) 比较 shellsort：

                      5-gap                               1-gap (insertion sort)
"01234567" - 0 swaps
"01734562" - 1 swaps:                         "7"w"2"
"06234517" - 1 swaps:             "6"w"1"
"06734512" - 2 swaps:             "6"w"1" and "7"w"2"
"51234067" - 1 swaps: "5"w"0"
"51734062" - 2 swaps: "5"w"0" and             "7"w"2"
"56234017" - 2 swaps: "5"w"0" and "6"w"1"
"56734012" - 3 swaps: "5"w"0",    "6"w"1" and "7"w"2"
"10234567" - 1 swaps:                                     "1"w"0"
"10734562" - 2 swaps:                         "7"w"2" and "1"w"0"
"16234507" - 2 swaps:             "6"w"0" and             "1"w"0"
"16734502" - 3 swaps:             "6"w"0",    "7"w"2" and "1"w"0"
"50234167" - 2 swaps: "5"w"1" and                         "1"w"0"
"50734162" - 3 swaps: "5"w"1",                "7"w"2" and "1"w"0"
"56234107" - 3 swaps: "5"w"1",    "6"w"0" and             "1"w"0"
"56734102" - 4 swaps: "5"w"1",    "6"w"0",    "7"w"2" and "1"w"0"

总共有 16 个序列导致总共 8 个中的最小比较 shellsort！或 40320 个可能的序列。

在 n=8 时可能的 2^(n-2) 或 64 个可能的间隙序列中，{5,1} 是最好的（@ 平均 17.4 次比较），紧随其后的是 {6,1}，{ 7,5,1}、{7,4,1}、{4,1} 和 {3,1} 的顺序。它们都需要平均少于 18 次比较。插入排序平均需要19.3次比较

这些空位序列的其他特征（包括插入排序以供比较）：

                    number of comparisons
                    in a                             when
gap sequence        minimum sort      maximum sort   input sequence reversed
{1} (insertion sort)        7                28                    28
{3,1}                      12                24                    19
{4,1}                      11                26                    20
{5,1}                      10                24                    15
{6,1}                       9                25                    16
{7,4,1}                    12                24                    15
{7,5,1}                    11                23                    17

Shell 排序最小比较

Shell Sort Minimum Comparisons

algorithm

performance

time-complexity

shellsort