排序算法總結(jié)C語(yǔ)言

排序算法總結(jié)一、插入排序(InsertionSort)

1.基本思想：

每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。

2.排序過程：

【示例】：

[初始關(guān)鍵字][49]38659776132749

J=2(38)[3849]659776132749

J=3(65)[384965]9776132749

J=4(97)[38496597]76132749

J=5(76)[3849657697]132749

J=6(13)[133849657697]2749

J=7(27)[13273849657697]49

J=8(49)[1327384949657697]代碼:ProcedureInsertSort(VarR:FileType);

//對(duì)R[1..N]按遞增序進(jìn)行插入排序,R[0]是監(jiān)視哨//

Begin

forI:=2ToNDo//依次插入R[2],...,R[n]//

begin

R[0]:=R;J:=I-1;

WhileR[0]<R[J]Do//查找R的插入位置//

begin

R[J+1]:=R[J];//將大于R的元素后移//

J:=J-1

end

R[J+1]:=R[0];//插入R//

end

End;//InsertSort//二、選擇排序

1.基本思想：

每一趟從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2.排序過程：

【示例】：

初始關(guān)鍵字[4938659776132749]

第一趟排序后13［38659776492749]

第二趟排序后1327［659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[49976576]

第五趟排序后1327384949[979776]

第六趟排序后132738494976[7697]

第七趟排序后13273849497676[97]

最后排序結(jié)果1327384949767697代碼:ProcedureSelectSort(VarR:FileType);//對(duì)R[1..N]進(jìn)行直接選擇排序//

Begin

forI:=1ToN-1Do//做N-1趟選擇排序//

begin

K:=I;

ForJ:=I+1ToNDo//在當(dāng)前無(wú)序區(qū)R[I..N]中選最小的元素R[K]//

begin

IfR[J]<R[K]ThenK:=J

end;

IfK<>IThen//交換R和R[K]//

beginTemp:=R;R:=R[K];R[K]:=Temp;end;

end

End;//SelectSort//三、冒泡排序(BubbleSort)

1.基本思想：

兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個(gè)數(shù)據(jù)元素的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。

2.排序過程：

設(shè)想被排序的數(shù)組R［1..N］垂直豎立，將每個(gè)數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復(fù)進(jìn)行，直至最后任何兩個(gè)氣泡都是輕者在上，重者在下為止。

【示例】：

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

4949497697979797代碼:ProcedureBubbleSort(VarR:FileType)//從下往上掃描的起泡排序//

Begin

ForI:=1ToN-1Do//做N-1趟排序//

begin

NoSwap:=True;//置未排序的標(biāo)志//

ForJ:=N-1DownTo1Do//從底部往上掃描//

begin

IfR[J+1]<R[J]Then//交換元素//

begin

Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;

NoSwap:=False

end;

end;

IfNoSwapThenReturn//本趟排序中未發(fā)生交換，則終止算法//

end

End;//BubbleSort//四、快速排序（QuickSort）

1.基本思想：

在當(dāng)前無(wú)序區(qū)R[1..H]中任取一個(gè)數(shù)據(jù)元素作為比較的"基準(zhǔn)"(不妨記為X)，用此基準(zhǔn)將當(dāng)前無(wú)序區(qū)劃分為左右兩個(gè)較小的無(wú)序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無(wú)序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無(wú)序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當(dāng)R[1..I-1]和R[I+1..H]均非空時(shí)，分別對(duì)它們進(jìn)行上述的劃分過程，直至所有無(wú)序子區(qū)中的數(shù)據(jù)元素均已排序?yàn)橹埂?/p>

2.排序過程：

【示例】：

