c常用經(jīng)典算法及其實(shí)現(xiàn)(已修改)
2025-07-07 06:22 本頁(yè)面
【正文】 常用算法經(jīng)典代碼（C++版）一、快速排序void qsort(int x,int y) //待排序的數(shù)據(jù)存放在a[1]..a[n]數(shù)組中 {int h=x,r=y。 int m=a[(x+y)1]。 //取中間的那個(gè)位置的值 while(hr){while (a[h]m) h++。 //比中間那個(gè)位置的值小，循環(huán)直到找一個(gè)比中間那個(gè)值大的 while (a[r]m) r。 //比中間那個(gè)位置的值大，循環(huán)直到找一個(gè)比中間那個(gè)值小的 if(h=r){int temp=a[h]。//如果此時(shí)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)。 //注意此處，頭指針跑到后半部分了}調(diào)用：qsort(1,n)即可實(shí)現(xiàn)數(shù)組a中元素有序。適用于n比較大的排序二、冒泡排序void paopao(void) //待排序的數(shù)據(jù)存放在a[1]..a[n]數(shù)組中{for(int i=1。in。i++) //控制循環(huán)（冒泡）的次數(shù)，n個(gè)數(shù)，需要n1次冒泡 for(int j=1。j=ni。j++) //相鄰的兩兩比較 if(a[j]a[j+1]) {int temp=a[j]。a[j]=a[j+1]。a[j+1]=temp。}}或者void paopao(void) //待排序的數(shù)據(jù)存放在a[1]..a[n]數(shù)組中{for(int i=1。in。i++) //控制循環(huán)（冒泡）的次數(shù)，n個(gè)數(shù)，需要n1次冒泡 for(int j=ni。j=1。j) //相鄰的兩兩比較 if(a[j]a[j+1]) {int temp=a[j]。a[j]=a[j+1]。a[j+1]=temp。}}調(diào)用：paopao()，適用于n比較小的排序三、桶排序void bucketsort(void)//a的取值范圍已知。如a=cmax。{memset(tong,0,sizeof(tong))。//桶初始化for(int i=1。i=n。i++)//讀入n個(gè)數(shù) {int acina。tong[a]++。}//相應(yīng)的桶號(hào)計(jì)數(shù)器加1 for(int i=1。i=cmax。i++) {if(tong[i]0) //當(dāng)桶中裝的樹(shù)大于0，說(shuō)明i出現(xiàn)過(guò)tong[i]次，否則沒(méi)出現(xiàn)過(guò)i while (tong[i]!=0) {tong[i]。couti’ ‘。}}}桶排序適用于那些待排序的關(guān)鍵字的值在已知范圍的排序。四、合（歸）并排序void merge(int l,int m,int r)//合并[l,m]和[m+1,r]兩個(gè)已經(jīng)有序的區(qū)間{ int b[101]。//借助一個(gè)新的數(shù)組B，使兩個(gè)有序的子區(qū)間合并成一個(gè)有序的區(qū)間，b數(shù)組的大小要注意 int h,t,k。 k=0。//用于新數(shù)組B的指針 h=l。t=m+1。//讓h指向第一個(gè)區(qū)間的第一個(gè)元素，t指向第二個(gè)區(qū)間的第一個(gè)元素。 while((h=m)amp。amp。(t=r))//在指針h和t沒(méi)有到區(qū)間尾時(shí)，把兩個(gè)區(qū)間的元素抄在新數(shù)組中 {k++。 //新數(shù)組指針加1 if (a[h]a[t]){b[k]=a[h]。h++。} //抄第一個(gè)區(qū)間元素到新數(shù)組 else{b[k]=a[t]。t++。} //抄第二個(gè)區(qū)間元素到新數(shù)組 } while(h=m){k++。b[k]=a[h]。h++。} //如果第一個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中 while(t=r){k++。b[k]=a[t]。t++。} //如果第二個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中 for(int o=1。o=k。o++)//把新數(shù)組中的元素，再抄回原來(lái)的區(qū)間，這兩個(gè)連續(xù)的區(qū)間變?yōu)橛行虻膮^(qū)間。a[l+o1]=b[o]。}void mergesort(int x,int y)//對(duì)區(qū)間[x,y]進(jìn)行二路歸并排序{ int mid。 if(x=y) return。 mid=(x+y)/2。//求[x,y]區(qū)間，中間的那個(gè)點(diǎn)mid,mid把x,y區(qū)間一分為二 mergesort(x,mid)。//對(duì)前一段進(jìn)行二路歸并 mergesort(mid+1,y)。//對(duì)后一段進(jìn)行二路歸并 merge(x,mid,y)。//把已經(jīng)有序的前后兩段進(jìn)行合并}歸并排序應(yīng)用了分治思想，把一個(gè)大問(wèn)題，變成兩個(gè)小問(wèn)題。二分是分治的思想。五、二分查找int find(int x,int y,int m) //在[x,y]區(qū)間查找關(guān)鍵字等于m的元素下標(biāo){ int head,tail,mid。 head=x。tail=y。mid=((x+y)/2)。//取中間元素下標(biāo) if(a[mid]==m) return mid。//如果中間元素值為m返回中間元素下標(biāo)mid if(headtail) return 0。//如果xy，查找失敗，返回0 if(ma[mid]) //如果m比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果 return find(mid+1,tail)。 else //如果m比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果 return find(head,mid1)。}六、高精度加法includeiostreamincludecstringusing namespace std。int main(){ string str1,str2。 int a[250],b[250],len。 //數(shù)組的大小決定了計(jì)算的高精度最大位數(shù) int i。 memset(a,0,sizeof(a))。 memset(b,0,sizeof(b))。 cinstr1str2。 //輸入兩個(gè)字符串 a[0]=()。 //取得第一個(gè)字符串的長(zhǎng)度 for(i=1。i=a[0]。i++) //把第一個(gè)字符串轉(zhuǎn)換為整數(shù)，存放在數(shù)組a中 a[i]=str1[a[0]i]39。039。 b[0]=()。 //取得第二個(gè)字符串長(zhǎng)度 for(i=1。i=b[0]。i++) //把第二個(gè)字符串中的每一位轉(zhuǎn)換為整數(shù)，存放在數(shù)組B中 b[i]=str2[b[0]i]39。039。 len=(a[0]b[0]?a[0]:b[0])。 //取兩個(gè)字符串最大的長(zhǎng)度 for(i=1。i=len。i++) //做按位加法，同時(shí)處理進(jìn)位 { a[i]+=b[i]。 a[i+1]+=a[i]/10。 a[i]%=10。 } len++。 //下面是去掉最高位的0，然后輸出。 while((a[len]==0)amp。amp。(len1)) len。 for(i=len。i=1。i) couta[i]。 return 0。}注意：兩個(gè)數(shù)相加，結(jié)果的位數(shù)，應(yīng)該比兩個(gè)數(shù)中大的那個(gè)數(shù)多一位。七、高精度減法in
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1