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