第一部分查找

1、線性查找法：

importjava.util.Scanner;

publicclassSearchDataE1ement{

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System,in);

int[]array;

arxay=newint[]{8,7,5,4,1,5,9,6,3,4};

for(inti=0;i〈array.length;i++)

System,out.println(，，，，^array[i]);

System,out.printin();

intreplay=0;

do{

System.out.print("請(qǐng)輸入要查找的數(shù)字OTO"):

intnum=scanner,nextInt();

lable:{

for(intt=0;t<array.length;t++)

(if(num==array[t])

(

System,out.printIn("array="+array[t]);

breaklable;

)

}

System,out.printin("輸入的數(shù)字?jǐn)?shù)組中不存在")；

)

System,out.println("量新查找1:繼續(xù)0:結(jié)束?”);

replay=scanner.nextlnt();

}while(replay==l);

)

)

2、二分查找算法

importjava.util.Scanner;

publicclassSearchBinary{

publicstaticintscarchB(intFlarr,intkey)

{intlow=0;

inthigh=arr.leng:h-l;//

while(high>=low)

(

intmid=(low+high)/2;

if(key<arr[mid])

high=mid-l;

elseif(key==arr[mid])

returnmid;

else

low=mid+l;

)

return-1;

)

publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

int□array:newint[]{2,4,7,11,14,25,33,42,55,64,75,88,89,90,92};

intkey;

Scannerscanner=newScanner(System,in);

System.out.printlnC\n請(qǐng)輸入關(guān)鍵字：”)；

key=scanner.nextlnt();

//

intresult=searchB(array,key);

if(result!=-l)

System.out.printf(，z\n%dfoundinarrrayelement/d\n”,key,result);

else

System,out.printf%dnotfoundinarray\n，z,key);

)

)

C語(yǔ)言排序方法

學(xué)的排序算法有：插入排序，合并排序，冒泡排序，選擇排序，希爾排序，堆排序，快速排

序，計(jì)數(shù)排序，基數(shù)排序，桶排序(沒有實(shí)現(xiàn))。比較一下學(xué)習(xí)后的心得。

我不是很清楚他們的時(shí)間復(fù)雜度，也真的不知道他們到底誰(shuí)快誰(shuí)慢，因?yàn)闀系耐茖?dǎo)我確實(shí)

只是小小了解，并沒有消化。也沒有完全理解他們的精髓，所以又什么錯(cuò)誤的還需要高手指

點(diǎn)。呵呵。

I.普及一下排序稔定，所謂排序穩(wěn)定就是指：如果兩個(gè)數(shù)相同，對(duì)他們進(jìn)行的排序結(jié)果為他

們的相對(duì)順序不變。例如A={121,2,1}這里排序之后是A={1,1,12,2}穩(wěn)定就是排序后第一

個(gè)1就是排序前的第一個(gè)I,第二個(gè)1就是排序前第二人1,第三個(gè)1就是排序前的第三個(gè)

io同理2也是一樣。這里用顏色標(biāo)明了。不穩(wěn)定呢就是他們的順序不應(yīng)和開始順序一致。

也就是可能會(huì)是A={1,1,12,2}這樣的結(jié)果。

2.普及一下原地排序：原地排序就是指不申請(qǐng)多余的空間來進(jìn)行的排序，就是在原來的排序

數(shù)據(jù)中比較和交換的排序。例如快速排序，堆排序等都是原地排序，合并排序，計(jì)數(shù)排序等

不是原地排序。

3.感覺誰(shuí)最好，在我的印象中快速排序是最好的，時(shí)間復(fù)雜度：n*log(n),不穩(wěn)定排序。原

地排序。他的名字很棒，快速嘛。當(dāng)然快了。我覺得他的思想很不錯(cuò)，分治，而且還是原地

排序，省去和很多的空間浪費(fèi)。速度也是很快的，n*log(n)o但是有?個(gè)軟肋就是如果己經(jīng)

是排好的情況下時(shí)間復(fù)雜度就是n*n,不過在加入隨機(jī)的情況下這種情況也得以好轉(zhuǎn)，而且他

可以做任意的比較，只要你能給出兩個(gè)元素的大小關(guān)系就可以了。適用范圍廣，速度快。

4.插入排序：n*n的時(shí)間復(fù)雜度，穩(wěn)定排序，原地排序。插入排序是我學(xué)的第一個(gè)排序，速

度還是很快的，特別是在數(shù)組已排好了之后，用它的思想來插入一個(gè)數(shù)據(jù)，效率是很高的。

因?yàn)椴挥萌颗?。他的?shù)據(jù)交換也很少，只是數(shù)據(jù)后移，然后放入要插入的數(shù)據(jù)。(這里不

是指調(diào)用插入排序，而是用它的思想)。我覺得，在數(shù)據(jù)大部分都排好了，用插入排序會(huì)給

你帶來很大的方便。數(shù)據(jù)的移動(dòng)和交換都很少。

5.冒泡排序，n*n的時(shí)間復(fù)雜度，穩(wěn)定排序，原地排序。冒泡排序的思想很不錯(cuò)，一個(gè)一個(gè)

比較，把小的上移，依次確定當(dāng)前最小元素。因?yàn)樗?jiǎn)虺，穩(wěn)定排序，而且好實(shí)現(xiàn)，所以用

處也是比較多的。還有一點(diǎn)就是加上哨兵之后他可以提前退出。

6.選擇排序，n*n的時(shí)間復(fù)雜度，穩(wěn)定排序，原地排序。選擇排序就是冒泡的基本思想，從

小的定位，一個(gè)一個(gè)選擇，直到選擇結(jié)束。他和插入排序是一個(gè)相反的過程，插入是確定一

個(gè)元素的位置，而選擇是確定這個(gè)位置的元素。他的好處就是每次只選擇確定的元素，不會(huì)

對(duì)很多數(shù)據(jù)進(jìn)行交換。所以在數(shù)據(jù)交換量上應(yīng)該比冒泡小。

7.插入排序，選擇排序，冒泡排序的比較，他們的時(shí)間復(fù)雜度都是我覺得他們的效率

也是差不多的，我個(gè)人喜歡冒泡?些，因?yàn)橐盟臅r(shí)候數(shù)據(jù)多半不多，而且可以提前的返

回已經(jīng)排序好的數(shù)組。而其他兩個(gè)排序就算已經(jīng)排好了，他也要做全部的掃描。在數(shù)據(jù)的交

換匕冒泡的確比他們都多。呵呵。舉例說明插入一個(gè)數(shù)據(jù)在末尾后排序，冒泡只要一次就

能搞定，而選擇和插入都必須要n*n的復(fù)雜度才能搞定。就看你怎么看待咯。

8.合并排序：n*log(n)的時(shí)間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想是分治，先分成小

的部分，排好部分之后合并，因?yàn)槲覀兞硗馍暾?qǐng)的空間，在合并的時(shí)候效率是0(n)的。速度

