Question

一个无序数组用什么排序方法排序是最快的

Answer 1

一个数组A是有序的,一个数组B是无序的.需要按顺序排序为一个数组,我能想到的就是先将无序B的用冒泡排序,再和A用归并排序,A,B的长度都不超过100各位高手,还能提供更高效率的排序算法吗?谢谢了. 答:</FONT>B用快排吧。A和B的合并使用使用归并。 答:</FONT>考虑到数组A已经有序，可以遍历数组B中每一个元素，使用binarysearch的方法将元素插入到数组B中。这个算法的时间复杂度应该时O(N*log(N))。 答:</FONT>O(nlogn)已经是最快的了 答:</FONT>将无序数组B插入有序数组A，每次插入时，用折半查找确定插入位置。在将A与B合并为新数组C的情形下（即有辅助数组），上述算法的复杂度为：O(len(B)*log(len(A)))(len(X)表示数组X的长度)。 答:</FONT>binarysearch是logn的复杂度，但是如何完成数组的插入操作？ 答:</FONT>二分查找再插入的算法复杂度为O(len(B)*log(len(A)len(B)) 答:</FONT>在这里我们更关心的是数组B的元素个数，数组A的元素个数相对于来说可以看作是常数，所以简单的说，这个算法应该是个O(N*log(N))的算法。 答:</FONT>该回复于2007-10-0914:24:36被管理员删除 答:</FONT>该回复于2007-10-0914:24:36被管理员删除 答:</FONT>首先用快排,然后用归并就可以了 答:</FONT>MONOLINUX()算法时间是2*O(n)-----------------------------------哟这不是咱们写搜索引擎的大牛嘛连这么一个简单的问题都弄不明白?基于比较的算法是O(nlogn)给个简单的证明如果存在低于O(nlogn)的算法那么对于任何数组B,给一个已排序的A,我们可以得到一个合并A,B且已排序的数组C去掉C中所拥有的A中的元素,这一步显然可以在O(n)内完成,那么我们就得到一个已排序的B,且得到一个复杂度低于O(nlogn)的基于比较的排序算法

Answer 2

希尔排序