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

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

1.基本思想：

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

2.排序過程：

【示例】：

[初始關鍵字][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);

//對R[1..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ù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。

2.排序過程：

【示例】：

初始關鍵字[4938659776132749]

第一趟排序后13［38659776492749]

第二趟排序后1327［659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[49976576]

第五趟排序后1327384949[979776]

第六趟排序后132738494976[7697]

第七趟排序后13273849497676[97]

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

Begin

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

begin

K:=I;

ForJ:=I+1ToNDo//在當前無序區(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)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。

2.排序過程：

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

【示例】：

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

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

Begin

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

begin

NoSwap:=True;//置未排序的標志//

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.基本思想：

在當前無序區(qū)R[1..H]中任取一個數(shù)據(jù)元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I-1]和R[I+1..H]，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，當R[1..I-1]和R[I+1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。

2.排序過程：

【示例】：

初始關鍵字[4938659776132749］

第一次交換后

［2738659776134949］

第二次交換后

［2738499776136549］

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

［2738139776496549］

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

［2738134976976549］

J向左掃描

［2738134976976549］

（一次劃分過程）

初始關鍵字

［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);

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

Begin

I:=1;J:=H;X:=R;//初始化，X為基準//

Repeat

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

begin

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

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

begin

R:=R[J];//相當于交換R和R[J]//

I:=I+1

end;

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

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

end;

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

begin

R[J]:=R;//相當于交換R和R[J]//

J:=J-1

end

UntilI=J;

R:=X//基準X已被最終定位//

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

Begin

IfS<TThen//當R[S..T]為空或只有一個元素是無需排序//

begin

Partion(R,S,T,I);//對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]看成是一顆完全二叉樹的順序存儲結(jié)構，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關系來選擇最小的元素。

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

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

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

3.排序過程：

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

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

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

Begin

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

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

begin

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

J:=J+1//令J指向關鍵字較大的右孩子//

//J指向R的左、右孩子中關鍵字較大者//

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

begin

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

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

end;

Else

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

end

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

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

Begin

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

Sift(R,I,N)

ForI:=NDownto2do//進行N-1趟排序//

begin

T:=R[1];R[1]:=R;R:=T;//將當前堆頂記錄和堆中最后一個記錄交換//

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

end

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

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

(1)待排序的元素數(shù)目n；

(2)元素本身信息量的大小；

(3)關鍵字的結(jié)構及其分布情況；

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

2.小結(jié)：

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

(2)若文件的初始狀態(tài)已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。

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

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

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

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

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

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

簡單地說就是所有相等的數(shù)經(jīng)過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。

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

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

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

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

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

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

功能：選擇排序

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

算法思想簡單描述：

在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。選擇排序是不穩(wěn)定的。算法復雜度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;/*假設當前下標為i的數(shù)最小，比較后再調(diào)整*/

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

{

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

{

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

}

}

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

{

t=*(x+i);

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

*(x+min)=t;

}

}

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

功能：直接插入排序

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

算法思想簡單描述：

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

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

voidinsert_sort(int*x,intn)

{

inti,j,t;

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

{

/*

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

第一個數(shù)即下標為0的數(shù)，前面沒有任何數(shù)，單單一個，認為

它是排好順序的。

*/

t=*(x+i);

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

{

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

}

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

}

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

功能：冒泡排序

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

算法思想簡單描述：

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

算法思想簡單描述：

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

{

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ù)組中起止元素的下標

算法思想簡單描述：

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

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

voidquick_sort(int*x,intlow,inthigh)

{

inti,j,t;

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

{

i=low;

j=high;

t=*(x+low);/*暫存基準點的數(shù)*/

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

{

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

{

j--;/*前移一個位置*/

}

if(i<j)

{

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

i++;/*后移一個位置，并以此為基準點*/

}

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

{

i++;/*后移一個位置*/

}

if(i<j)

{

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

j--;/*前移一個位置*/

}

}

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

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

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

}

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

功能：堆排序

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

算法思想簡單描述：

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

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

/*

功能：滲透建堆

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

*/

voidsift(int*x,intn,ints)

{

intt,k,j;

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

k=s;/*開始元素下標*/

j=2*k+1;/*右子樹元素下標*/

while(j<n)

{

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