C++ 常用代码

. .

一、快速排序

void qsort(int x,int y) //待排序的数据存放在a[1]..a[n]数组中 {int h=x,r=y;

int m=a[(x+y)>>1]; //取中间的那个位置的值 while(h

{while (a[h]m) r--; //比中间那个位置的值大，循环直到找一个比中间那个值小的

if(h<=r)

{int temp=a[h];//如果此时h<=r，交换a[h]和a[r] a[h]=a[r]; a[r]=temp;

h++;r--; //这两句必不可少哦 } }

if(r>x) qsort(x,r);//注意此处，尾指针跑到前半部分了 if(h

调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序

二、冒泡排序

void paopao(void) //待排序的数据存放在a[1]..a[n]数组中

{for(int i=1;i

if(a[j]

void paopao(void) //待排序的数据存放在a[1]..a[n]数组中

. . .

. .

{for(int i=1;i=1;j--) //相邻的两两比较

if(a[j]

调用：paopao()，适用于n比较小的排序 三、桶排序

void bucketsort(void)//a的取值围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化 for(int i=1;i<=n;i++)//读入n个数 {int a cin>>a;

tong[a]++;}//相应的桶号计数器加1 for(int i=1;i<=cmax;i++)

{if(tong[i]>0) //当桶中装的树大于0，说明i出现过tong[i]次，否则没出现过i while (tong[i]!=0) {tong[i]--; cout<

桶排序适用于那些待排序的关键字的值在已知围的排序。

四、合（归）并排序

void merge(int l,int m,int r)//合并[l,m]和[m+1,r]两个已经有序的区间

{ int b[101];//借助一个新的数组B，使两个有序的子区间合并成一个有序的区间，b数组的大小要注意

. . .

. .

int h,t,k;

k=0;//用于新数组B的指针

h=l;t=m+1;//让h指向第一个区间的第一个元素，t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时，把两个区间的元素抄在新数组中

{k++; //新数组指针加1

if (a[h]

while(h<=m){k++;b[k]=a[h];h++;} //如果第一个区间没有抄结束，把剩下的抄在新数组中

while(t<=r){k++;b[k]=a[t];t++;} //如果第二个区间没有抄结束，把剩下的抄在新数组中

for(int o=1;o<=k;o++)//把新数组中的元素，再抄回原来的区间，这两个连续的区间变为有序的区间。 a[l+o-1]=b[o]; }

void mergesort(int x,int y)//对区间[x,y]进行二路归并排序 {

int mid; 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);//把已经有序的前后两段进行合并 }

归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。

. . .

. .

五、二分查找

int find(int x,int y,int m) //在[x,y]区间查找关键字等于m的元素下标 { int head,tail,mid;

head=x;tail=y;mid=((x+y)/2);//取中间元素下标

if(a[mid]==m) return mid;//如果中间元素值为m返回中间元素下标mid if(head>tail) return 0;//如果x>y，查找失败，返回0

if(m>a[mid]) //如果m比中间元素大，在后半区间查找，返回后半区间查找结果 return find(mid+1,tail);

else //如果m比中间元素小，在前半区间查找，返回后前区间查找结果 return find(head,mid-1); }

六、高精度加法 #include #include using namespace std; int main() {

string str1,str2;

int a[250],b[250],len; //数组的大小决定了计算的高精度最大位数 int i;

memset(a,0,sizeof(a)); memset(b,0,sizeof(b));

cin>>str1>>str2; //输入两个字符串

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)&&(len>1)) len--; for(i=len;i>=1;i--) cout<

注意：两个数相加，结果的位数，应该比两个数的那个数多一位。

七、高精度减法 #include using namespace std;

int compare(string s1,string s2); int main() {

string str1,str2; int a[250],b[250],len; int i;

. . .