针对希尔排序算法的最坏情况确定性地创建一个包含 100 个元素的集合

Question

两个问题。

1. 我可以确定性地生成一个包含 100 个元素 (1,2,...,100) 的数组，这是希尔排序算法的最坏情况吗？
2. 如果没有，为什么？为什么只有随机方式？

我尝试过的

1. 反转算法的步骤确实有效，因为 h=1 在最后一步对集合进行排序。
   当我排除它并将 h=4 作为最后一个时，然后再次对数组中的每 4 个元素进行排序。

def generate_worst_case_shell_sort(n, gaps):
    # Start with a sorted array
    array = list(range(1, n + 1))
    
    for gap in reversed(gaps):
        # Process groups defined by the gap
        for i in range(gap):
            group = array[i::gap]
            # Reverse sort each group
            group.sort(reverse=True)
            array[i::gap] = group
    
    return array

# Example usage
n = 100
gaps = [1, 4, 13, 40]
worst_case_array = generate_worst_case_shell_sort(n, gaps)
print(worst_case_array)

2. 根据当前的 h 编写移动元素的数学公式，事实证明这非常棘手。例如，我意识到，对于 h=40，100 个元素的集合将被分成 20 个元素的块。而且它们是对称交换的。当我移动到 h=13 时，事实证明交换不再那么简单。

算法

这是一种可能的实现方式。

def shell_sort(A):
    N = len(A)
    h = 1
    while h < N // 3:
        h = h * 3 + 1
    while h >= 1:
        for i in range(h, N):
            for j in range(i, h-1, -h):
                if less(A[j], A[j - h]):
                    exch(A, j, j - h)
        h //= 3

背景

Rene Argento 建议 作者暗示采用随机生成的随机方法。 2.1.19 问题来自 Robert Sedgewick 和 Kevin Wayne 的算法（第 4 版）。

相关

类似的问题是质疑 - here 和 here - 复杂性，我只对具有 100 个元素生成/创建的数组感兴趣。

Answer 1

我不明白你如何确定 n = 10 时 shellsort 的最坏情况 37。我的意思是你使用了哪组间隙，它们是 n = 10 时的最佳组吗？

我发现 n = 10 的最佳间隙集会产生 35 次比较的最坏情况 - 这就是我问的原因。

但也许最初的问题并不关心最好的间隙集合，也许任何集合都可以使用？