排序的穩(wěn)定性
因?yàn)榇判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上的關(guān)鍵字相等的記錄， 排序結(jié)果可能會(huì)存在不唯一的情況。所以就有穩(wěn)定與不穩(wěn)定的定義。
假設(shè)ki=kj( 1 =< i <= n,1 =< j <= n, i != j)，且在排序前的序列中ri領(lǐng)先于rj。如果排序后ri仍領(lǐng)先于rj，則稱所用的排序方法是穩(wěn)定的;反之，若可能使得排序后的序列中rj領(lǐng)先于ri，則稱所用的排序方法是不穩(wěn)定的。
只要有一組關(guān)鍵字發(fā)生類似情況，就可認(rèn)為此排序方法是不穩(wěn)定的。
內(nèi)排序和外排序
根據(jù)在排序過(guò)程中待排序記錄是否全部放在內(nèi)存中，排序分為內(nèi)排序和外排序。
內(nèi)排序是在排序整個(gè)過(guò)程中，待排序的所有記錄全部被放置在內(nèi)存中。
外排序是由于排序的記錄個(gè)數(shù)太多，不能同時(shí)放置在內(nèi)存中，整個(gè)排序過(guò)程需要在內(nèi)外存之間多次交換數(shù)據(jù)才能進(jìn)行。
對(duì)內(nèi)排序來(lái)說(shuō)，排序算法的性能主要有3個(gè)影響因素：
1、時(shí)間性能
排序算法的時(shí)間開銷是衡量其好壞的最重要的標(biāo)志。
在內(nèi)排序中，主要進(jìn)行兩種操作：比較和移動(dòng)。
高效率的內(nèi)排序算法應(yīng)該具有盡可能少的關(guān)鍵字比較次數(shù)和盡可能少的記錄移動(dòng)次數(shù)。
2、輔助空間
評(píng)估算法的另一個(gè)主要標(biāo)準(zhǔn)是執(zhí)行算法所需要的輔助存儲(chǔ)空間。
輔助存儲(chǔ)空間是除了存放待排序所占用的存儲(chǔ)空間外，執(zhí)行算法所需要的其他存儲(chǔ)空間。
3、算法的復(fù)雜性
指算法本身的復(fù)雜性，過(guò)于復(fù)雜的算法也會(huì)影響排序的性能。
接下來(lái)本文介紹各種排序算法。
冒泡排序是一種交換排序，它的基本思想是：
兩兩比較相鄰記錄的關(guān)鍵字，如果反序則交換，直到?jīng)]有反序的記錄為止。
算法復(fù)雜度分析：
使用優(yōu)化后的冒泡排序，最好的情況下，僅需要n - 1次比較，時(shí)間復(fù)雜度為O(n);最壞情況下，需要n(n - 1)/2次比較和交換;
所以平均時(shí)間復(fù)雜度為O(n2)。
選擇排序的基本思想：
每一次遍歷時(shí)選取關(guān)鍵字最小的記錄作為有序序列的第i個(gè)記錄。
算法復(fù)雜度分析
簡(jiǎn)單選擇排序大的特點(diǎn)就是交換移動(dòng)數(shù)據(jù)次數(shù)少，但它的比較次數(shù)是和數(shù)組本身是否有序是無(wú)關(guān)的，即無(wú)論最好最差的情況，都要進(jìn)行n(n-1)/2次比較;在最好的情況下，不需要進(jìn)行交換，在最壞的情況下，進(jìn)行n-1次交換。
所以平均時(shí)間復(fù)雜度為O(n2)。
直接插入排序的基本操作：
將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而得到一個(gè)新的、記錄遞增1的有序表。
插入排序是進(jìn)行值移動(dòng)，而是不值交換。所以在量較小的情況下插入排序性能要優(yōu)于冒泡和簡(jiǎn)單選擇排序。
算法復(fù)雜度分析：
在最好的情況下，只需進(jìn)行比較n - 1次，無(wú)需進(jìn)行移動(dòng);
在最壞的情況下，比較(n + 2)(n - 1)/2次，交換(n + 4)(n - 1)/2次。
所以平均時(shí)間復(fù)雜度O(n2)
二分(折半)插入排序是一種在直接插入排序算法上進(jìn)行小改動(dòng)的排序算法。其與直接排序算法大的區(qū)別在于查找插入位置時(shí)使用的是二分查找的方式，在速度上有一定提升。
算法復(fù)雜度分析：
插入每個(gè)記錄需要O(log i)比較，最多移動(dòng)i+1次，最少2次。最佳情況O(n log n)，最差和平均情況O(n^2)。
總排序碼比較次數(shù)比直接插入排序的最差情況好得多，但比最好情況要差，所元素初始序列已經(jīng)按排序碼接近有序時(shí)，直接插入排序比二分插入排序比較次數(shù)少
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。
希爾排序通過(guò)將比較的全部元素分為幾個(gè)區(qū)域來(lái)提升插入排序的性能。這樣可以讓一個(gè)元素可以一次性地朝最終位置前進(jìn)一大步。然后算法再取越來(lái)越小的步長(zhǎng)進(jìn)行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數(shù)據(jù)幾乎是已排好的了。
更好的理解方式
將數(shù)組列在一個(gè)表中并對(duì)行排序(用插入排序)。重復(fù)這過(guò)程，不過(guò)每次用更小的列來(lái)進(jìn)行。最后整個(gè)表就只有一列了。
將數(shù)組轉(zhuǎn)換至表是為了更好地理解這算法，算法本身僅僅對(duì)原數(shù)組進(jìn)行排序(通過(guò)增加索引的步長(zhǎng)，例如是用i += step_size而不是i++)。
比如第一次放在5列中對(duì)每行使用快速排序排序，第二次放在3列中，最后放在1列中。類比于步長(zhǎng)從5到3再到1。
算法復(fù)雜度分析
希爾排序的算法復(fù)雜度和增量序列有關(guān)，只要最終步長(zhǎng)為1任何步長(zhǎng)序列都可以工作?？梢詤⒓酉柵判?。
堆
堆是具有下列性質(zhì)的完全二叉樹：
每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子節(jié)點(diǎn)的值，成為大頂堆;
每個(gè)節(jié)點(diǎn)的值都小于或等于其左右孩子節(jié)點(diǎn)的值，成為小頂堆;
完全二叉樹性質(zhì)
按完全二叉樹的性質(zhì)，該樹可以被順序存儲(chǔ)在數(shù)組中，按不同的角標(biāo)進(jìn)行表示。
即：
Parent(i) = (i-1)/2，i 的父節(jié)點(diǎn)下標(biāo)
Left(i) = 2i + 1，i 的左子節(jié)點(diǎn)下標(biāo)
Right(i) = 2(i + 1)，i 的右子節(jié)點(diǎn)下標(biāo)
基本思想
將待排序的序列構(gòu)造成一個(gè)大頂堆。此時(shí)，整個(gè)序列的大值就是堆定的根節(jié)點(diǎn)，將它移走(與堆數(shù)組末尾元素交換)，再將剩余n-1個(gè)序列重新構(gòu)造成一個(gè)堆，這樣就會(huì)得到第二大值，以此類推，就能得到一個(gè)有序序列了。
算法復(fù)雜度分析
在構(gòu)建堆時(shí)，對(duì)每個(gè)非葉子節(jié)點(diǎn)來(lái)說(shuō)，最多進(jìn)行2次比較和互換操作，復(fù)雜度為O(n);
在進(jìn)行排序時(shí)，第i次取堆頂記錄重新建堆需要用O(log i )時(shí)間，并需要取n-1次，所以重建堆的時(shí)間為O(nlogn)。
所以堆排序的時(shí)間復(fù)雜度為O(nlogn)。
實(shí)現(xiàn)步驟：
大堆調(diào)整(Max_Heapify)：從堆的倒數(shù)第一個(gè)非葉子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)。沒(méi)有必要從葉子節(jié)點(diǎn)開始，葉子節(jié)點(diǎn)可以看作是已符合堆特點(diǎn)的節(jié)點(diǎn)。
創(chuàng)建大堆(Build_Max_Heap)：將堆所有數(shù)據(jù)重新排序
堆排序(HeapSort)：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做大堆調(diào)整。
概念：
歸并排序是建立在歸并操作上的一種有效的排序算法，該算法是采用分治法的典型應(yīng)用。
它指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作。歸并排序算法依賴歸并操作。歸并排序有多路歸并排序、兩路歸并排序 , 可用于內(nèi)排序，也可以用于外排序。這里僅對(duì)內(nèi)排序的兩路歸并方法進(jìn)行討論。
算法思路
把 n 個(gè)記錄看成 n 個(gè)長(zhǎng)度為 l 的有序子表
進(jìn)行兩兩歸并使記錄關(guān)鍵字有序，得到 n/2 個(gè)長(zhǎng)度為 2 的有序子表
重復(fù)第 2 步直到所有記錄歸并成一個(gè)長(zhǎng)度為 n 的有序表為止。
算法復(fù)雜度分析：
在最后一步，需要依次遍歷兩個(gè)已排序的好的數(shù)組，此時(shí)的時(shí)間復(fù)雜度為O(n)。
同時(shí)又進(jìn)行著二路歸并，形成一顆完全二叉樹，此時(shí)整個(gè)排序需要進(jìn)行l(wèi)og2n次。
所以歸并排序的時(shí)間復(fù)雜度為O(nlogn)。這是它的最好、最壞、平均的時(shí)間性能。
基本思想
通過(guò)一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，直到整個(gè)序列有序。
復(fù)雜度分析
最好情況：partition每次劃分的都很均勻，如果排序n個(gè)關(guān)鍵字，其遞歸樹的深度就為floor(log2n)+ 1次，此時(shí)的復(fù)雜度為O(nlogn)。
如果是最壞情況，每次partition都只操作一個(gè)數(shù)字，該遞歸樹即為一顆斜樹，比較次數(shù)為n(n - 1)/2，時(shí)間復(fù)雜度為O(n2)。
平均復(fù)雜度為O(nlogn)。
基本思想
工作的原理是將數(shù)組分到有限數(shù)量的桶里。每個(gè)桶再個(gè)別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序)。
步驟
設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子。
尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
對(duì)每個(gè)不是空的桶子進(jìn)行排序。
從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。
算法復(fù)雜度
對(duì)于N個(gè)待排數(shù)據(jù)，M個(gè)桶，平均每個(gè)桶[N/M]個(gè)數(shù)據(jù)的桶排序平均時(shí)間復(fù)雜度為：
O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)
可以看出，最好情況即當(dāng)N=M時(shí)，每個(gè)桶只有一個(gè)數(shù)據(jù)時(shí)，能夠達(dá)到O(N)。
基本思想
計(jì)數(shù)排序是一種穩(wěn)定的線性時(shí)間排序算法。
計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C，其中C數(shù)組的第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來(lái)將A中的元素排到正確的位置。
步驟：
找出待排序的數(shù)組中大和最小的元素
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組 C 的第 i 項(xiàng)
對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加)
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng)，每放一個(gè)元素就將C(i)減去1
算法復(fù)雜度分析
當(dāng)輸入的元素是n個(gè)0到k之間的整數(shù)時(shí)，它的運(yùn)行時(shí)間是Θ(n + k)。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。
由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍(等于待排序數(shù)組的大值與最小值的差加上1)，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國(guó)云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
重慶分公司
重慶分公司
