算法导论第九章习题9.1-1
习题中要求在n+lgn-2比较次数寻找第二小元素，本代码中进过改进，在2lgn-2比较次数内完成。
//习题9.1-1//寻找第二小元素，思路是先通过两两比较，获取最小的元素，再两两比较找出第二小的元素//比较次数为2lgn-2#include<iostream>using namespace std;void FindMinAndMax(int a[],int length,int &min,int &second){int small[10];int i,j=0,s,lengths,len;//将数组进行分组，每两个元素比较，较大的放到big数组中//较小的放到small数组中for(i=0;i<length-1;i+=2){if(a[i]<a[i+1]){s=a[i];}else{s=a[i+1];}small[j++]=s;}if(length%2==1){small[j++]=a[length-1];}//获取small数组和big数组的长度lengths=len=j;//每两个元素进行比较，将较小的保留较大的去掉//知道数组中只剩一个元素，此元素即为最小元素while(lengths>1){j=0;for(i=0;i<lengths-1;i+=2){if(small[i]<small[i+1]){small[j++]=small[i];}else{small[j++]=small[i+1];}}//如果元素个数为奇数个，则最后一个元素没法进行比较，则直接放到下一轮if(lengths%2==1){small[j++]=small[lengths-1];}lengths=j;}//保留的最后一个元素即为最小的元素min=small[0];second=10000;while(length>1){j=0;for(i=0;i<length-1;i+=2){if(a[i]<a[i+1]){if(a[i]==min){if(second>=a[i+1]){second=a[i+1];}}a[j++]=a[i];}else{if(a[i+1]==min){if(second>=a[i]){second=a[i];}}a[j++]=a[i+1];}}//如果元素个数为奇数个，则最后一个元素没法进行比较，则直接放到下一轮if(length%2==1){a[j++]=a[length-1];}length=j;}}int main(){int a[10]={1,3,5,4,6,8,79,2,45,123};int min,second;FindMinAndMax(a,10,min,second);cout<<min<<endl;cout<<second<<endl;return 0;}