很快。貌似他的上限是n叫og(n),所以如果說是比較的次數(shù)的話，他比快速排序要少一些。

對(duì)任意的數(shù)組都能有效地在n*log(n)排好序。但是因?yàn)樗欠窃嘏判?，所以雖然他很快，

但是貌似他的人氣沒有快速排序高。

9.堆排序：n*log(n)的時(shí)間復(fù)雜度，M穩(wěn)定排序，原地排序。他的思想是利用的堆這種數(shù)據(jù)

結(jié)構(gòu)，堆可以看成一個(gè)完全二叉樹，所以在排序中比較的次數(shù)可以做到很少。加上他也是原

地排序，不需要申請(qǐng)額外的空間，效率也不錯(cuò)?？墒撬乃枷敫杏X比快速難掌握一些。還有

就是在已經(jīng)排好序的基礎(chǔ)上添加一個(gè)數(shù)據(jù)再排序，他的交換次數(shù)和比較次數(shù)一點(diǎn)都不會(huì)減

少。雖然堆排序在使用的中沒有快速排序廣泛，但是他的數(shù)據(jù)結(jié)構(gòu)和思想真的很不錯(cuò)，而且

用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，效率沒得說。堆，還是要好好學(xué)習(xí)掌握的。

10.希爾排序:n*log(n)的時(shí)間復(fù)雜度(這里是錯(cuò)誤的,應(yīng)該是nNamda(l<lamda<2),lamda

和每次步長(zhǎng)選擇有關(guān)。)，非穩(wěn)定排序，原地排序。主要思想是分治，不過他的分治和合并

排序的分治不一樣，他是按步長(zhǎng)來分組的，而不是想合并那樣左一半右一半。開始步長(zhǎng)為整

個(gè)的長(zhǎng)度的一半。分成nLen/2個(gè)組，然后每組排序。接個(gè)步長(zhǎng)減為原來的一半在分組排序，

直到步長(zhǎng)為1，排序之后希爾排序就完成了。這個(gè)思路很好，據(jù)說是插入排序的升級(jí)版，所

以在實(shí)現(xiàn)每組排序的時(shí)候我故意用了插入排序。我覺得他是一個(gè)特別好的排序方法了。他的

缺點(diǎn)就是兩個(gè)數(shù)可能比較多次，因?yàn)閮蓚€(gè)數(shù)據(jù)會(huì)多次分穴過他們不會(huì)出現(xiàn)數(shù)據(jù)的交換。效率

也是很高的。

11.快速排序，堆排序，合并排序，希爾排序的比較，他們的時(shí)間復(fù)雜的都是n*log(n),我認(rèn)

為在使用上快速排序最廣泛，他原地排序，雖然不穩(wěn)定，可是很多情況下排序根本就不在意

他是否穩(wěn)定。他的比較次數(shù)是比較小的，因?yàn)樗褦?shù)據(jù)分成了大和小的兩部分。每次都確定

了一個(gè)數(shù)的位置，所以理論上說不會(huì)出現(xiàn)兩個(gè)數(shù)比較兩次的情況，也是在最后在交換數(shù)據(jù)，

說以數(shù)據(jù)交換上也很少。合并排序和堆排序也有這些優(yōu)點(diǎn)，但是合并排序要申請(qǐng)額外的空間。

堆排序堆已經(jīng)排好的數(shù)據(jù)交換上比快速多。所以目前快速排序用的要廣泛的多。還有他很容

易掌握和實(shí)現(xiàn)。

12.計(jì)數(shù)排序：n的時(shí)間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想比較新穎，就是先約定數(shù)

據(jù)的范圍不是很大，而且數(shù)據(jù)都是整數(shù)(或能定位到整數(shù))的情況，然后直接申請(qǐng)一個(gè)空間。

把要排序的數(shù)組A的元素值與申請(qǐng)空間B的下標(biāo)對(duì)應(yīng)，然后B中存放該下標(biāo)元素值的個(gè)數(shù),

從而直接定位A中每個(gè)元素的位置。這樣效率只為n。因?yàn)楸容^很特殊，雖然很快，但是用

的地方并不多。

13.基數(shù)排序…的時(shí)間復(fù)雜度，穩(wěn)定排序，非原地排序。他的思想是數(shù)據(jù)比較集中在一個(gè)范

圍，例如都是4位數(shù)，都是5位數(shù)，或數(shù)據(jù)有多個(gè)關(guān)鍵字，我們先從各位開始排，然后排十

位，依次排到最高位，因?yàn)槲覀兛梢杂靡?個(gè)n的方法排一位，所以總的方法為d*n的復(fù)雜度。

關(guān)鍵字也一樣，我們先排第3個(gè)關(guān)鍵字，在排第3個(gè)關(guān)鍵字，最后排第一個(gè)關(guān)鍵字。只有能

保證每個(gè)關(guān)鍵字在n的時(shí)訶復(fù)雜度完成，那么整個(gè)排序就是一個(gè)d*n的時(shí)間復(fù)雜度。所以總

的速度是很快的。不過有一點(diǎn)就是要確保關(guān)鍵字能在nMJ時(shí)間復(fù)雜度完成。

14?桶排序：n的時(shí)間復(fù)雜度，穩(wěn)定排序，非原地排序。主要思路和基數(shù)排序一樣，也是假設(shè)

都在一個(gè)范圍例如概率都在0-1,而且分布還挺均勻，那么我們也是和基數(shù)排序一樣對(duì)一個(gè)

數(shù)把他劃分在他指定的區(qū)域。然后在連接這些區(qū)域就可以了。書上對(duì)每個(gè)區(qū)域使用鏈表的存

儲(chǔ)，我認(rèn)為在寸小區(qū)域的時(shí)候也會(huì)有時(shí)間在里面。所以只是理論上的n時(shí)間復(fù);雜度。這種思

路是不錯(cuò)的o呵呵。

15.計(jì)數(shù)排序，基數(shù)排序，桶排序的比較，我覺得他們都很有思想，不過都是在特定情況下

才能發(fā)揮最大的效果。雖然效率很高，但是用的不會(huì)很廣泛。他們之間我更喜歡計(jì)數(shù)排序，

來個(gè)映射的方式就直接找到了自己的位置，很而明。和基數(shù)排序和同排序只是理論上的n

時(shí)間復(fù)雜度，基數(shù)排序要確定一個(gè)關(guān)鍵字的排序是n復(fù)雜度的，桶排序要確定每個(gè)區(qū)域的排

序是n復(fù)雜度的。

16.排序算法的最后感悟：黑格爾說過：存在即合理。所以這些排序的算法都是很好的，他

確實(shí)給了我們思想上的幫助。感謝前人把精華留給了我們。我得到的收獲很大，總結(jié)一下各

自排序的收獲：

冒泡：好實(shí)現(xiàn)，速度不慢，使用于輕量級(jí)的數(shù)據(jù)排序。

插入排序：也使用于小數(shù)據(jù)的排耳，但是我從他的思想口學(xué)到怎么插入一個(gè)數(shù)據(jù)。呵呵，這

