常用算法(C語言版)

1、程序設(shè)計(jì)之常用算法【解析算法含義】所謂解析法（analysis algorithm）是指用解析的方法找出表示問題的前提條件與結(jié)果之間關(guān)系的數(shù)學(xué)表達(dá)式，并通過表達(dá)式的計(jì)算來實(shí)現(xiàn)問題求解。解析算法【雞兔同籠 】一個(gè)籠子里面關(guān)了雞和兔子（雞有 2 只腳，兔子有 4 只腳，沒有例外）。已經(jīng)知道了籠子里面腳的總數(shù) a，問籠子里面至少有多少只動(dòng)物，至多有多少只動(dòng)物？ 【輸入數(shù)據(jù)】 第 1 行是測試數(shù)據(jù)的組數(shù) n，后面跟著 n 行輸入。每組測試數(shù)據(jù)占 1 行，包括一個(gè)正整數(shù) a (a 32768)。 【輸出要求】 n 行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出是兩個(gè)正整數(shù)，第一個(gè)是最少的動(dòng)物數(shù)，第二個(gè)是最多的動(dòng)物數(shù)，兩

2、個(gè)正整數(shù)用空格分開。如果沒有滿足要求的情況出現(xiàn)，則輸出2個(gè)0。 【輸入樣例 】2 3 20 【輸出樣例】 0 0 5 10 【解題思路】 這個(gè)問題可以描述成任給一個(gè)整數(shù) N：如果 N是奇數(shù)，輸出 0 0如果 N是 4 的倍數(shù)，輸出 N / 4 N / 2如果 N不是 4的倍數(shù)，輸出 N/4+1 N/2解析算法【參考程序】1. #include 2. void main( ) 3. 4. int nCases, i, nFeet; /nCases 表示輸入測試數(shù)據(jù)的組數(shù)，nFeet表示輸入的腳數(shù)。 5. scanf(%d, &nCases); 6. for(i = 0; i y，則增加新的箱子+

3、N；5.統(tǒng)計(jì)N個(gè)箱子中可以放1*1產(chǎn)品的空位數(shù)x;6.若1*1產(chǎn)品的數(shù)量x，則增加新的箱子+N;7.輸出結(jié)果N；解析算法1. #include 2. int main() 3. 4. int N, a, b, c, d, e, f, y, x；/N用來存儲(chǔ)需要的箱子數(shù)目，y用來存儲(chǔ) 2*2 的空位數(shù)目 5. / x 用來存儲(chǔ) 1*1 的空位數(shù)目。 6. int u4=0, 5, 3, 1; 7. /數(shù)組u 表示3*3 的產(chǎn)品數(shù)目分別是 4的倍數(shù)，4 的倍數(shù)+1, 4 的倍數(shù)+2, 4 的倍數(shù)+3 8. /時(shí)，為3*3的產(chǎn)品打開的新箱子中剩余的 2*2的空位的個(gè)數(shù) 9. while(1) 10.

4、 scanf(%d%d%d%d%d%d, &a, &b, &c, &d, &e, &f); 11. if (a = 0 & b = 0 & c = 0 & d = 0 & e = 0 & f = 0) break; 12. N = f + e + d + (c + 3) / 4; 13. /這里有一個(gè)小技巧 (c+3)/4 正好等于 c 除以4向上取整的結(jié)果,下同 14. y = 5 * d + uc % 4; 15. if(b y) N += (b - y + 8 ) / 9; 16. x = 36 * N - 36 * f - 25 * e - 16 * d - 9 * c - 4 * b

5、; 17. if(a x) N += ( a - x + 35 ) / 36; 18. printf(%dn, N); 19. retrun 0;21. 枚舉（窮舉）算法枚舉算法法，本質(zhì)上就是搜索算法。【基本思想】枚舉也稱作窮舉，指的是從問題所有可能的解的集合中一一枚舉各元素。用題目中給定的檢驗(yàn)條件判定哪些是無用的，哪些是有用的。能使命題成立，即為其解?！緝?yōu)缺點(diǎn)】優(yōu)點(diǎn)：算法簡單，在局部地方使用枚舉法，效果十分的好缺點(diǎn)：運(yùn)算量過大，當(dāng)問題的規(guī)模變大的時(shí)候，循環(huán)的階數(shù)越大，執(zhí)行速度越慢?！景馘X買百雞問題】有一個(gè)人有一百塊錢，打算買一百只雞。到市場一看，公雞一只3元,母雞一只5元,小雞3只1元,試求