初始關(guān)鍵字[4938659776132749］

第一次交換后

［2738659776134949］

第二次交換后

［2738499776136549］

J向左掃描，位置不變，第三次交換后

［2738139776496549］

I向右掃描，位置不變，第四次交換后

［2738134976976549］

J向左掃描

［2738134976976549］

（一次劃分過程）

初始關(guān)鍵字

［4938659776132749］

一趟排序之后

［273813］49［76976549］

二趟排序之后

［13］27［38］49［4965］76［97］

三趟排序之后1327384949［65］7697

最后的排序結(jié)果1327384949657697

各趟排序之后的狀態(tài)代碼:ProcedureParttion(VarR:FileType;L,H:Integer;VarI:Integer);

//對(duì)無(wú)序區(qū)R[1,H]做劃分，I給以出本次劃分后已被定位的基準(zhǔn)元素的位置//

Begin

I:=1;J:=H;X:=R;//初始化，X為基準(zhǔn)//

Repeat

While(R[J]>=X)And(I<J)Do

begin

J:=J-1//從右向左掃描，查找第1個(gè)小于X的元素//

IfI<JThen//已找到R[J]〈X//

begin

R:=R[J];//相當(dāng)于交換R和R[J]//

I:=I+1

end;

While(R<=X)And(I<J)Do

I:=I+1//從左向右掃描，查找第1個(gè)大于X的元素///

end;

IfI<JThen//已找到R>X//

begin

R[J]:=R;//相當(dāng)于交換R和R[J]//

J:=J-1

end

UntilI=J;

R:=X//基準(zhǔn)X已被最終定位//

End;//Parttion//代碼:ProcedureQuickSort(VarR:FileType;S,T:Integer);//對(duì)R[S..T]快速排序//

Begin

IfS<TThen//當(dāng)R[S..T]為空或只有一個(gè)元素是無(wú)需排序//

begin

Partion(R,S,T,I);//對(duì)R[S..T]做劃分//

QuickSort(R,S,I-1);//遞歸處理左區(qū)間R[S,I-1]//

QuickSort(R,I+1,T);//遞歸處理右區(qū)間R[I+1..T]//

end;

End;//QuickSort//五、堆排序(HeapSort)

1.基本思想：

堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來(lái)選擇最小的元素。

2.堆的定義:N個(gè)元素的序列K1,K2,K3,...,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：

Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子結(jié)點(diǎn)的關(guān)鍵字。例如序列10,15,56,25,30,70就是一個(gè)堆，它對(duì)應(yīng)的完全二叉樹如上圖所示。這種堆中根結(jié)點(diǎn)（稱為堆頂）的關(guān)鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結(jié)點(diǎn)的關(guān)鍵字均大于等于其孩子的關(guān)鍵字，則稱之為大根堆。

3.排序過程：

堆排序正是利用小根堆（或大根堆）來(lái)選取當(dāng)前無(wú)序區(qū)中關(guān)鍵字?。ɑ蜃畲螅┑挠涗泴?shí)現(xiàn)排序的。我們不妨利用大根堆來(lái)排序。每一趟排序的基本操作是：將當(dāng)前無(wú)序區(qū)調(diào)整為一個(gè)大根堆，選取關(guān)鍵字最大的堆頂記錄，將它和無(wú)序區(qū)中的最后一個(gè)記錄交換。這樣，正好和直接選擇排序相反，有序區(qū)是在原記錄區(qū)的尾部形成并逐步向前擴(kuò)大到整個(gè)記錄區(qū)。

【示例】：對(duì)關(guān)鍵字序列42，13，91，23，24，16，05，88建堆代碼:ProcedureSift(VarR:FileType;I,M:Integer);

//在數(shù)組R[I..M]中調(diào)用R，使得以它為完全二叉樹構(gòu)成堆。事先已知其左、右子樹(2I+1<=M時(shí))均是堆//

Begin

X:=R;J:=2*I;//若J<=M,R[J]是R的左孩子//

WhileJ<=MDo//若當(dāng)前被調(diào)整結(jié)點(diǎn)R有左孩子R[J]//

begin

If(J<M)AndR[J].Key<R[J+1].KeyThen

J:=J+1//令J指向關(guān)鍵字較大的右孩子//

//J指向R的左、右孩子中關(guān)鍵字較大者//

IfX.Key<R[J].KeyThen//孩子結(jié)點(diǎn)關(guān)鍵字較大//

begin

R:=R[J];//將R[J]換到雙親位置上//

I:=J;J:=2*I//繼續(xù)以R[J]為當(dāng)前被調(diào)整結(jié)點(diǎn)往下層調(diào)整//

end;

Else

Exit//調(diào)整完畢，退出循環(huán)//

end

R:=X;//將最初被調(diào)整的結(jié)點(diǎn)放入正確位置//

End;//Sift//代碼:ProcedureHeapSort(VarR:FileType);//對(duì)R[1..N]進(jìn)行堆排序//

Begin

ForI:=NDivDownto1Do//建立初始堆//

Sift(R,I,N)

ForI:=NDownto2do//進(jìn)行N-1趟排序//

begin

