有效排序

发布时间：2020-12-16 03:06:34 所属栏目：百科来源：网络整理

导读：我有一个数组的数组,几乎是但不是很好的排序,有几个值被替换(比如,100000中的50).如何最有效地排序？解决方法在数组几乎排序的假设下,您可以使用以下之一： Smoothsort Wiki甚至有一个java实现就可以了.因为你不能比O(n)快得多(因为为了甚至找出数组是否排

我有一个数组的数组,几乎是但不是很好的排序,有几个值被替换(比如,100000中的50).如何最有效地排序？

解决方法

在数组几乎排序的假设下,您可以使用以下之一：

Smoothsort

Wiki甚至有一个java实现就可以了.因为你不能比O(n)快得多(因为为了甚至找出数组是否排序需要很多时间)smoothsort是一个不错的选择.更多细节here.

The advantage of smoothsort is that it
comes closer to O(n) time if the input
is already sorted to some degree

Coctail sort

The complexity of cocktail sort in big
O notation is O(n2) for both the worst
case and the average case,but it
becomes closer to O(n) if the list is
mostly ordered before applying the
sorting algorithm,

Timsort

Java的数组实际上是在java 7中使用timsort来排序对象(sort()).时钟说明here.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!