algorithm - BeechickSort 算法比快速排序更好？

Question

我们知道 Quicksort 是一种高效的排序算法，现在 here他们是这样说的:

BeechickSort (patent 5,218,700) has these characteristics:

• Sorts two to three times faster than the quicksort algorithm, depending on the list.
• Unlike quicksort algorithms, it provides stable sorting of duplicate keys.
• Whether the list is previously sorted or shuffled makes no difference.
• Uses no compares.
• Uses no swaps.
• Uses no pivot point.
• Works equally well with short or long lists.
• Is economical with memory.
• The first sorted results are available for other processes almost immediately, while the rest of the list is still being sorted.

你知道实现吗，还是要等到realese？

Answer 1

它似乎基本上是一种基数排序:也就是说，按项目的“最重要部分”(整数的前导位/数字，字符串的第一个字符)对项目进行分类，然后递归地按“次要部分”分类部分。您可以这样做，例如，设置一个数组，每个可能的最重要部分都有一个条目，然后对所有项目执行一次传递并将每个项目分配给适当的元素。

大多数版本的基数排序实际上首先处理最不重要的部分；事实证明，这使事情变得更容易。 “Beechick 排序”显然涉及首先处理最重要的部分；显然，发明者拥有或声称拥有一种新颖的方式来做到这一点，这种方式不会产生足够的开销来抵消不需要处理建立排序不需要的部分数据的优势。

您可以在 http://www.freepatentsonline.com/5218700.pdf 阅读全文如果您想确切地弄清楚这项专利据称除了简单的基数排序(这已经众所周知很久了)之外还有什么贡献，请不要介意阅读大量专利。或者，在 http://www.beechick-sort.bizhosting.com/abcsort.html 有一些解释。 .后者包括算法的简单版本的 C 代码。