樣就知道在排好的數(shù)據(jù)里面，不用再排序了，而是直接調(diào)用一下插入就可以了。

選擇排序：我學(xué)會(huì)了怎么去獲得最大值，最小值等方法。只要選擇一下，不就可以了。

合并排序：我學(xué)會(huì)分而治之的方法，而且在合并兩個(gè)數(shù)組的時(shí)候很適用。

堆排序：可以用它來實(shí)現(xiàn)優(yōu)先隊(duì)列，而且他的思想應(yīng)該給我加了很多內(nèi)力。

快速排序：本來就用的最多的排序，對(duì)我的幫助大的都不知道怎么說好。

希爾排序：也是分治，讓我看到了分治的不同，原來還有這種思想的存在。

計(jì)數(shù)排序，基數(shù)排序，桶排序：特殊情況特殊處理。

插入排序

插入排序主要思想是：把要排序的數(shù)字插入到已經(jīng)排好的數(shù)據(jù)中。

例如12356是已經(jīng)排好的序，我們將4插入到他們中，時(shí)插入之后也是排好序的。這里顯而

易見是插入到3的后面。變?yōu)?23456.實(shí)現(xiàn)思路：插入排序就是先是一個(gè)有序的數(shù)據(jù)，然后

把要插入的數(shù)據(jù)插到指定為位置，而排序首先給的就是無序的，我們?cè)趺创_定先得到一個(gè)有

序的數(shù)據(jù)呢？答案就是：如果只有一個(gè)，當(dāng)然是有序的咯。我們先拿一個(gè)出來，他是有序的,

然后把數(shù)據(jù)一個(gè)一個(gè)插入到其中，那么插入之后是有序的，所以直到最后都是有序的。。結(jié)

果就出來了！當(dāng)然在寫的時(shí)候還是有一個(gè)技巧的，不需要開額外的數(shù)組，下標(biāo)從第二個(gè)元素

開始遍歷知道最后一個(gè)，然后插入到前面己經(jīng)有序的數(shù)據(jù)中。這樣就不會(huì)浪費(fèi)空間了。插入

排序用處還是很多的，特別是鏈表中，因?yàn)殒湵硎侵羔槾娣诺模瑳]有數(shù)組那么好準(zhǔn)確的用下

標(biāo)表示，插入是簡(jiǎn)單有效的方法。

源代碼

I#include<stdio.h>

2#include<stdlib.h>

4//插入排序從下到大，nDala為要排序的數(shù)據(jù),nNum為數(shù)據(jù)的個(gè)數(shù)，該排序是穩(wěn)定的排序

5boolInseilionSort(intnData[],intnNum)

6{

7for(inti=1;i<nNum;++i)〃遍歷數(shù)組，進(jìn)行插入排序

81

9intnTemp=nDatafi];

10for(intj=0;j<i;++j)//對(duì)該數(shù)，尋找他要插入的位置

11{

12if(nDataUJ>nTemp)//找到位置，然后插入該位置，之后的數(shù)據(jù)后移

13{

14for(intk=i;k>j;-k)〃數(shù)據(jù)后移

15{

16nDatafk]=nDatafk-1];

17)

18nDatafj]=nTemp;〃將數(shù)據(jù)插入到指定位置

19break;

20)

21}

22)

24returntrue;

25}

27intmain()

28{

29ininDala[10]={4,10,9,876,5,4,3,2};〃創(chuàng)建10個(gè)數(shù)據(jù),測(cè)試

30InsertionSort(nData,10);〃調(diào)用插入排序

32for(inti=0;i<10;++i)

33{

34printf("%d",nDatafi]);

35)

37printfC'Xn");

38system("puase");

39return0;

401

冒泡排序

冒泡排序的主要思路：

我們把要排序的數(shù)組A={3,4,21}看成一組水泡，v!Tendif]-->就像冒泡一樣，輕的在上

面，重的在卜面，換成數(shù)據(jù)，就是小的在上面，大的在下面。我們先把最輕的冒出到頂端,

然后冒出第二輕的在最輕的下面，接著冒出第三輕的。依次內(nèi)推。直到所有都冒出來了為止。

3.我們?cè)趺醋龅桨炎钶p的放在頂端呢？我們從最底下的數(shù)據(jù)開始'冒，如果比他上面的數(shù)據(jù)

小，就交換(冒上去)，然后再用第二第下的數(shù)據(jù)比較(此時(shí)他已經(jīng)是較輕的一個(gè))，如果他

比他上面的小，則交換，把小的冒上去。直到比到第一位置，得到的就是最輕的數(shù)據(jù)咯，這

個(gè)過程就像是冒泡一樣，下面的和上面的比較，小的冒上去。大的沉下來。

畫個(gè)圖先：

最初第一次結(jié)果第二次結(jié)果第三次結(jié)果

3331

4413

2144

1222

開始：1和2比，1比2小，浮上，然后1跟4比，再1跟3比，這樣結(jié)構(gòu)就變?yōu)?,3,4,

2。最小的位置確定了，然后我們確定第二小的，同理2Vs4,2vs3得到2,再確定第3小

數(shù)據(jù)，3Vs4得到3,最后就是4為最大的數(shù)據(jù)，我們冒泡就排好了。

注：這里紅色的1,2是前一次比較1vs2交換的結(jié)構(gòu)。后面也一樣。

大概思路就這樣了，奉上源代碼：

#includc<stdio.h>

#include<stdlib.h>

〃冒泡排序,pnData要排序的數(shù)據(jù)，nLcn數(shù)據(jù)的個(gè)數(shù)

intBubbleSort(int*pnData,intnLen)