6、用100元買100只雞,各為多少才合適?根據(jù)題意我們可以得到方程組與條件：3X + 5Y + Z/3 = 100；X + Y + Z = 100； （100 X，Y，Z = 0, Z%3 = 0）int x,y,z; for( x = 0; x 100; x+ ) /1000000次循環(huán) for( y = 0; y 100 ; y+ ) for( z = 0; z 0 = x = 0, Z%3 = 0）,因此代碼可以優(yōu)化為下面這樣子：for( x = 0; x = 0 ) y /= 7; z = 100 - x - y; if( z % 3 = 0 & 3 * x + 5 * y + z /

7、3 = 100 ) printf(%d %d %dn,x,y,z); 采用枚舉的方法進(jìn)行問題求解，需要注意3個(gè)問題：簡單數(shù)學(xué)模型，數(shù)學(xué)模型中變量數(shù)量盡量少，它們之間相互獨(dú)立。這樣問題解的搜索空間的維度就小，反應(yīng)到程序代碼中，循環(huán)嵌套的層次就會(huì)少。我們上面從3維優(yōu)化到一維。減少搜索的空間。利用已有知識(shí)，縮小數(shù)學(xué)模型中各個(gè)變量的取值范圍，避免不必要的計(jì)算。反應(yīng)到程序代碼中，循環(huán)體被執(zhí)行的次數(shù)少采用合適的搜索順序。對(duì)搜索空間的遍歷順序要與數(shù)學(xué)模型中的條件表達(dá)式一致。枚舉（窮舉）算法【生理周期問題】人生來就有三個(gè)生理周期，分別為體力、感情和智力周期，它們的周期長度為23天、28天和33天。每一個(gè)周期中

8、有一天是高峰。在高峰這天，人會(huì)在相應(yīng)的方面表現(xiàn)出色。例如，智力周期的高峰，人會(huì)思維敏捷，精力容易高度集中。因?yàn)槿齻€(gè)周期的周長不同，所以通常三個(gè)周期的高峰不會(huì)落在同一天。對(duì)于每個(gè)人，我們想知道何時(shí)三個(gè)高峰落在同一天。對(duì)于每個(gè)周期，我們會(huì)給出從當(dāng)前年份的第一天開始，到出現(xiàn)高峰的天數(shù)（不一定是第一次高峰出現(xiàn)的時(shí)間）。你的任務(wù)是給定一個(gè)從當(dāng)年第一天開始數(shù)的天數(shù)，輸出從給定時(shí)間開始（不包括給定時(shí)間）下一次三個(gè)高峰落在同一天的時(shí)間（距給定時(shí)間的天數(shù)）。例如：給定時(shí)間為10，下次出現(xiàn)三個(gè)高峰同天的時(shí)間是12，則輸出2（注意這里不是3）。 【輸入數(shù)據(jù) 】輸入四個(gè)整數(shù)：p, e, i和d。 p, e, i分別表

9、示體力、情感和智力高峰出現(xiàn)的時(shí)間（時(shí)間從當(dāng)年的第一天開始計(jì)算）。d 是給定的時(shí)間，可能小于p, e, 或 i。 所有給定時(shí)間是非負(fù)的并且小于365, 所求的時(shí)間小于21252。當(dāng)p = e = i = d = -1時(shí)，輸入數(shù)據(jù)結(jié)束。 【輸出要求 】從給定時(shí)間起，下一次三個(gè)高峰同天的時(shí)間（距離給定時(shí)間的天數(shù)）?！緲永斎搿? 0 0 100 5 20 34 3254 5 6 7 -1 -1 -1 -1【樣例輸出】Case 1: the next triple peak occurs in 21152 days.Case 2: the next triple peak occurs in 1957

