【算法导论】与此同时找出最大值和最小值

【算法导论】同时找出最大值和最小值

在一个有n个元素的集合中，需要多少次比较才能确定其最小、最大元素呢？如果一个一个的比较，那么需要n-1次比较，是不是有更好的方法呢？

如果，在比较中，记录遇到的最大值和最小值。将输入的元素两两比较，然后与当前的最大值、最小值进行比较。这样每2个元素需要3次比较，而不是原来的4次。

实现代码如下：

void MiniNum(){const int size = 100000;int * array_list = new int [sizeof(int)*size];int max = 66666;/*人工加入的最大值*/int min = -90;/*人工加入的最小值*/int tmp_max = 0;/*临时的最大值*/int tmp_min = 0;/*临时的最小值*/srand(0);for(int i=0;i<size;i++){/*随机的填充数组元素*/int ran_num=rand()% size;if(i == size/2){array_list[i] = min;}else if(i == size/3){array_list[i] = max;}else{array_list[i] = ran_num;}}/*取得临时的最小值和最大值*/if(size % 2 == 0){if(array_list[0] > array_list[1]){tmp_max = array_list[0];tmp_min = array_list[1];}else{tmp_max = array_list[1];tmp_min = array_list[0];}}else{tmp_max = array_list[0];tmp_min = array_list[0];}for(int i=0;i<size -1;i+=2){/*采用两两进行比较*/int min_tmp ;int max_tmp;if(array_list[i] >= array_list[i+1]){min_tmp = array_list[i+1];max_tmp= array_list[i];}else{min_tmp = array_list[i];max_tmp= array_list[i+1];}if(max_tmp > tmp_max){tmp_max = max_tmp;}if(min_tmp < tmp_min){tmp_min = min_tmp;}}std::cout<<tmp_max<<std::endl;std::cout<<tmp_min<<std::endl;/*for(int i=0;i<size;i++){std::cout<<array_list[i]<<"\t";}*/delete array_list;}