日志

乎乎所在的班级要开运动会了，班主任是教信息学的y老师，他要将n个同学们按照身高从矮到高排成一排。初始同学们杂乱无章的站成一排，y老师采用的身高排序方法是：从第一个排头同学到最后一个排尾同学，依次比较相邻两个同学的身高，如果两位同学身高排序错位（即：高个同学在矮个同学前面），就移动两个同学位置，算作高个同学和矮个同学各移动一次。通过一轮两两比较和移动，最高的同学可以到排尾。重复上述过程，依次给一排的倒数第2个，倒数第3个，......，倒数第n-1个（正数第2个），倒数第n个（正数第1个） 找到按从矮到高对应身高的同学。乎乎想知道y老师的排序方法是否好，请编程帮他实现计算所有同学的平均移动次数。

比如：3名同学，初始按照身高156 144 138站成一排。

第一轮排序：身高156的同学移动2次，身高144的同学移动1次，身高138的同学移动1次，排序后：144 138 156，第一轮移动4次。

第二轮排序：身高156的同学移动0次，身高144的同学移动1次，身高138的同学移动1次，排序后：138 144 156，第一轮移动2次。

上述两轮排序后，共移动6次，平均移动次数为：6 / 3 = 2 (次)

#include<iostream>

using namespace std;

int main()

{

int n;

scanf("%d",&n);

int h[n];

for(int i=0;i<n;i++)

{

scanf("%d",&h[i]);

}

int temp;

int sum=0;

for(int i=0;i<n-1;i++)

{

for(int j=0;j<n-i-1;j++)

{

if(h[j]>h[j+1])

{

temp=h[j+1];

h[j+1]=h[j];

h[j]=temp;

sum=sum+2;

}

}

}

double a=(double)sum/n;

printf("%.1lf",a);

}

#include <iostream>：从 C++ 标准库中引入<iostream>头文件，用于提供输入输出功能。