10、5 days. Case 3: the next triple peak occurs in 16994 days. 【解題思路】 本題的關(guān)鍵是理清頭緒，理解輸入的p、e、i、d的含義： 對(duì)于給定時(shí)間d，求出某個(gè)時(shí)間x，使得時(shí)間x為給定時(shí)間d后第一次同為三個(gè)生理周期的高峰。根據(jù)題目可得出如下條件： （21252 x = d+1） （x-p）%23= 0，（x-e）%28= 0，（x-i）%33= 0 ）枚舉（窮舉）算法#include int main() int p, e ,i, d; int x; int num = 1; /變量num存儲(chǔ)輸入數(shù)據(jù)的組數(shù) while(1) scanf(%d

11、%d%d%d,&p,&e,&i,&d); if(p=-1 & e=-1 & i=-1 & d=-1) break; for( x=d+1;x=21252;x+) if(x-p)%23=0&(x-e)%28=0&(x-i)%33=0) printf(Case %d: the next triple peak occurs in %d days. ,num,x-d); num+; return 0; 枚舉（窮舉）算法【垃圾炸彈】2014年足球世界杯期間，為了方便球迷觀看比賽，街道上很多路口都放置了直播大屏幕，但是人群散去后總會(huì)在這些路口留下一堆垃圾。為此政府決定動(dòng)用一種最新發(fā)明“垃圾炸彈”。這種“

12、炸彈”利用最先進(jìn)的量子物理技術(shù)，爆炸后產(chǎn)生的沖擊波可以完全清除波及范圍內(nèi)的所有垃圾，并且不會(huì)產(chǎn)生任何其他不良影響。炸彈爆炸后沖擊波是以正方形方式擴(kuò)散的，炸彈威力（擴(kuò)散距離）以d給出，表示可以傳播d條街道。 假設(shè)城市的布局為嚴(yán)格的0,1024*0,1024的網(wǎng)格狀，由于財(cái)政問題，市政府只買得起一枚“垃圾炸彈”，希望你幫他們找到合適的投放地點(diǎn)，使得一次清除的垃圾總量最多。（假設(shè)垃圾數(shù)量為一個(gè)非負(fù)整數(shù)，且除設(shè)置大屏幕的路口以外的地點(diǎn)沒有垃圾） 【輸入數(shù)據(jù) 】第1行給出“炸彈”威力d；第2行給出一個(gè)整數(shù)n，表示設(shè)置了大屏幕（有垃圾）的路口數(shù)目；接下來n行，每行給出三個(gè)數(shù)字x，y，i，分別代表路口的坐標(biāo)

13、（x,y）以及垃圾數(shù)量i。點(diǎn)坐標(biāo)（x,y）保證是有效的（區(qū)間在0到1024之間），同一坐標(biāo)只會(huì)給出一次。【輸出要求 】輸出能清理垃圾最多的投放點(diǎn)數(shù)目，以及能夠清除的垃圾總量。【樣例輸入】124 4 106 6 20【樣例輸出】1 30【數(shù)據(jù)范圍】d=50,n=1000下圖是一個(gè)d=1的“垃圾炸彈”爆炸后的波及范圍排序算法我們通常所說的排序算法往往指的是內(nèi)部排序算法，即數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序。排序算法大體可分為兩種：排序算法（內(nèi)部）比較排序插入排序直接插入排序希爾排序冒泡排序選擇排序簡單選擇排序堆排序快速排序歸并排序非比較排序計(jì)數(shù)排序基數(shù)排序當(dāng)數(shù)據(jù)規(guī)模較大時(shí)應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)

14、的排序方法：快速排序、堆排序或歸并排序序?？焖倥判蚴悄壳盎诒容^的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短。排序算法穩(wěn)定性的簡單形式化定義為：如果Ai = Aj，排序前Ai在Aj之前，排序后Ai還在Aj之前，則稱這種排序算法是穩(wěn)定的。通俗地講就是保證排序前后兩個(gè)相等的數(shù)的相對(duì)順序不變。排序算法1.插入排序直接插入排序【基本思想】將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新的記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹??！疽c(diǎn)】設(shè)立哨兵，作為臨時(shí)存儲(chǔ)待排序記錄。【具體算法描述

