python - 排序技术 Python

Question

我正在尝试创建一种对数字列表进行排序的排序技术。但它所做的是比较两个数字，第一个是列表中的第一个数字，另一个数字是 2^k - 1 的索引。

2^k - 1 = [1,3,7, 15, 31, 63...]

例如，如果我有一个列表 [1, 4, 3, 6, 2, 10, 8, 19]

这个列表的长度是 8。所以程序应该在 2^k - 1 列表中找到一个小于 8 的数字，在本例中它将是 7。

现在它将比较随机列表中的第一个数字 (1) 和同一列表中的第 7 个数字 (19)。如果它大于第二个数字，它将交换位置。

在这一步之后，它将继续到 4 和之后的第 7 个数字，但是那不存在，所以现在它应该与 4 之后的第 3 个数字进行比较，因为 3 是 2^{k 中的下一个数字} - 1.

所以它应该比较 4 和 2，如果它们不在正确的位置则交换。所以这应该一直持续下去，直到我达到 2^k 中的 1 - 1 最终将对列表进行排序。

我需要帮助开始使用此代码。

到目前为止，我已经编写了一个小代码来生成 2^k - 1 列表，但这是我目前为止所得到的。

a = []

for i in range(10):
    a.append(2**(i+1) -1)

print(a)

示例:

考虑对序列 V = 17,4,8,2,11,5,14,9,18,12,7,1 进行排序。跳绳序列 1、3、7、15，... 产生 r=7 作为适合的最大值，因此查看 V，第一个稀疏子序列 =17,9，所以当我们传递 V 时，我们在第一次交换后产生 9,4,8​​,2,11,5,14,17,18,12,7,1，并且9,4,8​​,2,1,5,14,17,18,12,7,11 完全使用 r=7 后。使用 a=3(跳过中的下一个较小的项序列)，第一个稀疏子序列 = 9,2,14,12，应用于 V 时给出 2,4,8,9,1,5,12,17,18,14,7,11，其余 a = 3 排序给出 2,1,8,9,4,5,12,7,18,14,17,11，然后是 2,1,5,9,4,8​​,12 ,7,11,14,17,18。最后，a = 1，我们得到 1,2,4,5,7,8,9,11,12,14,17,18。

你可能想知道，鉴于最后我们做了一个没有跳过的排序，为什么这可能比简单地将最后一步作为开始的唯一步骤来更快。把它想象成一把梳子遍历序列——请注意，在前面的步骤中，我们使用航向梳来获取距离较远的事物正确的顺序，逐渐使用更精细的梳子，直到最后我们的微调处理的是一个接近排序的序列几乎不需要调整。

p = 0
x = len(V) #finding out the length of V to find indexer in a
for j in a: #for every element in a (1,3,7....)
    if x >= j: #if the length is greater than or equal to current checking value
        p = j #sets j as p 

这样就可以找到它应该与列表中的第一个数字进行比较的距离，但现在我需要写一些东西，一直这样做直到距离超出范围，所以它从 3 切换到 1，然后只检查较小的距离直到列表被排序。

Answer 1

您描述的排序算法实际上称为 Combsort 。事实上，更简单的冒泡排序是 combsort 的一个特例，其中间隙始终为 1 并且不会改变。

由于您对如何开始这个感到困惑，因此我建议您这样做:

1. 首先实现冒泡排序算法。逻辑更简单，在编写时更容易推理。
2. 一旦完成，您就拥有了重要的算法结构，接下来只需将间隙长度计算添加到组合中即可。这意味着，使用您的特定公式计算间隙长度。然后，您将修改循环控制索引和内部比较索引以使用计算出的间隙长度。
3. 在循环的每次迭代后，您将间隙长度(实际上使梳子更短)减少一些缩放量。
4. 最后一步是试验不同的间隙长度和公式，看看它如何影响算法效率。