see my explaination

assume the length is n
如果两两比较
there will be 3*n/2 compare operation + n memory read operation

如果amei的算法
best case: there will be n compare operation + n memory read (this will happen if the array was already sorted on an asceding order)

worst case: these will be 2n compare operation + n memory read (this will happen if the array was already sorted on an des order)

the mathimatical expecation of amei's method will have 3n/2 compare + n memory read.

So they are just same!

BTW, the math expection of assignment operation # for the 2 methods are same.

所有跟帖： 

• btw, memory read means memory look up here -Jamesxu- ♂ (130 bytes) () 02/14/2008 postreply 04:55:42

• Right! The average value for the operation of Amei's is also 3n/ -戏雨飞鹰- ♀ (0 bytes) () 02/14/2008 postreply 07:51:16