题目要求

编写一个实验程序，随机产生10个1~20的整数，设计一个高效算法找其中的最大元素和最小元素，并统计元素之间的比较次数。 调用该算法执行十次并求元素的平均比较次数。

题目分析

1. 开辟一个大小为11的数组，然后利用rand()函数生成随机数存入数组，从1号地址空间开始存，0号地址单元做检查哨。
2. 可以利用if…else…结构只比较次数，而不排序，我是用来排序算法，将数组进行升序排序，即可得到最大元素和最小元素，并设置计数变量统计比较次数。

排序方式很多种，对于小量数据来说希尔排序最快，但是比较次数很多 ，而且属于不稳定。
也可以使用经典的冒泡排序，稳定，但速度下降很多。 因为题目请求效率，所以我使用了希尔排序。
排序算法很多，这里只是把速度快的和常用的两种实现了。

3. 循环十次，将每次排序的比较次数进行求和，再求每次的平均比较次数。

功能代码（C++）

#include <iostream>
#include <stdlib.h>
#define MAXS 11			//定义数组大小为11，0号地址单元做检查哨 
using namespace std;
/*
题目：统计求最大、最小元素的平均比较次数 。
要求：编写一个实验程序，随机产生10个1~20的整数，设计一个高效算法找其中的最大元素和最小元素，并统计元素之间的比较次数。 
	  调用该算法执行十次并求元素的平均比较次数。
	  
解题思路：
	1. 开辟一个大小为11的数组，然后利用rand()函数生成随机数存入数组，从1号地址空间开始存，0号地址单元做检查哨。
	2. 利用排序算法，将数组进行升序排序，即可得到最大元素和最小元素，并设置计数变量统计比较次数。
	   排序方式很多种，对于小量数据来说希尔排序最快，但是比较次数很多 ，而且属于不稳定。
	   也可以使用经典的冒泡排序，稳定，但速度下降很多。 
	   因为题目请求效率，所以我使用了希尔排序。 
	3. 循环十次，将每次排序的比较次数进行求和，再求每次的平均比较次数。 
*/ 

//1. 向数组中填充随机数 
void RandArray(int array[],int n){
	for(int i = 1; i<n; i++){
		array[i] = rand()%20+1;		//生成1~20以内的随机数，并填充到array数组中 
	}
} 

//2. 希尔排序，比较的次数多 (方法一),此类排序方法不稳定，但速度快 
void ShellSort(int array[], int n,int &num){	//传入数组和数组大小，以用于记录比较次数的num 
	int increment = n,MAX,MIN,i,j;			//定义increment为增量计量，定义MAX和MIN来记录最大数和最小数,循环计数变量i和j。 
	num=0;		//将num赋0用于计数 
	do{
		increment = increment/3+1;				//增量序列
		for (i = increment+1; i<=n; i++){	 
			if (array[i]<array[i-increment]){ 	//将array[i]插入增量数组 
				array[0] = array[i];			//array[i]暂存入array[0] 
				num++;							//进行了一次比较，num加一 
				for (j = i-increment; j>0 && array[0]<array[j]; j-=increment){  
					array[j+increment] = array[j];		//寻找插入位置 
					num++;
				} 
				array[j+increment] = array[0];	//插入交换的位置 
			}
		}
	}while (increment>1);						//循环体为一次增量为increment的插入排序，没有循环增量则结束循环 
	/*	 	
	for (int k = 1; k<n; k++){					//测试阶段，查看最大、最小元素是否正确 
		cout << array[k] << endl;
	}	
	*/
	MIN = array[1]; 
	MAX = array[n-1];
	cout << "最小值为：" << MIN << endl; 
	cout << "最大值为：" << MAX << endl;
	cout << "希尔排序比较次数为：" << num << endl;
}

//2.冒泡排序（方法二）速度慢，但是稳定 
void BubbleSort(int array[], int n,int &num){
	int MAX,MIN,i,j; 
	num=0;									//次数控制变量i和j 
	for (i = 1; i<n-1; i++) { 				//控制n-2即数据总量-1次的趟比较
		for (j = 1; j<n-1-i; j++){
			num++;
			if (array[j]>array[j+1]) { 		//比较相邻的两个元素	
				array[0] = array[j]; 			//交换
				array[j] = array[j+1];
				array[j+1] = array[0]; 
			} 
		}
	}
	/*
	for (int k = 1; k < n; k++){				//测试阶段，查看最大、最小元素是否正确 
		cout << array[k] << endl;
	}
	*/
	MIN = array[1]; 
	MAX = array[n-1];
	cout << "最小值为：" << MIN << endl; 
	cout << "最大值为：" << MAX << endl;
	cout << "冒泡排序比较次数为：" << num << endl;
}
//3.main函数
int main(){
	int nums,numb,num;				//nums是希尔排序平均比较次数，numb是冒泡排序平均比较次数，num是用于过程比较次数 
	int array[MAXS];
	for(int v = 1; v<=10; v++){
		cout << "第" << v << "组：" << endl;
		RandArray(array,MAXS);
		ShellSort(array,MAXS,num);
		nums += num;
		cout << endl; 
		BubbleSort(array,MAXS,num);
		numb += num;
		cout << endl; 
		cout << endl; 
		cout << endl; 
	}
	cout << "希尔排序的平均比较次数为：" << (1.0*nums/10) << endl;
	cout << "冒泡排序的平均比较次数为：" << (1.0*numb/10) << endl;
	return 0;
}