常用算法经典代码C++.docxVIP

常用算法经典代码（C++版）一、快速排序void qsort(int x,int y) //待排序的数据存放在a[1]..a[n]数组中 {int h=x,r=y; int m=a[(x+y)1]; //取中间的那个位置的值 while(hr){while (a[h]m) h++; //比中间那个位置的值小，循环直到找一个比中间那个值大的 while (a[r]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(rx) qsort(x,r);//注意此处，尾指针跑到前半部分了?if(hy) qsort(h,y); //注意此处，头指针跑到后半部分了}调用：qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序?二、冒泡排序void paopao(void) //待排序的数据存放在a[1]..a[n]数组中{for(int i=1;in;i++)? //控制循环（冒泡）的次数，n个数，需要n-1次冒泡 for(int j=1;j=n-i;j++) //相邻的两两比较 if(a[j]a[j+1]) {int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}或者void paopao(void) //待排序的数据存放在a[1]..a[n]数组中{for(int i=1;in;i++)? //控制循环（冒泡）的次数，n个数，需要n-1次冒泡 for(int j=n-i;j=1;j--) //相邻的两两比较 if(a[j]a[j+1]) {int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}?调用：paopao()，适用于n比较小的排序?三、桶排序void bucketsort(void)//a的取值范围已知。如a=cmax。?{memset(tong,0,sizeof(tong));//桶初始化for(int i=1;i=n;i++)//读入n个数 {int acina;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]--;couti’ ‘;}}}?桶排序适用于那些待排序的关键字的值在已知范围的排序。?四、合（归）并排序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]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(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);//取中间元素下