3 algorithm definition data-structures
我正在进行排序算法.基数排序表示为非比较排序,但它比较数字中的数字并对它们进行排序.可以有人请让我知道非比较排序实际意味着什么？
比较排序算法比较被排序的项目对，并且每次比较的输出是二进制的（即smaller than或not smaller than）。基数排序按顺序考虑数字的数字，而不是比较它们，而是根据数字的值（以稳定的方式）将数字分组到桶中。请注意，该数字不会与任何内容进行比较 - 它只是放入与其值对应的存储桶中。
重要的是要知道我们为什么关心比较/非比较排序算法。如果我们使用比较排序算法，那么在每次比较时，我们会将可能的结果集大致分成两半（因为输出是二进制的），因此我们可能拥有的最佳复杂度是O(log(n!)) = O(n*log(n))。此限制不适用于非比较排序。
据我所知,比较和非比较排序算法之间的区别不在于算法中是否存在比较,而在于它们是否使用要排序的项的内部字符.
比较排序算法通过比较彼此之间的值来对项目进行排序.它可以应用于任何排序情况.最好的复杂性O(n*log(n))可以用数学方法证明.
非比较排序算法使用值的内部字符进行排序.它只能应用于某些特定情况,并且需要特定值.根据案例,最好的复杂性可能更好,例如O(n).
可以使用非比较排序算法排序的所有排序问题可以使用比较排序算法排序,但反之亦然.
对于基数排序,它受益于已排序的项目是可以减少为数字的数字.它关心的是排序的项目.而比较排序算法只需要一个项目的顺序.