修复这个错误的宾果排序实现
Fixing this faulty Bingo Sort implementation
在学习选择排序时，我遇到了一种称为宾果排序的变体。根据这个字典条目 here，Bingo Sort 是：
A variant of selection sort that orders items by first finding the least value, then repeatedly moving all items with that value to their final location and find the least value for the next pass.
根据上面的定义，我在Python中想出了如下实现：
def bingo_sort(array, ascending=True):
from operator import lt, gt
def comp(x, y, func):
return func(x, y)
i = 0
while i < len(array):
min_value = array[i]
j = i + 1
for k in range(i + 1, len(array), 1):
if comp(array[k], min_value, (lt if ascending else gt)):
min_value = array[k]
array[i], array[k] = array[k], array[i]
elif array[k] == min_value:
array[j], array[k] = array[k], array[j]
j += 1
i = j
return array
我知道这个实现是有问题的。当我 运行 在一个极小的数组上使用算法时，我得到了一个正确排序的数组。但是，运行 将算法与更大的数组结合使用会导致数组大部分排序时到处都是不正确的位置。要复制 Python 中的问题，算法可以是 运行 以下输入：
test_data = [[randint(0, 101) for i in range(0, 101)],
[uniform(0, 101) for i in range(0, 101)],
["a", "aa", "aaaaaa", "aa", "aaa"],
[5, 5.6],
[3, 2, 4, 1, 5, 6, 7, 8, 9]]
for dataset in test_data:
print(dataset)
print(bingo_sort(dataset, ascending=True, mutation=True))
print("\n")
我这辈子都想不出问题出在哪里，因为我看这个算法太久了，而且我并不真正精通这些东西。除了 2020 年 an undergraduate graduation project written 之外，我找不到在线宾果排序的实现。非常感谢任何可以为我指明正确方向的帮助。
我认为你的主要问题是你试图在你的第一个条件语句中设置 min_value 然后根据你刚刚在第二个条件语句中设置的相同 min_value 进行交换陈述。这些过程应该是交错的：宾果排序的工作方式是你在一次迭代中找到 min_value，在下一次迭代中你将那个 min_value 的所有实例交换到前面，同时找到next min_value 用于下一次迭代。这样，min_value 应该只在每次迭代结束时更改，而不是在迭代期间更改。当您在给定的迭代过程中更改要交换到前面的值时，您最终可能会无意中稍微打乱一些东西。
如果你想参考一些东西，我在下面有一个实现，有一些注意事项：因为你允许自定义比较器，我将 min_value 重命名为 swap_value 因为我们'我们并不总是抓住最小值，我修改了比较器 defined/passed 到函数中的方式，使算法更加灵活。另外，你真的不需要三个索引（我认为这里甚至有几个错误），所以我将 i 和 j 折叠成 swap_idx，并将 k 重命名为 cur_idx。最后，由于交换给定的 swap_val 和查找下一个_swap_val 的方式是交错的，因此您需要预先找到初始的 swap_val。我为此使用了一个 reduce 语句，但你可以在整个数组上使用另一个循环；他们是等价的。这是代码：
from operator import lt, gt
from functools import reduce
def bingo_sort(array, comp=lt):
if len(array) <= 1:
return array
# get the initial swap value as determined by comp
swap_val = reduce(lambda val, cur: cur if comp(cur, val) else val, array)
swap_idx = 0 # set the inital swap_idx to 0
while swap_idx < len(array):
cur_idx = swap_idx
next_swap_val = array[cur_idx]
while cur_idx < len(array):
if comp(array[cur_idx], next_swap_val): # find next swap value
next_swap_val = array[cur_idx]
if array[cur_idx] == swap_val: # swap swap_vals to front of the array
array[swap_idx], array[cur_idx] = array[cur_idx], array[swap_idx]
swap_idx += 1
cur_idx += 1
swap_val = next_swap_val
return array
一般来说，此算法的复杂性取决于处理了多少重复值以及处理它们的时间。这是因为在给定迭代期间每次处理 k 个重复值时，对于所有后续迭代，内循环的长度都会减少 k。因此，当早期处理大量重复值时（例如当数组的最小值包含许多重复项时），性能会得到优化。由此，基本上有两种方法可以分析算法的复杂性：您可以根据重复值在最终排序数组（类型 1）中出现的位置进行分析，或者您可以假设重复值的簇随机分布在排序数组中，并根据重复簇的平均大小（即，根据 m 相对于 n 的大小：类型 2）分析复杂性。
您链接的定义使用第一种类型的分析（基于重复项往往出现的位置）得出最佳 = Theta(n+m^2)、平均值 = Theta(nm)、最差 = Theta(nm) .第二种类型的分析会产生最佳 = Theta(n)、平均 = Theta(nm)、最差 = Theta(n^2)，因为您将 m 从 Theta(1) 更改为 Theta(m) 再到 Theta(n)。
在类型 1 的最佳情况下，所有重复项都将在数组的最小元素中，这样内循环的 运行 时间迅速减少到 O(m)，最后的迭代该算法作为 O(m^2) select 离子排序进行。但是，仍然有预先 O(n) 传递给 select 初始交换值，因此整体复杂度为 O(n + m^2).
在最坏的类型 1 情况下，所有重复项都将位于数组的最大元素中。直到算法的最后一次迭代，内部循环的长度才显着缩短，这样我们就实现了 运行 次看起来像 n + n-1 + n-2 .... + n-m。这是 m 个 O(n) 值的总和，总计 O(nm) 运行 时间。
在一般的第 1 类情况（以及所有第 2 类情况）中，我们不假设重复值的簇偏向排序数组的前面或后面。我们认为 m 个重复值簇根据它们的位置和大小随机分布在数组中。在此分析下，我们预计在最初的 O(n) 遍找到第一个交换值后，外循环的每 m 次迭代都会将内循环的长度减少大约 n/m。这导致未知 m 和随机分布数据的总体 运行 时间的表达式为：
我们可以将此表达式用于具有随机分布数据和未知 m，Theta(nm) 的平均情况 运行-时间，作为平均类型 2 运行-时间，并且它也根据我们如何改变 n 的大小，直接给我们最好和最坏的情况 运行 次。
在最好的类型 2 情况下，m 可能只是一些独立于 n 的常数值。如果我们有 m=Theta(1) 个随机分布的重复簇，那么最佳情况 运行 时间是 Theta(n*Theta(1))) = Theta(n)。例如，您会看到宾果排序的 O(2n) = O(n) 性能只有一个唯一值（一次通过查找查找值，一次通过将每个单个值交换到前面），并且这个 O( n) 如果 m 受任何常数限制，则渐近复杂度仍然成立。
然而，在最坏的类型 2 情况下，我们可能有 m=Theta(n)，宾果排序本质上退化为 O(n^2) select离子排序。这显然是 m = n 的情况，但是如果内循环的 运行 时间预计在每次迭代中减少的数量 n/m 是任何常数值，对于Theta(n) 中的任何 m 值，我们仍然看到 O(n^2) 复杂度。
在学习选择排序时，我遇到了一种称为宾果排序的变体。根据这个字典条目 here，Bingo Sort 是：
A variant of selection sort that orders items by first finding the least value, then repeatedly moving all items with that value to their final location and find the least value for the next pass.
根据上面的定义，我在Python中想出了如下实现：
def bingo_sort(array, ascending=True):
from operator import lt, gt
def comp(x, y, func):
return func(x, y)
i = 0
while i < len(array):
min_value = array[i]
j = i + 1
for k in range(i + 1, len(array), 1):
if comp(array[k], min_value, (lt if ascending else gt)):
min_value = array[k]
array[i], array[k] = array[k], array[i]
elif array[k] == min_value:
array[j], array[k] = array[k], array[j]
j += 1
i = j
return array
我知道这个实现是有问题的。当我 运行 在一个极小的数组上使用算法时，我得到了一个正确排序的数组。但是，运行 将算法与更大的数组结合使用会导致数组大部分排序时到处都是不正确的位置。要复制 Python 中的问题，算法可以是 运行 以下输入：
test_data = [[randint(0, 101) for i in range(0, 101)],
[uniform(0, 101) for i in range(0, 101)],
["a", "aa", "aaaaaa", "aa", "aaa"],
[5, 5.6],
[3, 2, 4, 1, 5, 6, 7, 8, 9]]
for dataset in test_data:
print(dataset)
print(bingo_sort(dataset, ascending=True, mutation=True))
print("\n")
我这辈子都想不出问题出在哪里，因为我看这个算法太久了，而且我并不真正精通这些东西。除了 2020 年 an undergraduate graduation project written 之外，我找不到在线宾果排序的实现。非常感谢任何可以为我指明正确方向的帮助。
我认为你的主要问题是你试图在你的第一个条件语句中设置 min_value 然后根据你刚刚在第二个条件语句中设置的相同 min_value 进行交换陈述。这些过程应该是交错的：宾果排序的工作方式是你在一次迭代中找到 min_value，在下一次迭代中你将那个 min_value 的所有实例交换到前面，同时找到next min_value 用于下一次迭代。这样，min_value 应该只在每次迭代结束时更改，而不是在迭代期间更改。当您在给定的迭代过程中更改要交换到前面的值时，您最终可能会无意中稍微打乱一些东西。
如果你想参考一些东西，我在下面有一个实现，有一些注意事项：因为你允许自定义比较器，我将 min_value 重命名为 swap_value 因为我们'我们并不总是抓住最小值，我修改了比较器 defined/passed 到函数中的方式，使算法更加灵活。另外，你真的不需要三个索引（我认为这里甚至有几个错误），所以我将 i 和 j 折叠成 swap_idx，并将 k 重命名为 cur_idx。最后，由于交换给定的 swap_val 和查找下一个_swap_val 的方式是交错的，因此您需要预先找到初始的 swap_val。我为此使用了一个 reduce 语句，但你可以在整个数组上使用另一个循环；他们是等价的。这是代码：
from operator import lt, gt
from functools import reduce
def bingo_sort(array, comp=lt):
if len(array) <= 1:
return array
# get the initial swap value as determined by comp
swap_val = reduce(lambda val, cur: cur if comp(cur, val) else val, array)
swap_idx = 0 # set the inital swap_idx to 0
while swap_idx < len(array):
cur_idx = swap_idx
next_swap_val = array[cur_idx]
while cur_idx < len(array):
if comp(array[cur_idx], next_swap_val): # find next swap value
next_swap_val = array[cur_idx]
if array[cur_idx] == swap_val: # swap swap_vals to front of the array
array[swap_idx], array[cur_idx] = array[cur_idx], array[swap_idx]
swap_idx += 1
cur_idx += 1
swap_val = next_swap_val
return array
一般来说，此算法的复杂性取决于处理了多少重复值以及处理它们的时间。这是因为在给定迭代期间每次处理 k 个重复值时，对于所有后续迭代，内循环的长度都会减少 k。因此，当早期处理大量重复值时（例如当数组的最小值包含许多重复项时），性能会得到优化。由此，基本上有两种方法可以分析算法的复杂性：您可以根据重复值在最终排序数组（类型 1）中出现的位置进行分析，或者您可以假设重复值的簇随机分布在排序数组中，并根据重复簇的平均大小（即，根据 m 相对于 n 的大小：类型 2）分析复杂性。
您链接的定义使用第一种类型的分析（基于重复项往往出现的位置）得出最佳 = Theta(n+m^2)、平均值 = Theta(nm)、最差 = Theta(nm) .第二种类型的分析会产生最佳 = Theta(n)、平均 = Theta(nm)、最差 = Theta(n^2)，因为您将 m 从 Theta(1) 更改为 Theta(m) 再到 Theta(n)。
在类型 1 的最佳情况下，所有重复项都将在数组的最小元素中，这样内循环的 运行 时间迅速减少到 O(m)，最后的迭代该算法作为 O(m^2) select 离子排序进行。但是，仍然有预先 O(n) 传递给 select 初始交换值，因此整体复杂度为 O(n + m^2).
在最坏的类型 1 情况下，所有重复项都将位于数组的最大元素中。直到算法的最后一次迭代，内部循环的长度才显着缩短，这样我们就实现了 运行 次看起来像 n + n-1 + n-2 .... + n-m。这是 m 个 O(n) 值的总和，总计 O(nm) 运行 时间。
在一般的第 1 类情况（以及所有第 2 类情况）中，我们不假设重复值的簇偏向排序数组的前面或后面。我们认为 m 个重复值簇根据它们的位置和大小随机分布在数组中。在此分析下，我们预计在最初的 O(n) 遍找到第一个交换值后，外循环的每 m 次迭代都会将内循环的长度减少大约 n/m。这导致未知 m 和随机分布数据的总体 运行 时间的表达式为：
我们可以将此表达式用于具有随机分布数据和未知 m，Theta(nm) 的平均情况 运行-时间，作为平均类型 2 运行-时间，并且它也根据我们如何改变 n 的大小，直接给我们最好和最坏的情况 运行 次。
在最好的类型 2 情况下，m 可能只是一些独立于 n 的常数值。如果我们有 m=Theta(1) 个随机分布的重复簇，那么最佳情况 运行 时间是 Theta(n*Theta(1))) = Theta(n)。例如，您会看到宾果排序的 O(2n) = O(n) 性能只有一个唯一值（一次通过查找查找值，一次通过将每个单个值交换到前面），并且这个 O( n) 如果 m 受任何常数限制，则渐近复杂度仍然成立。
然而，在最坏的类型 2 情况下，我们可能有 m=Theta(n)，宾果排序本质上退化为 O(n^2) select离子排序。这显然是 m = n 的情况，但是如果内循环的 运行 时间预计在每次迭代中减少的数量 n/m 是任何常数值，对于Theta(n) 中的任何 m 值，我们仍然看到 O(n^2) 复杂度。