在一个有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; }