(

boolisOk=false;〃設(shè)置排序是否結(jié)束的哨兵

//i從[0,nLen-l)開始冒泡，確定第i個(gè)元素

for(inti=0;i<nLcn-1&&!isOk;++i)

{

isOk=true;〃假定排序成功

〃從[nLen-l,D檢查是否比上面一個(gè)小，把小的冒泡浮上去

for(intj=nLen-1;j>i;-j)

{

if(pnData[j]<pnDaa[j-1])〃如果下面的比上面小，交換

(

intnTemp=pnDala[j];

pnData[j]=pnData[j-1];

pnData|j-1]=nlemp;

isOk=false;

return1;

I

intmain()

(

intnData[10]={4,10,9,8,7,6,5,4,3,2};//創(chuàng)建10個(gè)數(shù)據(jù)，測(cè)試

BubbleSort(nData,10);〃調(diào)用冒泡排序

for(inti=0;i<10;++i)

{

printf("%d",nDatafi]);

I

printfCXn");

system("pause");

return0;

選擇排序

選擇排序和冒泡排序思路上有?點(diǎn)相似，都是先確定最小元素，再確定第二笑元素，最后確

定最大元素。他的主要流程如下：

1.加入一個(gè)數(shù)組A={5,362,4,7},我們對(duì)他進(jìn)行排序

2.確定最小的元素放在A[0]位置，我們?cè)趺创_定呢，首先默認(rèn)最小元素為5,他的索引為0,

然后用它跟3比較，比他打，則認(rèn)為最小元素為3,他的索引為1,然后用3跟6比，發(fā)現(xiàn)比

他小，最小元素還是3,然后跟2比，最小元素變成了2,索引為3,然后跟4比，跟7比。

當(dāng)比較結(jié)束之后，最小元素也塵埃落定了。就是2,索引為3,然后我們把他放在A⑼處。

為了使A[O]原有數(shù)據(jù)部丟失，我們使A[O](要放的位置)與A[3](最小數(shù)據(jù)的位置)交換。

這樣就不可以了嗎？

3.然后我們?cè)趤碚业诙≡兀旁贏[l],第三小元素，放在A[2]。。當(dāng)尋找完畢，我們排

序也就結(jié)束了。

4.不過，在找的時(shí)候要注意其實(shí)位置，不能在找A[2]的時(shí)候，還用A[2]的數(shù)據(jù)跟已經(jīng)排好的

比，一定要跟還沒有確定位置的元素比。還有一個(gè)技巧就是我們不能每次都存元素

值和索引，我們只存索引就可以了，通過索引就能找到元素了。

5.他和冒泡的相似和區(qū)別，冒泡和他最大的區(qū)別是他發(fā)現(xiàn)比他小就交換，把小的放上面，而

選擇是選擇到最小的在直接放在確定的位置。選擇也是穩(wěn)定的排序。

基本思路就這樣了，奉上源代碼：

#includc<stdio.h>

^include<stdlib.h>

〃選擇排序,pnData要排序的數(shù)據(jù)，nLcn數(shù)據(jù)的個(gè)數(shù)

intSelectSort(int*pnData,intnLen)

{

//i從[0,nLen-l)開始選擇，確定第i個(gè)元素

for(inti=0;i<nLen-1;++i)

{

intnlndex=i;

〃遍歷剩余數(shù)據(jù)，選擇出當(dāng)前最小的數(shù)據(jù)

for(intj=i+1;j<nLen;++j)

{

if(pnData[jJ<pnData[nlndex])

(

nlndex=j;

)

I

〃如果當(dāng)前最小數(shù)據(jù)索引不是i,也就是說排在i位置的數(shù)據(jù)在nlndex處

if(nlndex!=i)

{

〃交換數(shù)據(jù)，確定i位置的數(shù)據(jù)。

intnTcnip=pnDataj];

pnDatafi]=pnDala[nIndex];

pnData[nIndex]=nTemp;

}

return1;

intmain()

{

intnDataflO]={4,10,9,8,7,6,5,4,3,2};//創(chuàng)建10個(gè)數(shù)據(jù),測(cè)試

SclcctSort(nData,10);〃調(diào)用選擇排序

fbr(inti=0;i<10;++i)

{

printf(M%d”,nData[i]);

}

printf("\nu);

systemC'pause");

return0:

I

希爾排序

希爾排序，他的主要思想借用了合并排序的思想。不過他不是左邊一半右邊一半，而是按照

步K求分，隨著步K減少，分成的組也越少。然后進(jìn)行各組的插入排序。主要思路就是這樣。

#includc<stdio.h>

^include<stdlib.h>

〃對(duì)單個(gè)組排序

intSortGroup(int*pnData,intnLen,intnBegin,intnStep)

{

for(inti=nBcgin+nStep;i<nLcn;i+=nStep)

{

〃尋找i元素的位置，

for(intj=nBegin;j<i;j+=nStep)

{

〃如果比他小，則這里就是他的位置了

if(pnData[i]<pnDatafj])

{

intnTemp=pnDatafil;

for(intk=i;k>i;k-=nStep)

(

pnData[k]=pnData[k-nStep];

1

pnData[j]=nTemp;

return1;

I

〃希爾排序,pnData要排序的數(shù)據(jù)，nLen數(shù)據(jù)的個(gè)數(shù)

intShellSort(int*pnData,intnLen)

〃以nStep分組，nStep每次減為原來的一半。

for(intnStep=nLcn/2;nStep>0;nStep/=2)

〃對(duì)每個(gè)組進(jìn)行排序

for(inti=0;i<nStep;++i)

{

SorlGroup(pnData,nLen,i,nStep);

|

)

return1;

1

intmain()

{

intnData[101={4,10,9,8,7,6,5,4,3,2};〃創(chuàng)建10個(gè)數(shù)據(jù),測(cè)試

ShcllSort(nData,10);〃調(diào)用希爾排序

for(inti=0;i<10;++i)

{

printf("%d",nData[iJ);

)

printf("\n");

systein("pausen);

return0;

)

合并排序合并排序的主要思想是：把兩個(gè)已經(jīng)排序好的序列進(jìn)行合并，成為一個(gè)排序好的

序列。例如：135792468這兩個(gè)序列，各自都是排好序的，然后我們進(jìn)行合并，成為123456789

這樣一個(gè)

排好序的序列。貌似這個(gè)跟排序關(guān)系不大，因?yàn)榕判蚪o的是一個(gè)亂的序列，而合并是合并的

兩個(gè)已經(jīng)排序

好的序列。且慢，我們可以把需要排序的數(shù)據(jù)分解成N個(gè)子序列，當(dāng)分解的子序列所包含

數(shù)據(jù)個(gè)數(shù)為1的時(shí)

候，那么這個(gè)序列不久是有序了嗎？然后再合并。這個(gè)就是有名的“分治。例如321分成3,

2,1三個(gè)序列，1這個(gè)序列是有序的啦。同理2,3都是有序的。然后我們逐一的合并他們。

3,2合并為23,

然后在23與1合并為122。哈哈，排序成功。合并排序主要思路就是這樣了。

但是，問題乂出來了，怎么合并兩個(gè)有序列呢？我相信我應(yīng)該理解了數(shù)組的存儲(chǔ)方式，所以

直接用數(shù)組說

事啦。。我們先把下標(biāo)定位到各有序子序列的開始，也把合并之后數(shù)組的下標(biāo)定位到最初。

那么下標(biāo)對(duì)應(yīng)

的位置就是他們當(dāng)前的最小值了。然后拿他們來比較，把更小的那個(gè)放到合并之后數(shù)組的下

標(biāo)位置。這樣

,合并后數(shù)組的第一個(gè)元素就是他們的最小值了。接著，控制合并后數(shù)組的下標(biāo)后移一個(gè)，

把比較時(shí)小數(shù)

字所在序列對(duì)應(yīng)的下標(biāo)后移一個(gè)。這樣。下次比較的時(shí)候，他得到就是他的第二小，(第一

下已經(jīng)合并了

)就是當(dāng)前最小值了，在于另一個(gè)序列的當(dāng)前最小值比較，用小的一個(gè)放到合并后數(shù)組的相

應(yīng)位置。依次

類推。接著當(dāng)數(shù)據(jù)都合并玩了結(jié)束，合并完成。(這樣說忒空泛了，云里霧里的，BS一下以

前的我。)

13572468來做例子:

(1回合)1357246800000(合并后數(shù)據(jù)空)

(2)3572468100000(0表示空)因?yàn)镮<2所以把1放到合并后位置中了(這里I并不是丟

掉了，而是下

標(biāo)變?yōu)橹赶?了，1是沒有寫而已。呵呵。理解為數(shù)組的下標(biāo)指向了3)

(3)357468120000因?yàn)?>2,所以把而放進(jìn)去

⑷57468123000同理3<4

⑸57681234000同理5>4

(6)7681234500同理5>6

⑺781234560同理7>6

(8)0(空了)812345670同理7<8

(9)0012345678弄最后一個(gè)

當(dāng)然，這些只是思路。并不是一定一成不變的這樣。合并OK,那么我們就可?以用合并排序

了哦！哈哈

不過注意，那個(gè)321全部弄成一個(gè)單個(gè)數(shù)字，然后一個(gè)一個(gè)合并這樣來合并似乎不是很好,

貌似還有更好

的解決方案。哈哈，對(duì)了，就是我先分一半來合并。如果這一半是排好序的，那么合并不久

簡(jiǎn)單了嗎？但

是我怎么讓一般排好序呢，呵呵簡(jiǎn)單，我一半在分一半合并排序，在分一半合并排序，直到

分到兩個(gè)都是

1個(gè)了，就合并，ok!

例如，81726354：

(1)分成91726354

(2)把8172分成81和72把6354分成63和54

(3)81分成8和1,哦能合并了哦。合并為18,同理72,63,5人也可以分解成單個(gè)合并為27,36,45

(4)現(xiàn)在變?yōu)榱?8,27,36,45了,這個(gè)時(shí)侯，18和27能合并了，合并為1278同理36,合

并為453456

(5)好了最好吧，1278和3456合并為12345678.ok排序成功。

這樣把一個(gè)問題分解為兩個(gè)或多個(gè)小問題，然后在分解，最后解決小小問題，已達(dá)到解決打

問題的目的。

I#include<s(dio.h>

2#inckide<stdlib.h>

4〃合并排序的合并程序他合并數(shù)組nData中位置為[nP,nM)和[nM,nR).這個(gè)是更接近標(biāo)準(zhǔn)

的思路

5boolMcrgcStandard(intnData[],intnP,intnM,intnR)

6{

7intnl=nM-nP;〃第一個(gè)合并數(shù)據(jù)的長(zhǎng)度

8intn2=nR-nM;〃第二個(gè)合并數(shù)據(jù)的長(zhǎng)度

10int*pnDl=newint[nl+1];//申請(qǐng)一個(gè)保存第一個(gè)數(shù)據(jù)的空間

11int*pnD2=newint[n2+i];//申請(qǐng)二個(gè)保存第一個(gè)數(shù)據(jù)的空間

13for(inti=0;i<nl;++i)〃復(fù)制第一個(gè)數(shù)據(jù)到臨時(shí)空間里面

14{

15pnD1[il=nDatafnP+i];

16)

17pnDl|nl]=INT.MAX;〃將最后一個(gè)數(shù)據(jù)設(shè)置為最大值(哨兵)

19for(inti=0;i<n2:++i)〃兔制第二個(gè)數(shù)據(jù)到臨時(shí)空間里面

20(

21pnD2[i]=nDatafnM+i];

22}

23pnD2[n2]=INT_MAX;//將最后一個(gè)數(shù)據(jù)設(shè)置為最大值(哨兵)

25nl=n2=0;

27while(nP<nR)

28{

29nData[nP++]=pnDl[nll<pnD2fn2]?pnDI[nl++l:pnD2fn2++];〃取出當(dāng)前最小

值到指定位置

30)

32deletepnDl;

33deletepnD2;

34returntrue;

35}

37〃合并排序的合并程序他合并數(shù)組nData中位置為[nRnM)和[nM,nR).

38boolMerge(intnDatafl,intnP.intnM,intnR)

39{

40〃這里面有幾個(gè)注釋語(yǔ)句是因?yàn)楫?dāng)時(shí)想少寫幾行而至?？此贫塘?，其實(shí)運(yùn)行時(shí)間是一

樣的，而且不易閱讀。

42intnLenl=nM-nP;〃笫一個(gè)合并數(shù)據(jù)的長(zhǎng)度

43intnLen2=nR-nM;〃第二個(gè)合并數(shù)據(jù)的長(zhǎng)度

44int*pnDl=newint|nLenl];〃申請(qǐng)一個(gè)保存第一個(gè)數(shù)據(jù)的空間

45int*pnD2=newint[nLen2];〃申請(qǐng)一個(gè)保存第一個(gè)數(shù)據(jù)的空間

46

47inti=0;

48for(i=0;i<nLenl;++i)〃復(fù)制第一個(gè)數(shù)據(jù)到臨時(shí)空間里面

49(

50pnDl[i]=nData[nP+i];

51)

53intj=0;

54for(j=O;j<nLen2;++j)〃復(fù)制第二個(gè)數(shù)據(jù)到臨時(shí)空間里面

55{

56pnD21j]=nData[nM+j];

57}

59i=j=0;

60while(i<nLen1&&j<nLen2)

61

62//nData[nP++l=pnD1[i]<pnD2|j]?pnDlfi++]:pnD2fj++];〃取出當(dāng)前最小值添

加到數(shù)據(jù)中

64if(pnDI[il<pnD2[j])〃取出最小值，并添加到指定位置中，如果pnDl[i]<pnD2[j]

65{

66nDatalnPJ=pnDlli];〃取出pnDl的值，然后i++,定位到下一個(gè)個(gè)最小值。

67++i；

68}

69else//這里同上

70(

71nData[nPJ=pnD2[jJ;

72++j；

73)

74++nP;〃最后np++,到確定下一個(gè)數(shù)據(jù)

75I

77if(i<nLenl)//如果第一個(gè)數(shù)據(jù)沒有結(jié)束(第二個(gè)數(shù)據(jù)已經(jīng)結(jié)束了)

78(

79while(nP<nR)〃直接把第一個(gè)剩余的數(shù)據(jù)加到nData的后面即可。

80|

81//nDatalnP++J=pnDl[i++];

82nDatafnPl=pnDl[i];

83++nP;

84++i；

85}

86)

87else//否則(第一個(gè)結(jié)束，第二個(gè)沒有結(jié)束)

88|

89while(nP<nR)〃直接把第一個(gè)剩余的數(shù)據(jù)加到nData的后面即可。

90(

91//nData[nP++]=pnD2[j++];

92nData[nP]=pnD2[j];

93++nP;

94++j；

95)

96)

98deletepnDl;〃釋放申請(qǐng)的內(nèi)存空間

99deletepnD2;

100

101returntrue;

102}

104//合并的遞歸調(diào)用，排序[nBegin,nEnd)區(qū)間的內(nèi)容

105boolMergeRecursion(intnDa(a[],intnBegin,intnEnd)

106{

107if(nBegin>=nEnd-1)〃已經(jīng)到最小顆粒了，直接返回

108(

109returnfalse;

110}

112intnMid=(nBegin'+nEnd)/2;〃計(jì)算出他們的中間位置，便于分治

113MergeRecursion(nData,nBegin,nMid);〃遞歸調(diào)用，合并排序好左邊一半

114MergeRecursion(nData,nMid,nEnd);〃遞歸調(diào)用，合并排序好右邊一半

115//Merge(nData,nBegin,nMid,nEnd);〃將已經(jīng)合并排序好的左右數(shù)據(jù)合并，時(shí)整個(gè)

數(shù)據(jù)排序完成

116MergeStandard(nData,nBegin,nMid,nEnd);〃(用更接近標(biāo)準(zhǔn)的方法合并)

118returntrue;

119}

121//合并排序

122boolMcrgcSort(intnData[],intnNuni)

123(

124returnMergeRecursion(nData,0,nNum);〃調(diào)用遞歸，完成合并排序

125}

127intmain()

128{

129intnData[10]={4,10,3,8,5,6,7,4,9,2};//創(chuàng)建10個(gè)數(shù)據(jù)，測(cè)試

131McrgcSort(nData,10)；

132for(inti=0;i<10;++i)

133{

134printf("%d",nDataliJ);

135}

137printfCXn*');

138system("pause),);

139return0;

140}

堆排序

#include<stdio.h>

#include<stdlib.h>

〃交換兩個(gè)整數(shù)。注意一定要if判斷是否兩個(gè)相等，如果

〃不相等才交換，如果相等也交換會(huì)出錯(cuò)的。a^a=0

inlinevoidSwap(int&a,int&b)

(

if(a!=b)

{

aA=b;

bA=a;

aA=b;

1

〃維持一個(gè)最大堆

intHeapify(int*npData,intnPos,intnLen)

intnMax=-1;〃暫存最大值

intnChild=nPos*2;〃他的左孩子位置

while(nChild<=nLen)〃判斷他是否有孩子

(

nMax=npData[nPos];〃是當(dāng)前最大值為他

if(nMax<npData[nChild])〃與左孩子比較

nMax=npData[nChild];〃如果比左孩子小，就時(shí)最大值為左孩子

)

〃同理與右孩子比較，這里要注意，必須要保證有右孩子。

if(nChild+I<=nLen&&nMax<npData[nChild+11)

{

++nChild;〃賦值最大值的時(shí)候把孩子變?yōu)橛液⒆?，方便最后的?shù)據(jù)交換

nMax=npData[nChild];

)

if(nMax!=npDatalnPos])〃判斷是否該節(jié)點(diǎn)比孩子都打，如果不大

(

Swap(npData[nPos],npData[nChild]);〃與最大孩T交換數(shù)據(jù)

nPos=nChild;〃該節(jié)點(diǎn)位置變?yōu)榻粨Q孩子的位置

nChild*=2;〃因?yàn)橹挥薪粨Q后才使不滿足堆得性質(zhì)。

)

else〃都最大了，滿足堆得性質(zhì)了。退出循環(huán)

{

break;

)

)

return1;〃維持結(jié)束。

}

〃建立一個(gè)堆

intBuildHeap(int*npData,intnLen)

{

//從nLen/2最后一個(gè)有葉子的數(shù)據(jù)開始，逐一的插入堆，并維持堆得平衡。

〃因?yàn)槎咽且粋€(gè)完全二叉樹，所以nlen/2+l-nLen之間肯定都是葉子。

//葉子還判斷什么呢。只有一個(gè)數(shù)據(jù)?，肯定滿足堆得性質(zhì)咯。

fbr(inti=nLen/2;i>=1;-i)

{

Heapify(npData,i,nLen);

)

return1;

〃堆排序

intHeapSort(in(*npData,intnLen)

BuildHeap(npData,nLen);〃建立一個(gè)堆。

while(nLen>=1)〃逐一交和第一個(gè)元素交換數(shù)據(jù)到最后

(〃完成排序

Swap(npData[nLen],npData[1]);

-nLcn;

Heapify(npDala,1,nLen);〃交換之后一定要維持一下堆得性質(zhì)。

)〃不然小的成第一個(gè)元素,就不是堆了。

return1;

}

//main函數(shù)，

intmain()

{

intnData[ll]={0.9,8,7,6,5.4,321,0};〃測(cè)試數(shù)據(jù)，下標(biāo)從1開始哦。

HeapSort(nData,10);//堆排序

for(inti=l;i<=10;++i)〃輸出排序結(jié)果。

{

printf("%d",nData[il);

)

printf("\nH);

systemC'pause");

return0;

}

用堆排序?qū)崿F(xiàn)優(yōu)先隊(duì)列

I.一個(gè)是他是一個(gè)數(shù)組(當(dāng)然你也可以真的用鏈表來做。)。

2.他可以看做一個(gè)完全二叉樹。注意是完全二叉樹。所以他的葉子個(gè)數(shù)剛好是nSize/2個(gè)。

3.我使用的下標(biāo)從I開始，這樣好算，如果節(jié)點(diǎn)的位置為i,他的父節(jié)點(diǎn)就是i/2,他的左孩子

結(jié)點(diǎn)就是i*2,右孩子結(jié)點(diǎn)就是i*2+l,如果下標(biāo)從0開始，要復(fù)雜一點(diǎn)。

4.他的父節(jié)點(diǎn)一定不比子節(jié)點(diǎn)小(我所指的是最大堆)。

由這些性質(zhì)就可以看出堆得一些優(yōu)點(diǎn)：

1.可以一下找到最大值，就在第一個(gè)位置heap"].

2.維持堆只需要log(2,n)(n是數(shù)據(jù)個(gè)數(shù))的復(fù)雜度，速度比較快。他只需要比較父與子之間的

大小關(guān)系,所以比較次數(shù)就是樹的高度，而他是一個(gè)完全二叉樹，所以比較次數(shù)就是10g(2,n)o

具體實(shí)現(xiàn)：

具體實(shí)現(xiàn)就看看源代碼吧！

#include<stdio.h>

#include<stdlib.h>

〃定義一個(gè)堆得結(jié)構(gòu)體，

structMyHeap

{

int*pnData;〃指向數(shù)據(jù)的指針

intnSize;〃當(dāng)前堆中的元素個(gè)數(shù)

I；

〃調(diào)整數(shù)據(jù)，維持堆得性質(zhì)，這個(gè)和上次hcapify的作用一樣

〃只是這個(gè)時(shí)從子道父節(jié)點(diǎn)這樣的判斷而已。

intIncreaseKey(MyHeap*pHeap,intnPos)

//循環(huán)和他父節(jié)點(diǎn)判斷，只要nPos>1他就有父節(jié)點(diǎn)

whilc(nPos>1)

(

intnMax=pHeap->pnData[nPos];

intnParent=nPos/2;

〃如果他比父節(jié)點(diǎn)大，交換數(shù)據(jù)，并使判斷進(jìn)入父節(jié)點(diǎn)

//(因?yàn)橹挥懈腹?jié)點(diǎn)可能會(huì)影響堆得性質(zhì)。他的數(shù)據(jù)改變了。)

if(nMax>pHeap->pnDa(a[nParentl)

{

pHeap->pnDala[nPos]=pHeap->pnDatafnParent];

pHeap->pnData[nParent]=nMax:

nPos=nParent;

)

else〃否則堆沒有被破壞，退出循環(huán)

{

break;

I

)

return1;

}

〃插入數(shù)據(jù)，這里pnHeap為要插入的隊(duì)，nLen為當(dāng)前堆得大小。

//nData為要插入的數(shù)據(jù)，這里注意報(bào)保證堆得空間足夠。

intInscrtfMyHcap*pHcap,intnData)

(

++pHcap->nSizc;〃添加數(shù)據(jù)到末尾

pHeap->pnData[pHeap->nSize]=nData;

IncreaseKey(pHeap,pHe<ip->nSize);

return1;

1

〃彈出堆中W大元素，并使堆得個(gè)數(shù)減一

intPopMaxHeapCMyHeap*pHeap)

(

ininMax=pHeap->pnData[i1；//得到最大元素

〃不要忘記維持堆得性質(zhì)，因?yàn)樽畲笤匾呀?jīng)彈出了，主要思路就是

〃同他最大孩子填充這里。

intnPos=l;〃起始位1,因?yàn)樗麖棾?，所以是這里開始破壞堆得性質(zhì)的

intnChild=nPos*2;"他的左孩子的位置，

//循環(huán)填充，用最大孩子填充父節(jié)點(diǎn)

whilc(nChild<=pHeap->nSize)

intnTemp=pHeap->pnData[nChild];

if(nChild+I<=pHeap->nSize&&

nTemp<pHeap->pnData[nChild+1])

(

++nChild;

nTemp=pHeap->pnData[nChild];

)

pHcap->pnData[nPos]=nTemp;

nPos=nChild;

nChild*=2;

)

〃最好一個(gè)用最末尾的填充。

pHeap->pnData[nPos]=pHcap->pnData[pHcap->nSizc];

-pHeap->nSize;〃堆個(gè)數(shù)量減一

returnnMax;〃返回最大值。

I

〃程序入口main

intmain()

{

MyHeapmyHeap;〃定義一個(gè)堆

myHeap.pnData=(int*)::malloc(sizeof(int)*11);〃申請(qǐng)數(shù)據(jù)空間

myHcap.nSize=0;//初始大小為0

for(inii=l;i<=10;++i)〃給優(yōu)先隊(duì)列堆里添加數(shù)據(jù)

{

lnscrt(&myHcap,i);

)

for(inti=1;i<=10;++i)〃測(cè)試優(yōu)先隊(duì)列是否建立成功

{

printf("%d",myHeap.pnData[i]);

)

printf("\n");

while(myHeap.nSize>0)//逐一彈出隊(duì)歹ij的最大值。并驗(yàn)證

(

printf("%d”,PopMaxHcap(&myHcap));

}

printf("\nH);

:：free(myHeap.pnData);〃最后不要忘記釋放申請(qǐng)的空間

systemCpause'*);

return0;

I

基數(shù)排序

據(jù)說他的時(shí)間復(fù)雜度也是0(n),他的思路就是：

沒有計(jì)數(shù)排序那么理想，我們的數(shù)據(jù)都比較集中，都比較大，一般是4,5位?；緵]有小

的數(shù)據(jù)。

那我們的處理很簡(jiǎn)單，你不是沒有小的數(shù)據(jù)嘛。我給一個(gè)基數(shù)，例如個(gè)位，個(gè)位都是[0-10)

范圍內(nèi)的。先對(duì)他進(jìn)行歸類，把小的放上面，大的放下面，然后個(gè)位排好了，在來看10位,

我們也這樣把小的放上面，大的放下面，依次內(nèi)推，直到最高位排好。那么不就排好了嗎？

我們只需要做d(基數(shù)個(gè)數(shù))的循環(huán)就可以了。時(shí)間復(fù)雜度相當(dāng)于O(d*n)因?yàn)閐為常量，例

如5位數(shù)，d就是5.所以近似為O(n)的時(shí)間復(fù)雜度。這次自己寫個(gè)案例：

最初的數(shù)據(jù)排好個(gè)位的數(shù)據(jù)排好H立的數(shù)據(jù)排好百位的數(shù)據(jù)

981981725129

387753129387

753955753456

129725955725

955456456753

725387981955

456129387981

這里只需循環(huán)3次就出結(jié)果了。

!supportLists]->3.<!--[endif]-->但是注意，我們必須要把個(gè)位排好。但是個(gè)位怎么

排呢？這個(gè)是個(gè)問題。書上說的是一疊一疊的怎么合并，我是沒有理解的。希望知道的有高

手教我一下。

我是用的一個(gè)計(jì)數(shù)排序來排各位的，然后排十位。效率應(yīng)該也低不到哪里去。

思路就這樣咯。奉上源代碼：

#includc<stdio.h>

#include<stdlib.h>

〃計(jì)數(shù)排序，npRadix為對(duì)應(yīng)的關(guān)鍵字序列，nMax是關(guān)鍵字的范圍。叩Data是具體要

〃排的數(shù)據(jù)，nLen是數(shù)據(jù)的范圍，這里必須注意nplndex和npDala對(duì)應(yīng)的下標(biāo)要一致

〃也就是說nplndex[l]所對(duì)應(yīng)的值為npData[l]

intRadixCountSort(int*nplndex,intnMax,int*npData,intnLcn)

{

〃這里就不用說了，計(jì)數(shù)的排序。不過這里為了是排序穩(wěn)定

〃在標(biāo)準(zhǔn)的方法上做了小修改。

int*pnCount=(int*)malloc(sizeof(int)*nMax);〃保存計(jì)數(shù)的個(gè)數(shù)

for(inti=0;i<nMax;++i)

(

pnCountli]=0;

)

for(inti=0;i<nLen;++i)〃初始化計(jì)數(shù)個(gè)數(shù)

(

++pnCount[npIndex[i]]:

)

for(inti=1;i<10;++i)//確定不大于該位置的個(gè)數(shù)。

(

pnCount[i]+=pnCountfi-11;

int*pnSort=(int*)malloc(sizeof(int)*nLen);〃存放零時(shí)的排序結(jié)果。

〃注意：這里i是從nLcn-1到0的順序排序的，是為了使排序穩(wěn)定。

for(inti=nLen-1;i>=0;—i)

-pnCount[npIndex[i]];

pnSort[pnCount[npIndex[il]]=npDatafi];

for(inti=0;i<nLen;++i)//把排序結(jié)構(gòu)輸入到返回的數(shù)據(jù)中。

{

npDatafi]=pnSort[i];

)

free(pnSort);〃記得釋放資源。

free(pnCount);

return1;

I

〃基數(shù)排序

intRadixSortCint*nPData,ininLen)

