排序问题

liota

见太久没更新就发个吧.问题描述很简单.
N个不相同的整数,求最坏情况时最少经过多少次比较后使其有序.
------------------------------------------------------

重新描述下题目,N个不同的数,设计出正确的排序方案,并计算出其的比较次数.求尽可能少的比较次数.
现在找到了最少比较的方法,但并未找到严谨的证明,则只需提供排序方案及比较次数即可.

畅想幻想

最少经过 n-1 次比较,而最坏情况时: N(N-1)/2

预言者

最坏时经过n(n-1)/2次,每一个数都与N-1个数比较所以经过n(n-1)次每个都算了两次,所以应该除以2,
解毕

liota

注意验证一下自己的猜想额..建议找几个数做下试验.最好是先得出方法,再推导比较次数.

预言者

N与其他N-1的数一一比较,N-1与除N,N-1以外的N-2个数比较......所以需要N-1+N-2+N-3+......+1,即(N-1+1)*N/2,不知对于否

liota

似乎你的计算有问题...这个应该是(N-1)项,那么和其他人的公式一样,(n-1)n/2.
那我现在举个例子吧,
比如说5个无法直接看出大小的数,元素编号A,B,C,D,E.
AB比较得到有序数组1{A,B}(不妨设A<B),须一次比较.
同理得{D,E}有序数组,须一次,将F元素插入该数组,毫无疑问,至少需要两次比较.得数组2{D,E,F}且设D<E<F
得有序数组{A,B}与{D,E,F},已比较4次.
现在把数组1插入数组2.
A与E先比较,
若A>E,则A与F比较,
          若F<A,则得有序数组{D,E,F,A,B},累计所有比较次数,共 6 次.
          若F>A,则B与F比较,得有序数组{D,E,A,F,B}或{D,E,A,B,F},须 7 次比较.
同理得A<E的情况.
最终得到结论,5个数可以用7次比较得到有序的序列.
但大家从提供的公式来看5*(5-1)/2=10≠7,
说明诸位的理想排序方案还是可以优化的.

[ 本帖最后由 liota 于 2008-11-1 18:55 编辑 ]

liota

实际上,在比较当中,通常是以二分来得到答案的,那样可以将时间复杂度优化很多.
以2分查找为例,假设有n个有序的数,那么我们可以先找最中间那个比较大小后,在依次往左右递归,
最坏情况就是比较了   [log₂(n)]+1   次,比按顺序一个一个数试的比较次数快很多.

本题答案:
令S为最终比较次数.
2^S-1<N!<2^S
S-1<log₂(N!)<S
S=[log₂(N!)]+1

(注:以上中括号为取整,N>2.)

[ 本帖最后由 liota 于 2008-11-2 08:58 编辑 ]