T:=R[1];R[1]:=R;R:=T;//將當(dāng)前堆頂記錄和堆中最后一個(gè)記錄交換//

Sift(R,1,I-1)//將R[1..I-1]重成堆//

end

End;//HeapSort//六、幾種排序算法的比較和選擇

1.選取排序方法需要考慮的因素：

(1)待排序的元素?cái)?shù)目n；

(2)元素本身信息量的大?。?/p>

(3)關(guān)鍵字的結(jié)構(gòu)及其分布情況；

(4)語(yǔ)言工具的條件，輔助空間的大小等。

2.小結(jié)：

(1)若n較小(n<=50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動(dòng)操作較直接選擇排序多，因而當(dāng)記錄本身信息量較大時(shí)，用直接選擇排序較好。

(2)若文件的初始狀態(tài)已按關(guān)鍵字基本有序，則選用直接插入或冒泡排序?yàn)橐恕?/p>

(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。

快速排序是目前基于比較的內(nèi)部排序法中被認(rèn)為是最好的方法。

(4)在基于比較排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來(lái)描述比較判定過程，由此可以證明：當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時(shí)間。

這句話很重要它告訴我們自己寫的算法是有改進(jìn)到最優(yōu)當(dāng)然沒有必要一直追求最優(yōu)

(5)當(dāng)記錄本身信息量較大時(shí)，為避免耗費(fèi)大量時(shí)間移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。,C語(yǔ)言排序算法總結(jié)相關(guān)知識(shí)介紹（所有定義只為幫助讀者理解相關(guān)概念，并非嚴(yán)格定義）：

1、穩(wěn)定排序和非穩(wěn)定排序

簡(jiǎn)單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。

比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過某種排序后為a1,a2,a4,a3,a5，

則我們說這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。2、內(nèi)排序和外排序

在排序過程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱為內(nèi)排序；

在排序過程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。3、算法的時(shí)間復(fù)雜度和空間復(fù)雜度

所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

===============================================

功能：選擇排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)

算法思想簡(jiǎn)單描述：

在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)--[n的平方]

===============================================

voidselect_sort(int*x,intn)

{

inti,j,min,t;

for(i=0;i<n-1;i++)/*要選擇的次數(shù)：0~n-2共n-1次*/

{

min=i;/*假設(shè)當(dāng)前下標(biāo)為i的數(shù)最小，比較后再調(diào)整*/

for(j=i+1;j<n;j++)/*循環(huán)找出最小的數(shù)的下標(biāo)是哪個(gè)*/

{

if(*(x+j)<*(x+min))

{

min=j;/*如果后面的數(shù)比前面的小，則記下它的下標(biāo)*/

}

}

if(min!=i)/*如果min在循環(huán)中改變了，就需要交換數(shù)據(jù)*/

{

t=*(x+i);

*(x+i)=*(x+min);

*(x+min)=t;

}

}

}================================================

功能：直接插入排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)

算法思想簡(jiǎn)單描述：

在要排序的一組數(shù)中，假設(shè)前面(n-1)[n>=2]個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)--[n的平方]

=====================================================

voidinsert_sort(int*x,intn)

{

inti,j,t;

for(i=1;i<n;i++)/*要選擇的次數(shù)：1~n-1共n-1次*/

{

/*

暫存下標(biāo)為i的數(shù)。注意：下標(biāo)從1開始，原因就是開始時(shí)

第一個(gè)數(shù)即下標(biāo)為0的數(shù)，前面沒有任何數(shù)，單單一個(gè)，認(rèn)為

它是排好順序的。

*/

t=*(x+i);

for(j=i-1;j>=0&&t<*(x+j);j--)/*注意：j=i-1，j--，這里就是下標(biāo)為i的數(shù)，在它前面有序列中找插入位置。*/

{

*(x+j+1)=*(x+j);/*如果滿足條件就往后挪。最壞的情況就是t比下標(biāo)為0的數(shù)都小，它要放在最前面，j==-1，退出循環(huán)*/

}

*(x+j+1)=t;/*找到下標(biāo)為i的數(shù)的放置位置*/

}

}================================================

功能：冒泡排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)

算法思想簡(jiǎn)單描述：

在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。下面是一種改進(jìn)的冒泡算法，它記錄了每一遍掃描后最后下沉數(shù)的位置k，這樣可以減少外層循環(huán)掃描的次數(shù)。冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)--[n的平方]

=====================================================

