C++常用经典算法及其实现

常用算法经典代码（C++版）一、快速排序voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中{inth=x,r=y;intm=a[(x+y)1];//取中间的那个位置的值while(hr){while(a[h]m)h++;//比中间那个位置的值小，循环直到找一个比中间那个值大的while(a[r]m)r--;//比中间那个位置的值大，循环直到找一个比中间那个值小的if(h=r){inttemp=a[h];//如果此时h=r，交换a[h]和a[r]a[h]=a[r];a[r]=temp;h++;r--;//这两句必不可少哦}}if(rx)qsort(x,r);//注意此处，尾指针跑到前半部分了if(hy)qsort(h,y);//注意此处，头指针跑到后半部分了}调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序二、冒泡排序voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;in;i++)//控制循环（冒泡）的次数，n个数，需要n-1次冒泡for(intj=1;j=n-i;j++)//相邻的两两比较if(a[j]a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;in;i++)//控制循环（冒泡）的次数，n个数，需要n-1次冒泡for(intj=n-i;j=1;j--)//相邻的两两比较if(a[j]a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}调用：paopao()，适用于n比较小的排序三、桶排序voidbucketsort(void)//a的取值范围已知。如a=cmax。{memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i=n;i++)//读入n个数{intacina;tong[a]++;}//相应的桶号计数器加1for(inti=1;i=cmax;i++){if(tong[i]0)//当桶中装的树大于0，说明i出现过tong[i]次，否则没出现过iwhile(tong[i]!=0){tong[i]--;couti’‘;}}}桶排序适用于那些待排序的关键字的值在已知范围的排序。四、合（归）并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b数组的大小要注意inth,t,k;k=0;//用于新数组B的指针h=l;t=m+1;//让h指向第一个区间的第一个元素，t指向第二个区间的第一个元素。while((h=m)&&(t=r))//在指针h和t没有到区间尾时，把两个区间的元素抄在新数组中{k++;//新数组指针加1if(a[h]a[t]){b[k]=a[h];h++;}//抄第一个区间元素到新数组else{b[k]=a[t];t++;}//抄第二个区间元素到新数组}while(h=m){k++;b[k]=a[h];h++;}//如果第一个区间没有抄结束，把剩下的抄在新数组中while(t=r){k++;b[k]=a[t];t++;}//如果第二个区间没有抄结束，把剩下的抄在新数组中for(into=1;o=k;o++)//把新数组中的元素，再抄回原来的区间，这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{intmid;if(x=y)return;mid=(x+y)/2;//求[x,y]区间，中间的那个点mid,mid把x,y区间一分为二mergesort(x,mid);//对前一段进行二路归并mergesort(mid+1,y);//对后一段进行二路归并merge(x,mid,y);//把已经有序的前后两段进行合并}归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid;head=x;tail=y;mid=((x+y)/2);//取中间元素下标if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标midif(headtail)return0;//如果xy，查找失败，返回0if(ma[mid])//如果m比中间元素大，在后半区间查找，返回后半区间查找结果returnfind(mid+1,tail);else//如果m比中间元素小，在前半区间查找，返回后前区间查找结果returnfind(head,mid-1);}六、高精度加法#includeiostream#includecstringusingnamespacestd;intmain(){stringstr1,str2;inta[250],b[250],len;//数组的大小决定了计算的高精度最大位数inti;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cinstr1str2;//输入两个字符串a[0]=str1.length();//取得第一个字符串的长度for(i=1;i=a[0];i++)//把第一个字符串转换为整数，存放在数组a中a[i]=str1[a[0]-i]-'0';b[0]=str2.length();//取得第二个字符串长度for(i=1;i=b[0];i++)//把第二个字符串中的每一位转换为整数，存放在数组B中b[i]=str2[b[0]-i]-'0';len=(a[0]b[0]?a[0]:b[0]);//取两个字符串最大的长度for(i=1;i=len;i++)//做按位加法，同时处理进位{a[i]+=b[i];a[i+1]+=a[i]/10;a[i]%=10;}len++;//下面是去掉最高位的0，然后输出。while((a[len]==0)&&(len1))len--;for(i=len;i=1;i--)couta[i];return0;}注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。七、高精度减法#includeiostreamusingnamespacestd;intcompare(strings1,strings2);intmain(){stringstr1,str2;inta[250],b[250],len;inti;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cinstr1str2;a[0]=str1.length();for(i=1;i=a[0];i++)a[i]=str1[a[0]-i]-'0';b[0]=str2.length();for(i=1;i=b[0];i++)b[i]=str2[b[0]-i]-'0';if((compare(str1,str2))==0)//大于等于，做按位减，并处理借位。{for(i=1;i=a[0];i++){a[i]-=b[i];if(a[i]0){a[i+1]--;a[i]+=10;}}a[0]++;while((a[a[0]]==0)&&(a[0]1))a[0]--;for(i=a[0];i=1;i--)couta[i];coutendl;}else{cout'-';//小于就输出负号for(i=1;i=b[0];i++)//做按位减，大的减小的{b[i]-=a[i];if(b[i]0){b[i+1]--;b[i]+=10;}}b[0]++;while((b[b[0]]==0)&&(b[0]1))b[0]--;for(i=b[0];i=1;i--)coutb[i];coutendl;}return0;}intcompare(strings1,strings2)//比较字符串（两个数）数字的大小，大于等于返回0，小于返回1。{if(s1.length()s2.length())return0;//先比较长度，哪个字符串长，对应的那个数就大if(s1.length()s2.length())return1;for(inti=0;i=s1.length();i++)//长度相同时，就一位一位比较。{if(s1[i]s2[i])return0;if(s1[i]s2[i])return1;}return0;//如果长度相同，每一位也一样，就返回0，说明相等}做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意处理借位。八、高精度乘法#includeiostream#includecstringusingnamespacestd;intmain(){stringstr1,str2;inta[250],b[250],c[500],len;//250位以内的两个数相乘inti,j;memset(a,0,sizeof(a));memset(b,0,sizeof(b));cinstr1str2;a[0]=str1.length();for(i=1;i=a[0];i++)a[i]=str1[a[0]-i]-'0';b[0]=str2.length();for(i=1;i=b[0];i++)b[i]=str2[b[0]-i]-'0';memset(c,0,sizeof(c));for(i=1;i=a[0];i++)//做按位乘法同时处理进位，注意循环内语句的写法。for(j=1;j=b[0];j++){c[i+j-1]+=a[i]*b[j];c[i+j]+=c[i+j-1]/10;c[i+j-1]%=10;}len=a[0]+b[0]+1;//去掉最高位的0，然后输出while((c[len]==0)&&(len1))len--;//为什么此处要len1??for(i=len;i=1;i--)coutc[i];return0;}注意：两个数相乘，结果的位数应该是这两个数的位数和减1。优化：万进制#includeiostream#includecstringusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法，即10000位十进制乘法。Intmain(){stringstr1,str2;intlen;cinstr1str2;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));num1(a,str1);//把str1从最低位开始，每4位存放在数组a中num1(b,str2);//把str2从最低位开始，每4位存放在数组b中for(inti=1;i=a[0];i++)//作按位乘法并处理进位，此处是万进制进位for(intj=1;j=b[0];j++){c[i+j-1]+=a[i]*b[j];c[i+j]+=c[i+j-1]/10000;c[i+j-1]%=10000;}len=a[0]+b[0];//a[0]和b[0]存放的是每个数按4位处理的位数while((c[len]==0)&&(len1))len--;//去掉高位的0，并输出最高位coutc[len];for(inti=len-1;i=1;i--)//把剩下来的每一位还原成4位输出{if(c[i]1000)cout’0’;if