Question

算法设计与分析的题目求解

考虑下面的算法：
输入：n个元素的组数A
输出：按递增顺序排序的数组A
void sort (int A[ ],int n)
{
int i, j, temp;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(A[j]<A[i]){
temp=A[i];
A[i]=A[j];
A[j]=temp;
}
}
(1)什么时候算法所执行的元素赋值的次数最少？最少多少次？
（2）什么时候算法所执行的元素赋值的次数最多？最多多少次？

Answer 1

冒泡~

1. 所有元素都是排好的，一次赋值都木有
   

2. 所有元素都是递减的，每次都赋值，(1+n-1)*(n-1)/2次
   

追问

大神 求过程 再追你10分 考试用 没过程 没分啊

追答

1. 赋值次数最少-->
   if(A[j]<A[i])没有一次满足-->a[j]>=a[i]永真-->后面的元素都要大于或等于前面的元素

2. 赋值次数最多-->
   if(A[j]<A[i])每一次满足-->a[j]<[i]永真-->后面的元素都要小于前面的元素，次数为子循环次数，然后
   后面就是高中数学的东西了，子循环次数公式给你了~
   

追问

大神 我基础差不会 第2问求再给算下吧 我再给10分 真的急需

追答

第一次外循环i=0,内循环 j=1~n-1，循环n-1次，
第二次外循环i=1,内循环j=2~n-1，循环n-2次
......
以此类推，最后一次，外循环i=n-2，内循环j=n-1，循环1次
总的循环次数 ，1+2+3+....+n-1 = (1+n-1)*(n-1)/2
然后赋值次数，貌似是3*循环次数=(1+n-1)*(n-1)/2*3

第一次外循环i=0,内循环 j=1~n-1，循环n-1次，
第二次外循环i=1,内循环j=2~n-1，循环n-2次
......
以此类推，最后一次，外循环i=n-2，内循环j=n-1，循环1次
总的循环次数 ，1+2+3+....+n-1 = (1+n-1)*(n-1)/2
然后赋值次数，貌似是3*循环次数=(1+n-1)*(n-1)/2*3

Answer 2

上面那个完全是照搬别人的嘛，问题也都不一样的。关键点在于子规模与合并这间的关系

Answer 3