15、】從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描如果該元素（已排序）大于新元素，將該元素移到下一位置重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置將新元素插入到該位置后重復(fù)步驟25示例：序列 6, 5, 3, 1, 8, 7, 2, 4 進(jìn)行插入排序的實(shí)現(xiàn)過程如下：排序算法【程序?qū)崿F(xiàn)】/ 分類 - 內(nèi)部比較排序/ 數(shù)據(jù)結(jié)構(gòu) - 數(shù)組/ 最差時(shí)間復(fù)雜度 - 最壞情況為輸入序列是降序排列的,此時(shí)時(shí)間復(fù)雜度o(n2)/ 最優(yōu)時(shí)間復(fù)雜度 - 最好情況為輸入序列是升序排列的,此時(shí)時(shí)間復(fù)雜度o(n)/ 平均時(shí)間復(fù)雜度 - o(n2)/ 所需輔助空間

16、- o(1)/ 穩(wěn)定性 - 穩(wěn)定void insertsort(int a, int n) for (int i = 1; i = 0 & aj get) / 從右向左進(jìn)行比較 aj + 1 = aj; / 如果當(dāng)前元素大于哨兵，就將其右移 j-; aj + 1 = get; / 將哨兵放入aj右側(cè)(相等元素的相對(duì)次序未變，是穩(wěn)定的) 排序算法2.插入排序希爾排序(Shell Sort)【基本思想】希爾排序又叫縮小增量排序或遞減增量排序，先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2d1

17、重復(fù)上述的分組和排序，直至所取的增量dt =1( dt dt-1d2= 1) for (int i = h; i = 0 & aj get) aj + h = aj; j = j - h; aj + h = get; h = h/2; / 遞減增量 【程序?qū)崿F(xiàn)】排序算法3.冒泡排序【基本思想】在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。這個(gè)算法的名字由來是因?yàn)樵叫?或越大)的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。【具體算法描述】比較相鄰的元素

18、，如果前一個(gè)比后一個(gè)大，就把它們兩個(gè)調(diào)換位置。對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。【示例】序列 6, 5, 3, 1, 8, 7, 2, 4 進(jìn)行冒泡排序的實(shí)現(xiàn)過程如下：排序算法/ 分類 - 內(nèi)部比較排序/ 數(shù)據(jù)結(jié)構(gòu) - 數(shù)組/ 最差時(shí)間復(fù)雜度 - o(n2)/ 最優(yōu)時(shí)間復(fù)雜度 - 如果能在內(nèi)部循環(huán)第一次運(yùn)行時(shí),使用一個(gè)旗標(biāo)來表示有無需要交換的可能,可以把最優(yōu)時(shí)間復(fù)雜度降低到o(n)/ 平均時(shí)間復(fù)雜度 - o(n2)/ 所

19、需輔助空間 - o(1)/ 穩(wěn)定性 - 穩(wěn)定void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp;void bubblesort(int a, int n) for (int j = 0; j n - 1; j+) / 每次最大元素就像氣泡一樣浮到數(shù)組的最后 for (int i = 0; i ai + 1) / 如果條件改成ai = ai + 1,則變?yōu)椴环€(wěn)定的排序算法 swap(a, i, i + 1);【程序?qū)崿F(xiàn)】排序算法4.選擇排序簡單選擇排序【基本思想】在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€(gè)數(shù)與第1個(gè)

20、位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個(gè)位置的數(shù)交換，依次類推，直到第n-1個(gè)元素（倒數(shù)第二個(gè)數(shù)）和第n個(gè)元素（最后一個(gè)數(shù)）比較為止。注意選擇排序與冒泡排序的區(qū)別：冒泡排序通過依次交換相鄰兩個(gè)順序不合法的元素位置，從而將當(dāng)前最小（大）元素放到合適的位置；而選擇排序每遍歷一次都記住了當(dāng)前最小（大）元素的位置，最后僅需一次交換操作即可將其放到合適的位置?！臼纠繉?duì)序列 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 進(jìn)行選擇排序的實(shí)現(xiàn)過程如右圖排序算法/ 分類 - 內(nèi)部比較排序/ 數(shù)據(jù)結(jié)構(gòu) - 數(shù)組/ 最差時(shí)間復(fù)雜度 - o(n2)/ 最優(yōu)時(shí)間復(fù)雜度 - o(n2)