voidbubble_sort(int*x,intn)

{

intj,k,h,t;

for(h=n-1;h>0;h=k)/*循環(huán)到?jīng)]有比較范圍*/

{

for(j=0,k=0;j<h;j++)/*每次預(yù)置k=0，循環(huán)掃描后更新k*/

{

if(*(x+j)>*(x+j+1))/*大的放在后面，小的放到前面*/

{

t=*(x+j);

*(x+j)=*(x+j+1);

*(x+j+1)=t;/*完成交換*/

k=j;/*保存最后下沉的位置。這樣k后面的都是排序排好了的。*/

}

}

}

}================================================

功能：希爾排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)

算法思想簡(jiǎn)單描述：

在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。時(shí)間復(fù)雜度O(n3/2)

=====================================================

voidshell_sort(int*x,intn)

{

inth,j,k,t;

for(h=n/2;h>0;h=h/2)/*控制增量*/

{

for(j=h;j<n;j++)/*這個(gè)實(shí)際上就是上面的直接插入排序*/

{

t=*(x+j);

for(k=j-h;(k>=0&&t<*(x+k));k-=h)

{

*(x+k+h)=*(x+k);

}

*(x+k+h)=t;

}

}

}================================================

功能：快速排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中起止元素的下標(biāo)

算法思想簡(jiǎn)單描述：

快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少1?？焖倥判蛲ㄟ^一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。它是由C.A.R.Hoare于1962年提出的。顯然快速排序可以用遞歸實(shí)現(xiàn)，當(dāng)然也可以用?；膺f歸實(shí)現(xiàn)。下面的函數(shù)是用遞歸實(shí)現(xiàn)的，有興趣的朋友可以改成非遞歸的。快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n2)

=====================================================

voidquick_sort(int*x,intlow,inthigh)

{

inti,j,t;

if(low<high)/*要排序的元素起止下標(biāo)，保證小的放在左邊，大的放在右邊。這里以下標(biāo)為low的元素為基準(zhǔn)點(diǎn)*/

{

i=low;

j=high;

t=*(x+low);/*暫存基準(zhǔn)點(diǎn)的數(shù)*/

while(i<j)/*循環(huán)掃描*/

{

while(i<j&&*(x+j)>t)/*在右邊的只要比基準(zhǔn)點(diǎn)大仍放在右邊*/

{

j--;/*前移一個(gè)位置*/

}

if(i<j)

{

*(x+i)=*(x+j);/*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)小的數(shù)，替換基準(zhǔn)點(diǎn)的數(shù)*/

i++;/*后移一個(gè)位置，并以此為基準(zhǔn)點(diǎn)*/

}

while(i<j&&*(x+i)<=t)/*在左邊的只要小于等于基準(zhǔn)點(diǎn)仍放在左邊*/

{

i++;/*后移一個(gè)位置*/

}

if(i<j)

{

*(x+j)=*(x+i);/*上面的循環(huán)退出：即出現(xiàn)比基準(zhǔn)點(diǎn)大的數(shù)，放到右邊*/

j--;/*前移一個(gè)位置*/

}

}

*(x+i)=t;/*一遍掃描完后，放到適當(dāng)位置*/

quick_sort(x,low,i-1);/*對(duì)基準(zhǔn)點(diǎn)左邊的數(shù)再執(zhí)行快速排序*/

quick_sort(x,i+1,high);/*對(duì)基準(zhǔn)點(diǎn)右邊的數(shù)再執(zhí)行快速排序*/

}

}================================================

功能：堆排序

輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)

算法思想簡(jiǎn)單描述：

堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。堆的定義如下：具有n個(gè)元素的序列（h1,h2,...,hn),當(dāng)且僅當(dāng)滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹，調(diào)整它們的存儲(chǔ)順序，使之成為一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來(lái)看，堆排序需要兩個(gè)過程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。

堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog2n)。

/*

功能：滲透建堆

輸入：數(shù)組名稱（也就是數(shù)組首地址）、參與建堆元素的個(gè)數(shù)、從第幾個(gè)元素開始

*/

voidsift(int*x,intn,ints)

{

intt,k,j;

t=*(x+s);/*暫存開始元素*/

k=s;/*開始元素下標(biāo)*/

j=2*k+1;/*右子樹元素下標(biāo)*/

while(j<n)

{

if(j<n-1&&*(x+j)<*(x+j+1))/*判斷是否滿