内容发布更新时间 : 2024/11/16 16:22:24星期一 下面是文章的全部内容请认真阅读。
常用算法经典代码（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] {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 ??? 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);