假设数组几乎已排序,您可以使用以下之一:
Wiki甚至还有一个java实现.因为你不能比O(n)更快(因为它需要花费很多时间才能找出数组是否排序)smoothsort是一个不错的选择.更多细节在这里.
smoothsort的优点是,如果输入已经在某种程度上排序,它会更接近O(n)时间
对于最坏情况和平均情况,大O符号中鸡尾酒排序的复杂性是O(n2),但如果列表在应用排序算法之前大部分是有序的,则它变得更接近O(n),
Java的数组实际上现在在java 7中使用timsort来排序对象(sort()).timsort的描述在这里.