所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。排序算法，就是如何使得記錄按照要求排列的方法。排序算法在很多領(lǐng)域得到相當(dāng)?shù)刂匾?，尤其是在大量?shù)據(jù)的處理方面。一個(gè)優(yōu)秀的算法可以節(jié)省大量的資源。在各個(gè)領(lǐng)域中考慮到數(shù)據(jù)的各種限制和規(guī)范，要得到一個(gè)符合實(shí)際的優(yōu)秀算法，得經(jīng)過大量的推理和分析。
所謂排序算法，即通過特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對(duì)于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中，則經(jīng)過一定的排序算法之后，兩者在排序前后的相對(duì)位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們?cè)谂判蜻^程中也是各有區(qū)別的，不允許混淆不清。
排序基礎(chǔ)知識(shí)
排序的定義
排序，就是重新排列表中的元素，使表中的元素滿足按關(guān)鍵字遞增或遞減的過程。為了査找方便，通常要求計(jì)算機(jī)中的表是按關(guān)鍵字有序的。
排序的確切定義如下：
代碼語言：javascript
復(fù)制
輸入: n個(gè)記錄 R1，R2，R3…Rn, 對(duì)應(yīng)的關(guān)鍵字為 K1,K2,K3…Kn
輸出: 輸入序列的一個(gè)重排R1’，R2’，R3’…Rn’, 使得有K1’ ≤ K2’ ≤ K3’… ≤ Kn’ (其中 ≤可以換成其它的比較大小符號(hào))。
算法的穩(wěn)定性：
若待排序表中有兩個(gè)元素 Ri 和 Rj，其對(duì)應(yīng)的關(guān)鍵字 keyi = kcyj , 且在排序前 Ri 在 Rj 的前面。使用某一排序算法排序后，Ri 仍然在 Rj 的前面盡的前面，則稱這個(gè)排序算法是穩(wěn)定的。否則稱排序算法是不穩(wěn)定的。
需要注意的是，算法是否具有穩(wěn)定性并不能衡量—個(gè)算法的優(yōu)劣，它主要針對(duì)算法的性質(zhì)進(jìn)行描述。只需舉出一組關(guān)徤字的實(shí)例，即可說明一個(gè)算法是不穩(wěn)定的。
穩(wěn)定性是一個(gè)特別重要的評(píng)估標(biāo)準(zhǔn)。穩(wěn)定的算法在排序的過程中不會(huì)改變?cè)乇舜说奈恢玫南鄬?duì)次序，反之不穩(wěn)定的排序算法經(jīng)常會(huì)改變這個(gè)次序，這是我們不愿意看到的。我們?cè)谑褂门判蛩惴ɑ蛘哌x擇排序算法時(shí)，更希望這個(gè)次序不會(huì)改變，更加穩(wěn)定，所以排序算法的穩(wěn)定性，是一個(gè)特別重要的參數(shù)衡量指標(biāo)依據(jù)。就如同空間復(fù)雜度和時(shí)間復(fù)雜度一樣，有時(shí)候甚至比時(shí)間復(fù)雜度、空間復(fù)雜度更重要一些。所以往往評(píng)價(jià)一個(gè)排序算法的好壞往往可以從下邊幾個(gè)方面入手：(1)時(shí)間復(fù)雜度：即從序列的初始狀態(tài)到經(jīng)過排序算法的變換移位等操作變到最終排序好的結(jié)果狀態(tài)的過程所花費(fèi)的時(shí)間度量。(2)空間復(fù)雜度：就是從序列的初始狀態(tài)經(jīng)過排序移位變換的過程一直到最終的狀態(tài)所花費(fèi)的空間開銷。(3)使用場(chǎng)景：排序算法有很多，不同種類的排序算法適合不同種類的情景，可能有時(shí)候需要節(jié)省空間對(duì)時(shí)間要求沒那么多，反之，有時(shí)候則是希望多考慮一些時(shí)間，對(duì)空間要求沒那么高，總之一般都會(huì)必須從某一方面做出抉擇。(4)穩(wěn)定性：穩(wěn)定性是不管考慮時(shí)間和空間必須要考慮的問題，往往也是非常重要的影響選擇的因素。 [2]
常見排序算法
播報(bào)編輯
插入排序
插入排序算法是基于某序列已經(jīng)有序排列的情況下，通過一次插入一個(gè)元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執(zhí)行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大于該最大元素，則可直接插入最大元素的后面即可，否則再向前一位比較查找直至找到應(yīng)該插入的位置為止。插入排序的基本思想是，每次將1個(gè)待排序的記錄按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中，尋找最適當(dāng)?shù)奈恢?，直至全部記錄插入完畢。?zhí)行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的后面，因此插入該元素后并未改變?cè)蛄械那昂箜樞?。我們認(rèn)為插入排序也是一種穩(wěn)定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
排序算法有：一、冒泡排序;二、選擇排序;三、插入排序;四、希爾排序;五、歸并排序;六、快速排序;七、堆排序;八、計(jì)數(shù)排序;九、桶排序;十、基數(shù)排序。
一、冒泡排序
冒泡排序是排序算法中較為簡(jiǎn)單的一種，英文稱為Bubble Sort。它遍歷所有的數(shù)據(jù)，每次對(duì)相鄰元素進(jìn)行兩兩比較，如果順序和預(yù)先規(guī)定的順序不一致，則進(jìn)行位置交換;這樣一次遍歷會(huì)將最大或最小的數(shù)據(jù)上浮到頂端，之后再重復(fù)同樣的操作，直到所有的數(shù)據(jù)有序。
二、選擇排序
選擇排序簡(jiǎn)單直觀，英文稱為Selection Sort，先在數(shù)據(jù)中找出最大或最小的元素，放到序列的起始;然后再從余下的數(shù)據(jù)中繼續(xù)尋找最大或最小的元素，依次放到排序序列中，直到所有數(shù)據(jù)樣本排序完成。
三、插入排序
插入排序英文稱為Insertion Sort，它通過構(gòu)建有序序列，對(duì)于未排序的數(shù)據(jù)序列，在已排序序列中從后向前掃描，找到相應(yīng)的位置并插入，類似打撲克牌時(shí)的碼牌。插入排序有一種優(yōu)化的算法，可以進(jìn)行拆半插入。
基本思路是先將待排序序列的第一個(gè)元素看做一個(gè)有序序列，把第二個(gè)元素到最后一個(gè)元素當(dāng)成是未排序序列;然后從頭到尾依次掃描未排序序列，將掃描到的每個(gè)元素插入有序序列的適當(dāng)位置，直到所有數(shù)據(jù)都完成排序;如果待插入的元素與有序序列中的某個(gè)元素相等，則將待插入元素插入到相等元素的后面。
四、希爾排序
希爾排序也稱遞減增量排序，是插入排序的一種改進(jìn)版本，英文稱為Shell Sort，效率雖高，但它是一種不穩(wěn)定的排序算法。
插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效果是非常好的;但是插入排序每次只能移動(dòng)一位數(shù)據(jù)，因此插入排序效率比較低。
希爾排序在插入排序的基礎(chǔ)上進(jìn)行了改進(jìn)，它的基本思路是先將整個(gè)數(shù)據(jù)序列分割成若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全部數(shù)據(jù)進(jìn)行依次直接插入排序。
五、歸并排序
歸并排序英文稱為Merge Sort，歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個(gè)非常典型的應(yīng)用。它首先將數(shù)據(jù)樣本拆分為兩個(gè)子數(shù)據(jù)樣本, 并分別對(duì)它們排序, 最后再將兩個(gè)子數(shù)據(jù)樣本合并在一起; 拆分后的兩個(gè)子數(shù)據(jù)樣本序列, 再繼續(xù)遞歸的拆分為更小的子數(shù)據(jù)樣本序列, 再分別進(jìn)行排序, 直到最后數(shù)據(jù)序列為1，而不再拆分，此時(shí)即完成對(duì)數(shù)據(jù)樣本的最終排序。
歸并排序嚴(yán)格遵循從左到右或從右到左的順序合并子數(shù)據(jù)序列, 它不會(huì)改變相同數(shù)據(jù)之間的相對(duì)順序, 因此歸并排序是一種穩(wěn)定的排序算法.
作為一種典型的分而治之思想的算法應(yīng)用，歸并排序的實(shí)現(xiàn)分為兩種方法：
1、自上而下的遞歸;
2、自下而上的迭代;
六、快速排序
快速排序,英文稱為Quicksort，又稱劃分交換排序 partition-exchange sort 簡(jiǎn)稱快排。
快速排序使用分治法(Divide and conquer)策略來把一個(gè)序列(list)分為兩個(gè)子序列(sub-lists)。首先從數(shù)列中挑出一個(gè)元素，并將這個(gè)元素稱為「基準(zhǔn)」，英文pivot。重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面(相同的數(shù)可以到任何一邊)。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)(partition)操作。之后，在子序列中繼續(xù)重復(fù)這個(gè)方法，直到最后整個(gè)數(shù)據(jù)序列排序完成。
七、堆排序
堆排序，英文稱Heapsort，是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于(或者大于)它的父節(jié)點(diǎn)。堆排序?qū)崿F(xiàn)分為兩種方法：
1、大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列;
2、小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列;
算法步驟：
1、創(chuàng)建一個(gè)堆 H[0……n-1];
2、把堆首(最大值)和堆尾互換;
3、把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置;
4、重復(fù)步驟 2，直到堆的尺寸為 1
八、計(jì)數(shù)排序
計(jì)數(shù)排序英文稱Counting sort，是一種穩(wěn)定的線性時(shí)間排序算法。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C，其中第i個(gè)元素是待排序數(shù)組A中值等于 i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來將A中的元素排到正確的位置?；镜牟襟E如下：
1、找出待排序的數(shù)組中最大和最小的元素
2、統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù)，存入數(shù)組C的第i項(xiàng)
3、對(duì)所有的計(jì)數(shù)累加,從C中的第一個(gè)元素開始，每一項(xiàng)和前一項(xiàng)相加
4、反向填充目標(biāo)數(shù)組,將每個(gè)元素i放在新數(shù)組的第C[i]項(xiàng)，每放一個(gè)元素就將C[i]減去1
九、桶排序
桶排序也稱為箱排序，英文稱為 Bucket Sort。它是將數(shù)組劃分到一定數(shù)量的有序的桶里，然后再對(duì)每個(gè)桶中的數(shù)據(jù)進(jìn)行排序，最后再將各個(gè)桶里的數(shù)據(jù)有序的合并到一起。
十、基數(shù)排序
基數(shù)排序英文稱Radix sort，是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也僅限于整數(shù)。它首先將所有待比較數(shù)值，統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個(gè)有序序列。
下載文檔
