排序算法

1、前兩天為準(zhǔn)備考軟件設(shè)計(jì)師就順便復(fù)習(xí)了下幾個(gè)常用的排序算法今天貼出來(lái)供大家參考!對(duì)其中的錯(cuò)漏之處敬請(qǐng)指正!排序排序所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來(lái)。當(dāng)待排序記錄的關(guān)鍵字都不相同時(shí)，排序結(jié)果是惟一的，否則排序結(jié)果不惟一。在待排序的文件中，若存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過(guò)排序后這些具有相同關(guān)鍵字的記錄之間的相對(duì)次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對(duì)次序發(fā)生改變，則稱這種排序方

2、法是不穩(wěn)定的。要注意的是，排序算法的穩(wěn)定性是針對(duì)所有輸入實(shí)例而言的。即在所有可能的輸入實(shí)例中，只要有一個(gè)實(shí)例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。一.插入排序插入排序插入排序的基本思想是每步將一個(gè)待排序的記錄按其排序碼值的大小，插到前面已經(jīng)排好的文件中的適當(dāng)位置，直到全部插入完為止。插入排序方法主要有直接插入排序和希爾排序。①.直接插入排序(穩(wěn)定)接插入排序的過(guò)程為：在插入第i個(gè)記錄時(shí)，R1R2..Ri1已經(jīng)排好序，將第i

3、個(gè)記錄的排序碼Ki依次和R1R2..Ri1的排序碼逐個(gè)進(jìn)行比較，找到適當(dāng)?shù)奈恢?。使用直接插入排序，?duì)于具有n個(gè)記錄的文件，要進(jìn)行n1趟排序。代碼如下:voidDir_(intA[]intN)直接插入排序intjtf(inti=1it)A[j1]=A[j]jA[j1]=t②.希爾排序(不穩(wěn)定)：代碼如下:voidDir_Choose(intA[]intn)直接選擇排序intktf(inti=0i=K2i且Ki=K2i1)(1=i=n2)。

4、根結(jié)點(diǎn)(堆頂)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者，稱為小根堆；根結(jié)點(diǎn)的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。若將此序列所存儲(chǔ)的向量R[1..n]看作是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。堆排序的關(guān)鍵步驟有兩個(gè)：一是如何建立初始堆；二是當(dāng)堆的根結(jié)點(diǎn)與堆的最后一個(gè)結(jié)點(diǎn)交換后，如何對(duì)少了一個(gè)結(jié)點(diǎn)后的結(jié)點(diǎn)序列做調(diào)整，使之重新成為

5、堆。堆排序的最壞時(shí)間復(fù)雜度為O(nlog2n)堆排序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數(shù)較多，所以堆排序不適宜于記錄較少的文件。堆排序是就地排序，輔助空間為O(1)，它是不穩(wěn)定的排序方法。代碼略..三.交換排序交換排序交換排序的基本思想是：兩兩比較待排序記錄的排序碼，并交換不滿足順序要求的那寫偶對(duì)，直到滿足條件為止。交換排序的主要方法有冒泡排序和快速排序.①.冒泡排序(穩(wěn)定的)冒泡排序?qū)⒈慌判虻挠涗洈?shù)組R[1..n]垂