c語言常用排序算法

《c語言常用排序算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、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ù)在外存中

2、的存放順序排序方法稱為外排序。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è)位置

3、的數(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

4、=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)

5、在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)--[n的平方]=====================================================voidinsert_sort(int*x,intn){inti,j,t;for(i=1;i

6、);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)前還未排好

7、序的范圍內(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)]有比

8、較范圍*/{for(j=0,k=0;j