21、/ 平均時(shí)間復(fù)雜度 - o(n2)/ 所需輔助空間 - o(1)/ 穩(wěn)定性 - 不穩(wěn)定void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp;void selectionsort(int a, int n) for (int i = 0; i n - 1; i+) / i為已排序序列的末尾 int min = i; for (int j = i + 1; j n; j+) / 未排序序列 if (aj size & aleft_child size & aright_child = 0; i-) / 從每一個(gè)非葉結(jié)點(diǎn)開始

22、向下進(jìn)行堆調(diào)整 heapify(a, i, heap_size); return heap_size;void heapsort(int a, int n) int heap_size = buildheap(a, n); / 建立一個(gè)最大堆 while (heap_size 1) / 堆（無序區(qū)）元素個(gè)數(shù)大于1，未完成排序 / 將堆頂元素與堆的最后一個(gè)元素互換，并從堆中去掉最后一個(gè)元素 / 此處交換操作很有可能把后面元素的穩(wěn)定性打亂，所以堆排序是不穩(wěn)定的排序算法 swap(a, 0, -heap_size); heapify(a, 0, heap_size); / 從新的堆頂元素開始向下進(jìn)行

23、堆調(diào)整，時(shí)間復(fù)雜度o(logn) 【程序?qū)崿F(xiàn)】排序算法6.快速排序（Quick Sort）【基本思想】1）選擇一個(gè)基準(zhǔn)元素,通常選擇第一個(gè)元素。2）通過一趟排序?qū)⒋判虻挠涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小，另一部分記錄的 元素值比基準(zhǔn)值大。3）此時(shí)基準(zhǔn)元素在其排好序后的正確位置。4）然后分別對(duì)這兩部分記錄用同樣的方法繼續(xù)進(jìn)行快速排序，直到整個(gè)序列有序?！究焖倥判虻氖纠浚╝）一趟排序的過程：int partition(int a, int low, int high) int privotkey = alow; /基準(zhǔn)元素 while(low high) /從兩端交

