Question

用基于比较的排序对6个数字排序,最坏情况下最少比较的次数是多少?

用基于比较的排序对6个数字排序，最坏情况下最少比较的次数是多少？
我知道是要不少于10次
并且构造出11次的方法

所以答案是10或者11但是我不知道

请问怎么比较可以在10次就比较出来
或者怎么证明10次不行？

Answer 1

将6个数的排列结果看成是一个六位数的大小比较，共有6！=720个六位数，一次比较可拆半，2^9=512小于720,2^10=1024大于720，所以最少10次。

Answer 2

可以用C语言里面的冒泡排序来证明啊!
下面是用冒泡法对6个元素进行升序排列.
你可以输入6个从大到小排列的的数.
最后运行显示出来的结果就是最坏的情况所需要的次数.
#include <stdio.h>
#define N 6
mian()
{
int i,j,t,a[N],k=0;

for(i=0;i<N;i++)
scanf("%d",&a[i]);

for ( i=0;i<N-1;i++)
{ for(j=N-1;j>i;j++)
if (a[j-1]>a[j])
{ t=a[j-1];
a[j-1]=a[j];
a[j]=t;
}
k++;
}

printf("%d",k);
}