{

//申請(qǐng)存放基數(shù)的空間

int*nDataRadix=(int*)malloc(sizeof(int)*nLen);

intnRadixBase=1;〃初始化倍數(shù)基數(shù)為I

boolnlsOk=false;//設(shè)置完成排序?yàn)閒alse

〃循環(huán)，知道排序完成

while(JnlsOk)

{

nlsOk=true;

nRadixBase*=10;

for(inti=0;i<nLcn;++i)

(

nDataRadix(i]=nPData[i]%nRadixBase;

nDataRadixfil/=nRadixBase/10;

if(nDataRadix[i]>0)

(

nlsOk=false;

)

}

if(nlsOk)〃如果所有的基數(shù)都為0,認(rèn)為排序完成，就是已經(jīng)判斷到最高位了。

(

break;

1

RadixCountSort(nDataRadix,10,nPData,nLen);

)

free(nDataRadix);

return1;

1

intinain()

//測(cè)試基數(shù)排序。

intnData[10]=(123,5264,9513,854,9639,1985J59,3654,8521,8888);

RadixSort(nData,10);

for(inti=0;i<10;++i)

{

printf(M%d”，nData[i]);

}

printf("\n");

system("pause");

return0;

I

計(jì)數(shù)排序：

貌似計(jì)數(shù)排序的復(fù)雜度為。(n)。很強(qiáng)大。他的基本思路為：

<!-[if!supportLists]->1.我們希望能線性的時(shí)間復(fù)雜度排序,如果一個(gè)一個(gè)

比較，顯然是不實(shí)際的，書上也在決策樹模型中論證了，比較排序的情況為nlogn的復(fù)雜度。

<!-[if!supportLists]->2.<!--[endif]-->既然不能一個(gè)一個(gè)比較，我們想到一個(gè)辦法，就是

如果我在排序的時(shí)候就知道他的位置，那不就是掃描一遍，把他放入他應(yīng)該的位置不就可以

了嘛。

<!-[if!supportLists]->3.要知道他的位置,我們只需要知道有多少不大于他

不就可以了嗎？

<!-[if!supportLists]->4.<!-"endif]-->以此為出發(fā)點(diǎn)，我們?cè)趺创_定不大于他的個(gè)數(shù)呢？

我們先來個(gè)約定，如果數(shù)處中的元素都比較集中，都在[0,max]范圍內(nèi)。我們開一個(gè)max的

空間b數(shù)組，把b數(shù)組下標(biāo)對(duì)應(yīng)的元素和要排序的A數(shù)組下標(biāo)對(duì)應(yīng)起來。這樣不就可以知

道不比他大的有多少個(gè)了嗎？我們只要把比他小的位置元素個(gè)數(shù)求和，就是不比他大的。例

如：A二{3,5,7};我們開一個(gè)大小為8的數(shù)組b,把a(bǔ)⑼=3放入b[3]中，使b[3]=0;同理b[5]

=l;b[7]=2;其他我們都設(shè)置為-1,哈哈我們只需要遍歷一下b數(shù)組，如果他有數(shù)據(jù)，就來

出來，鐵定是當(dāng)前最小的。如果要知道比a[2]小的數(shù)字有多少個(gè)，值只需要求出b[0]-b[61

的有數(shù)據(jù)的和就可以了。這個(gè)0(n)的速度不是蓋得。

<!-[if!supporlListsl->5.思路就是這樣咯。但是要注意兩個(gè)數(shù)相同的情況A

={1,2,33,4},這種情況就不可以咯，所以還是有點(diǎn)小技巧的。

<!-[if!supportLis(s]->6.<!Tendif]-->處理小技巧：我們不把A的元素大小與B的下標(biāo)

一一對(duì)應(yīng)，而是在B數(shù)組對(duì)應(yīng)處記錄該元素大小的個(gè)數(shù)，這不久解決了嗎。哈哈。例如A=

{123,3,4}我們開大小為5的數(shù)組b;記錄數(shù)組A中元素佳為0的個(gè)數(shù)為bl0|=0,記錄數(shù)組A

中元素個(gè)數(shù)為1的b⑴=1,同理b⑵=1,皿3]=2,皿4]=1;好了,這樣我們就知道比A[4](4)

小的元素個(gè)數(shù)是多少了：count=b[0]+b[l]+b[2j+b[3]=4;他就把A[4]的元素放在第4個(gè)

位置。

還是截張書上的圖：

?b1

?。1?！靶"i"

C一問，?(廠外，⑸小

<!-[if!vml]->.<!-[endifJ->

再次推薦《算法導(dǎo)論》這本書，在我的上次的隨筆中有下載鏈接。哈哈,真正支持還是需要

買一下紙版。呵呵。

<!-[if!supportLists]->7.不過在編程的時(shí)候還是要注意細(xì)節(jié)的，例如我不能每次都來算一下

比他小的個(gè)數(shù)。呵呵，思路就這樣了。奉上源代碼：

#include<stdio.h>

#include<stdlib.h>

〃計(jì)數(shù)排序

intCountSort(int*pData,intnLen)

int*pCout=NULL;〃保存記數(shù)數(shù)據(jù)的指針

pCout=(int*)malloc(sizeof(int)*nLen);//申請(qǐng)空間

〃初始化記數(shù)為0

fbr(inti=0;i<nLen;++i)

pCoutli]=0;

〃記錄排序記數(shù)。在排序的值相應(yīng)記數(shù)加I。

for(inti=0;i<nLen;++i)

++pCout[pData[i]];〃增

I

//確定不比該位置大的數(shù)據(jù)個(gè)數(shù)。

for(inti=1;i<nLen;++i)

pCoutfi]+=pCoutfi-1];〃不比他大的數(shù)據(jù)個(gè)數(shù)為他的個(gè)數(shù)加上前一個(gè)的記數(shù)。

)

int*pSort=NULL;〃保存排序結(jié)果的指針

pSort=(int*)malloc(sizeof(int)*nLcn);〃申請(qǐng)空間

for(inti=0;i<nLen;++i)

〃把數(shù)據(jù)放在指定位置。因?yàn)閜CouHpData[i]]的值就是不比他大數(shù)據(jù)的個(gè)數(shù)。

〃為什么要先減一，因?yàn)閜Cout[pData[i]]保存的是不比他大數(shù)據(jù)的個(gè)數(shù)中包括了

〃他自己，我的下標(biāo)是從零開始的!所以要先減一。

-pCout[pData[i]];〃因?yàn)橛邢嗤瑪?shù)據(jù)的可能，所以要把該位置數(shù)據(jù)個(gè)數(shù)減一。

pSort[pCout[pData[i]]]=pData[i];

)

//排序結(jié)束，復(fù)制到原來數(shù)組中。

for(inii=0;i<nLen;++i)