非比较排序的定义是什么？

Question

6

我正在学习排序算法。基数排序被称为一种非比较排序，但它会比较数字并对它们进行排序。请问什么是非比较排序？

- user3785745

2

http://en.wikipedia.org/wiki/Comparison_sort - Dmitry Bychenko

1

只有在比较列表中的两个元素时才算作比较。仅仅查看一个数字的最后一位来确定将其放入哪个桶中，并不是比较两个元素。 - Kevin

我所知道的基数排序算法不会比较数字位，而是使用数字值来访问数组。 - user395760

@ Dmitry Bychenko @kevin 谢谢。Kevin的评论为我解决了困惑。 - user3785745

我投票关闭此问题，因为它是一个理论计算机科学问题，而不是编程问题/问题。 - nbro

2个回答

5

比较排序算法会比较排序中被排序的项对，每次比较的输出是二进制的（即小于或不小于）。基数排序按顺序考虑数字的各个位，并将数字根据位的值（稳定地）分组到桶中，而不是进行比较。请注意，数字不会与任何东西进行比较-它只是放在与其值相对应的桶中。

知道为什么我们关心比较/非比较排序算法很重要。如果我们使用比较排序算法，则在每次比较时，我们将大致将可能的结果集一分为二（因为输出是二进制的），因此我们可能拥有的最佳复杂度是O(log(n!)) = O(n*log(n))。这种限制对于非比较排序并不适用。

- Ivaylo Strandjev

用大 O 符号表示复杂度时，说最优复杂度是正确的吗？ - brz

在所有上限函数O(f)中，nlogn是最低的可能值，因此是正确的。 - Eduardo Sebastian

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Landys · Accepted Answer

据我理解，比较排序算法和非比较排序算法的区别不在于算法中是否存在比较，而在于它们是否使用要排序项目的内部特性。

比较排序算法通过比较项目之间的值来对项目进行排序。它可以应用于任何排序情况。最好的复杂度是O(n*log(n))，这可以通过数学证明。

非比较排序算法使用要排序值的内部特性。它只能应用于某些特定情况，并需要特定的值。最佳复杂度可能取决于情况，例如O(n)。

使用非比较排序算法可以解决的所有排序问题都可以使用比较排序算法来解决，但反之则不成立。

对于基数排序，它受益于排序项是可缩减为数字的数字。它关心的是被排序的项是什么。而比较排序算法只需要一个项目的顺序。