24、替地向中間掃描 /從后向前搜索，將較小的元素交換到低端 while(low = privotkey) high-; swap(a,low,high); /從前向后搜索，將較大的元素交換到高端 while(low high & alow = privotkey ) low+; swap(a,low,high); return low; 排序算法（b）排序的全過程void quicksort(int a, int low, int high) if(low mid 或jright，轉(zhuǎn)6 /其中一個(gè)數(shù)組已歸并完，比較選取結(jié)束/否則選取ai和aj較小的存入輔助數(shù)組af如果ai=aj，afindex=a

25、i； i+； index+； 轉(zhuǎn)2否則，afindex=aj； j+； index+； 轉(zhuǎn)2/將尚未處理完的子表中元素存入af如果i=mid，將aimid存入afindexright /前一數(shù)組非空如果j=right , 將ajright 存入afindexright /后一數(shù)組非空歸并結(jié)束，將arleftright存入aleftrightvoid merge(int a, int left, int mid, int right) / 合并兩個(gè)已排好序的數(shù)組aleft.mid和amid+1.right int index=left / 輔助數(shù)組ar的起始元素 int i = left; /

26、前一數(shù)組的起始元素 int j = mid + 1; / 后一數(shù)組的起始元素 while (i = mid & j = right) if(ai = aj) arindex+=ai+; / 帶等號(hào)保證歸并排序的穩(wěn)定性 else arindex+=aj+; while (i = mid) arindex+ = ai+; while (j = right) arindex+ = aj+; for (i=left; i = right; i+) ai = ari;排序算法/ 分類 - 內(nèi)部比較排序/ 數(shù)據(jù)結(jié)構(gòu) - 數(shù)組/ 最差時(shí)間復(fù)雜度 - o(nlogn)/ 最優(yōu)時(shí)間復(fù)雜度 - o(nlogn)/

27、 平均時(shí)間復(fù)雜度 - o(nlogn)/ 所需輔助空間 - o(n)/ 穩(wěn)定性 - 穩(wěn)定void merge(int a, int left, int mid, int right) / 歸并兩個(gè)已排好序的數(shù)組 /代碼省略void mergesortrecursion(int a, int left, int right) / 遞歸實(shí)現(xiàn)的歸并排序(自頂向下) if (left = right) return; / 當(dāng)待排序的序列長度為1時(shí)，遞歸結(jié)束 int mid = (left + right) / 2; mergesortrecursion(a, left, mid); / 前一數(shù)組排序

28、mergesortrecursion(a, mid + 1, right); /后一數(shù)組排序 merge(a, left, mid, right); /歸并兩個(gè)數(shù)組void mergesortiteration(int a, int len) / 非遞歸(迭代)實(shí)現(xiàn)的歸并排序(自底向上) int left, mid, right; / 子數(shù)組索引,前一個(gè)為aleft.mid，后一個(gè)子數(shù)組為amid+1.right for (int i = 1; i len; i *= 2) / 子數(shù)組的大小i初始為1，每輪翻倍 left = 0; while (left + i len) / 后一個(gè)子數(shù)組存在

29、(需要?dú)w并) mid = left + i - 1; right = mid + i len ? mid + i : len - 1; / 后一個(gè)子數(shù)組大小可能不夠 merge(a, left, mid, right); left = right + 1; / 前一個(gè)子數(shù)組索引向后移動(dòng) 排序算法8.計(jì)數(shù)排序【基本思想】計(jì)數(shù)排序的基本思想為一組數(shù)在排序之前先統(tǒng)計(jì)這組數(shù)中其他數(shù)小于這個(gè)數(shù)的個(gè)數(shù)，則可以確定這個(gè)數(shù)的位置。 例如要排序的數(shù)為 7 4 2 1 5 3 1 5；則比7小的有7個(gè)數(shù)，所有7應(yīng)該在排序好的數(shù)列的第八位，同理3在第四位，對(duì)于重復(fù)的數(shù)字，1在1位和2位（暫且認(rèn)為第一個(gè)1比第二個(gè)1小

30、），5和1一樣位于6位和7位?！居?jì)數(shù)排序的實(shí)現(xiàn)辦法】 首先需要三個(gè)數(shù)組，第一個(gè)數(shù)組記錄A要排序的數(shù)列大小為n，第二個(gè)數(shù)組B要記錄比某個(gè)數(shù)小的其他數(shù)字的個(gè)數(shù)，所以第二個(gè)數(shù)組的大小應(yīng)當(dāng)為K（數(shù)列中最大數(shù)的大?。谌齻€(gè)數(shù)組C為記錄排序好了的數(shù)列的數(shù)組，大小應(yīng)當(dāng)為n。接著記錄數(shù)列中每個(gè)數(shù)的出現(xiàn)次數(shù)到數(shù)組B，并通過前面的所有數(shù)的出現(xiàn)次數(shù)來確定比這個(gè)數(shù)小的數(shù)的個(gè)數(shù)，從而確定其位置。對(duì)于重復(fù)的數(shù)，每排好一個(gè)數(shù)則對(duì)其位置數(shù)進(jìn)行減1操作，以此對(duì)完成其余相同的數(shù)字進(jìn)行排位。【計(jì)數(shù)排序示例】待排序數(shù)列數(shù)i出現(xiàn)次數(shù)小于等于數(shù)i的個(gè)數(shù)數(shù)組A數(shù)組B0，1，1，2，3，4，5，7，9數(shù)組C排序算法/ 分類 - 內(nèi)部非比較

