如果我有一个仅包含 0 和 1 的二进制值列表，如下面的 000111010110 并且我想将其排序为以下 000000111111 如果您还知道列表大小，那么执行此操作的最有效方法是什么？现在我想有一个计数器，当我从头到尾遍历列表时，我只计算 0 的数量。然后，如果我将 listSize 除以 numberOfZeros，我得到 numberOfOnes。然后我在想，不是从零开始重新排序列表，而是创建一个新列表。你同意这是最有效的方法吗？
问问题
321 次
3 回答
1
您的算法实现了经典桶排序算法（其计数排序实现）的最原始版本。当数字的范围已知并且（相对）较小时，这是对数字进行排序的最快方法。由于您只有零和一，因此您不需要存储桶排序中存在的计数器数组：单个计数器就足够了。
于 2012-10-26T16:11:35.877 回答
0
如果你有数值，你可以使用汇编指令bitscan（x86汇编中的BSF）来计算位数。要创建“排序”值，您将设置 n+1 位，然后减去 1。这会将所有位设置到 n+1 位的右侧。
于 2012-10-26T17:38:45.377 回答
0
桶排序看起来是一种排序算法。
我认为不需要这样的操作。我们知道没有比 N*logN 更快的排序算法。所以默认情况下是错误的。
所有这一切，因为你要做的就是你一开始所说的。只需遍历列表并计算零或一，这会给你 O(n) 复杂度。然后只需创建一个新数组，其中包含计数的零开头后面是一个。然后你总共有 N+N 复杂度，给你 O(n) 复杂度。
那只是因为你只有两个值。所以快速排序或任何其他排序都不能更快地做到这一点。没有比 NLog(n) 更快的排序
于 2012-10-27T03:10:42.587 回答