sorting - 我需要对不是 Merge、Quicksort 或 heapsort 的项目进行快速排序

Question

对于上面未列出的种类，我一直在寻找一个小时左右的时间。我在其他地方问过，但人们只是以最慢的速度回应。请帮忙。它必须不低于 O(n log n)。

谢谢

标签： sortingbig-o

Answer 1

选择最快的算法对数据进行排序实际上取决于被排序的数据。

您可以使用计数排序，它需要O(N + R); 其中R是值的范围。因此，元素的范围越大，时间就越长。

或快速排序：对数据数组进行排序的最快方法是仅扫描数据，这将为您N提供第一个元素的N - 1选择，第二个元素的选择等等，直到最后一个元素只有1选择。这最终形成了一个排序算法，可以在O(N!). N!可以近似为2^(N * log N); 因此快速排序在O(N * log N).

不存在比 排序更快的排序算法O(N * log N)。

更快排序的一个技巧是使用无限数量的处理器，这可以降低时间复杂度，0(log N)但对于大型N，您可以看到这不切实际。

或者可以使用log N并行工作的处理器将时间复杂度提高到O(N). 但同样，并行处理更像是一种技巧。算法本身没有压缩到O(N).