31、排序/ 數(shù)據(jù)結(jié)構(gòu) - 數(shù)組/ 平均時(shí)間復(fù)雜度 - (n+k)（其中k是整數(shù)的范圍）/ 所需輔助空間 - o(k+1)/ 穩(wěn)定性 - 穩(wěn)定void countsort(int a,int c,int n) int max = 0; for (int i = 0; i max ? ai : max; int b max+1; memset(b, 0, sizeof(b); /初始化數(shù)組b元素值為0 for (int i = 0; i n; i+) /統(tǒng)計(jì)數(shù)ai出現(xiàn)次數(shù) bai+; for (int i = 1; i max + 1; i+) /依次計(jì)算范圍1,max內(nèi)小于等于各數(shù)的數(shù)字個(gè)數(shù) bi

32、= bi + bi - 1; for (int i = 0; i n; i+) /將數(shù)組a各元素存入排好序的對(duì)應(yīng)位置 bai-; cbai = ai; 排序算法9.基數(shù)排序（Radix Sort）先說桶排序：基本思想是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序）。簡單來說，就是把數(shù)據(jù)分組，放在一個(gè)個(gè)的桶中，然后對(duì)每個(gè)桶里面的在進(jìn)行排序。例如要對(duì)大小為1.1000范圍內(nèi)的n個(gè)整數(shù)A1.n排序 首先，可以把桶設(shè)為大小為10的范圍，具體而言，設(shè)集合B1存儲(chǔ)1.10的整數(shù)，集合B2存儲(chǔ) (10.20的整數(shù)，集合Bi存儲(chǔ)( (i-1)*1

33、0, i*10的整數(shù)，i = 1,2,.100?？偣灿?100個(gè)桶。 然后，對(duì)A1.n從頭到尾掃描一遍，把每個(gè)Ai放入對(duì)應(yīng)的桶Bj中。 再對(duì)這100個(gè)桶中每個(gè)桶里的數(shù)字排序，這時(shí)可用冒泡，選擇，乃至快排，一般來說任 何排序法都可以。 最后，依次輸出每個(gè)桶里面的數(shù)字，且每個(gè)桶中的數(shù)字從小到大輸出，這樣就得到所有數(shù)字排好序的一個(gè)序列了。排序算法【基本思想】將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列。 基數(shù)排序的方式可以采用LSD（Least significant d

34、igital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。SD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用MSD的效率會(huì)比較好。以LSD為例，假設(shè)原來有一串?dāng)?shù)值如下所示：73, 22, 93, 43, 55, 14, 28, 65, 39, 81第1趟（個(gè)位數(shù)）第2趟（十位數(shù)）桶編號(hào)桶數(shù)值桶編號(hào)桶數(shù)值00181114222222，28373，93，43339414443555，6555566657773828881939993接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：81, 22, 73

35、, 93, 43, 14, 55, 65, 28, 39最后將這些桶子中的數(shù)值重新串接起來，即最終的排序結(jié)果：14, 22, 28, 39, 43, 55, 65, 73, 81, 93排序算法void radixsort(int a,length,maxradix) int m,n,k,lsp; k=1;m=1; int temp10length-1; empty(temp); /清空臨時(shí)空間 while(kmaxradix) /遍歷所有關(guān)鍵字 for(int i=0;ilength;i+) /分配過程 if(aim) temp0n=ai; else lsp=(ai/m)%10; /確定關(guān)鍵

36、字 templspn=ai; n+; collectelement(a,temp); /收集 n=0; m=m*10; k+; 排序算法各種排序的穩(wěn)定性，時(shí)間復(fù)雜度和空間復(fù)雜度總結(jié)：高精度計(jì)算【概念】高精度運(yùn)算,是指參與運(yùn)算的數(shù)(加數(shù),減數(shù),因子）范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型（整型，實(shí)型）能表示的范圍的運(yùn)算。以整數(shù)為例，最大的是long long類型，范圍是-263 ,263 )，假如要求范圍更大的兩個(gè)-21000 ,21000 )范圍內(nèi)的數(shù)的和，這時(shí)就要用到高精度算法了?！靖呔冗\(yùn)算涉及到的問題】（1）數(shù)據(jù)的輸入（2）數(shù)據(jù)的存儲(chǔ)（3）數(shù)據(jù)的運(yùn)算：如加法、乘法進(jìn)位和減法借位（4）結(jié)果的輸出：小數(shù)

37、點(diǎn)的位置和處理多余的0 當(dāng)輸入的數(shù)較長時(shí)，采用字符串方式輸入將字符串中的每一位數(shù)字取出，用數(shù)組存儲(chǔ)#include /c+中引用字符串類型數(shù)據(jù)必須該頭文件 void init(string s,int a) /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲(chǔ) a0=s.size(); / 利用數(shù)組元素a0存儲(chǔ)字符串長度,與s.length()同功能 for(int i=1;i=a0;i+) ai=sa0-i-0; / ai=sa0-i-48;高精度計(jì)算【算法分析】（1）運(yùn)算順序：兩個(gè)加數(shù)右對(duì)齊； 從低位向高位運(yùn)算相加；（2）運(yùn)算規(guī)則：同一位的數(shù)字相加，再加上從低位上來的進(jìn)位； 和/10為向高位的進(jìn)位，和%10

38、為該位的值；（3）最高位的進(jìn)位：最高位相加后進(jìn)位值不為0， 則和的結(jié)果應(yīng)添加一位；void add(int a,int b,int c) int lenc=1,x=0; /x保存每次相加的進(jìn)位 while(lenc=a0|lenc=b0) clenc=alenc+blenc+x; /兩數(shù)相加 x=clenc/10; /進(jìn)位用于下次相加 clenc+%=10; /該位的結(jié)果 if(x=0) lenc-; else clenc=x; /處理最高位相加后的進(jìn)位 c0=lenc; /保存和的長度 1.高精度加法。輸入兩個(gè)正整數(shù)，求他們的和高精度計(jì)算/高精度加法 #include #include /c

39、+中引用字符串類型數(shù)據(jù)必須該頭文件 #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN,cMAXN;void init(string s,int a) /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲(chǔ) /代碼略void add(int a,int b,int c) /高精度加法計(jì)算a+b-c /代碼略int main()string a1,b1;getline(cin,a1); /getline函數(shù)默認(rèn)是碰到換行符才結(jié)束，可讀入空格 cinb1; /碰到空格或換行符結(jié)束 memset(a,0

40、,sizeof(a); /要引用cstring頭文件 memset(b,0,sizeof(b);memset(c,0,sizeof(c);init(a1,a);init(b1,b);add(a,b,c);for(int i=c0;i=1;i-) coutci; /從高位輸出 return 0;高精度計(jì)算/高精度加法改良算法，節(jié)省存儲(chǔ)空間#include #include /c+中引用字符串類型數(shù)據(jù)必須該頭文件 #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void ini

41、t(string s,int a) /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲(chǔ) /代碼略void add(int a,int b) /高精度加法計(jì)算a+b-a int len=1; while(len=a0|lena1;cinb1; /碰到空格或換行符結(jié)束 memset(a,0,sizeof(a); memset(b,0,sizeof(b); init(a1,a);init(b1,b);add(a,b);for(int i=a0;i=1;i-) coutai; /從高位輸出 return 0;高精度計(jì)算【算法分析】（1）減法的輸入與存儲(chǔ)與加法相同； 字符串輸入、數(shù)組存儲(chǔ)（2）結(jié)果位數(shù)最大是兩個(gè)數(shù)中較大

42、數(shù)的位數(shù)； 比較兩個(gè)數(shù)大小、被減數(shù)必須比減數(shù)大（3）借位處理； 高位減1、當(dāng)前位加10（4）結(jié)果的輸出； 符號(hào)位、省略高位的02.高精度減法。輸入兩個(gè)正整數(shù)，求他們的差/高精度運(yùn)算的輸入與存儲(chǔ)#include #include #include using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void init(string s,int a) a0=s.size(); for(int i=1;i=a0;i+) ai=sa0-i-0; int main() string a1,b1; getl

43、ine(cin,a1); getline(cin,b1); memset(a,0,sizeof(a); memset(b,0,sizeof(b); init(a1,a); init(b1,b); 判斷兩個(gè)字符串a(chǎn)1、b1大小字符串長度不等，長度較小的字符串?。蛔址L度相等，可直接比較a1b1？字符串互換與兩個(gè)變量的值互換一樣；/減法及借位if(alen1) len-;高精度計(jì)算/高精度運(yùn)算 #include /c+中萬能頭文件 using namespace std;#define MAXN 1000 / const int MAXN=1000;int aMAXN,bMAXN;void init(string s,int a) /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲(chǔ) /代碼略void sub(int a,int b) /高精