1. 簡介

排序與我們?nèi)粘Ｉ钪邢⑾⑾嚓P(guān)，比如，我們要從電話簿中找到某個聯(lián)系人首先會按照姓氏排序、買火車票會按照出發(fā)時間或者時長排序、買東西會按照銷量或者好評度排序、查找文件會按照修改時間排序等等。在計算機程序設(shè)計中，排序和查找也是最基本的算法，很多其他的算法都是以排序算法為基礎(chǔ)，在一般的數(shù)據(jù)處理或分析中，通常第一步就是進(jìn)行排序，比如說二分查找，首先要對數(shù)據(jù)進(jìn)行排序

排序的算法有很多，在維基百科上有這么一個分類，另外大家有興趣也可以直接上維基百科上看相關(guān)算法

2. 選擇排序

原理

選擇排序很簡單，他的步驟如下：

1. 從左至右遍歷，找到最小(大)的元素，然后與第一個元素交換。

2. 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓笈c第二個元素進(jìn)行交換。

3. 以此類推，直到所有元素均排序完畢。

之所以稱之為選擇排序，是因為每一次遍歷未排序的序列我們總是從中選擇出最小的元素。

實現(xiàn)

```

def selection_sort(list2):

? ? ? for i in range(0, len (list2)):

? ? ? ? ? ?min = i

? ? ? ? ? ?for j in range(i + 1, len(list2)):

? ? ? ? ? ? ? ? if list2[j] < list2[min]:

? ? ? ? ? ? ? ? ? ? min = j

? ? ? ? ? ? ? ? ? ? ?list2[i], list2[min] = list2[min], list2[i]? # swap

```

*選擇排序需要花費 (N – 1) + (N – 2) + … + 1 + 0 = N(N- 1) / 2 ~ N2/2次比較 和 N-1次交換操作。

*對初始數(shù)據(jù)不敏感，不管初始的數(shù)據(jù)有沒有排好序，都需要經(jīng)歷N2/2次比較，這對于一些原本排好序，或者近似排好序的序列來說并不具有優(yōu)勢。在最好的情況下，即所有的排好序，需要0次交換，最差的情況，倒序，需要N-1次交換。

*數(shù)據(jù)交換的次數(shù)較少，如果某個元素位于正確的最終位置上，則它不會被移動。在最差情況下也只需要進(jìn)行N-1次數(shù)據(jù)交換，在所有的完全依靠交換去移動元素的排序方法中，選擇排序?qū)儆诒容^好的一種。

3. 插入排序
原理

插入排序也是一種比較直觀的排序方式?？梢砸晕覀兤匠４驌淇伺茷槔齺碚f明，假設(shè)我們那在手上的牌都是排好序的，那么插入排序可以理解為我們每一次將摸到的牌，和手中的牌從左到右依次進(jìn)行對比，如果找到合適的位置則直接插入。具體的步驟為：

1. 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序

2. 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描

3. 如果該元素小于前面的元素（已排序），則依次與前面元素進(jìn)行比較如果小于則交換，直到找到大于該元素的就則停止；

4. 如果該元素大于前面的元素（已排序），則重復(fù)步驟2

5. 重復(fù)步驟2~4 直到所有元素都排好序

實現(xiàn)

3. 希爾排序

原理：

希爾排序也稱之為遞減增量排序，他是對插入排序的改進(jìn)。在第二部插入排序中，我們知道，插入排序?qū)τ诮埔雅藕眯虻男蛄衼碚f，效率很高，可以達(dá)到線性排序的效率。但是插入排序效率也是比較低的，他一次只能將數(shù)據(jù)向前移一位。比如如果一個長度為N的序列，最小的元素如果恰巧在末尾，那么使用插入排序仍需一步一步的向前移動和比較，要N-1次比較和交換。

希爾排序通過將待比較的元素劃分為幾個區(qū)域來提升插入排序的效率。這樣可以讓元素可以一次性的朝最終位置邁進(jìn)一大步，然后算法再取越來越小的步長進(jìn)行排序，最后一步就是步長為1的普通的插入排序的，但是這個時候，整個序列已經(jīng)是近似排好序的，所以效率高。

實現(xiàn)：

可以看到，希爾排序的實現(xiàn)是在插入排序的基礎(chǔ)上改進(jìn)的，插入排序的步長為1，每一次遞減1，希爾排序的步長為我們定義的h，然后每一次和前面的-h位置上的元素進(jìn)行比較。算法中，我們首先獲取小于N/3 的最大的步長，然后逐步長遞減至步長為1的一般的插入排序。

分析：

1. 希爾排序的關(guān)鍵在于步長遞減序列的確定，任何遞減至1步長的序列都可以，目前已知的比較好的序列有：

Shell’s 序列: N/2 , N/4 , …, 1 (重復(fù)除以2);

Hibbard’s 序列: 1, 3, 7, …, 2k – 1 ;

Knuth’s 序列: 1, 4, 13, …, (3k – 1) / 2 ;該序列是本文代碼中使用的序列。

已知最好的序列是 Sedgewick’s (Knuth的學(xué)生，Algorithems的作者)的序列: 1, 5, 19, 41, 109, ….

該序列由下面兩個表達(dá)式交互獲得:

1, 19, 109, 505, 2161,….., 9(4k – 2k) + 1, k = 0, 1, 2, 3,…

5, 41, 209, 929, 3905,…..2k+2 (2k+2 – 3 ) + 1, k = 0, 1, 2, 3, …

“比較在希爾排序中是最主要的操作，而不是交換。”用這樣步長的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快，但是在涉及大量數(shù)據(jù)時希爾排序還是比快速排序慢。

2. 希爾排序的分析比較復(fù)雜，使用Hibbard’s 遞減步長序列的時間復(fù)雜度為O(N3/2)，平均時間復(fù)雜度大約為O(N5/4) ,具體的復(fù)雜度目前仍存在爭議。

3. 實驗表明，對于中型的序列( 萬)，希爾排序的時間復(fù)雜度接近最快的排序算法的時間復(fù)雜度nlogn。

4. 快速排序

原理：

快速排序的基本思想如下：

1. 對數(shù)組進(jìn)行隨機化。

2. 從數(shù)列中取出一個數(shù)作為中軸數(shù)(pivot)。

3. 將比這個數(shù)大的數(shù)放到它的右邊，小于或等于它的數(shù)放到它的左邊。

4. 再對左右區(qū)間重復(fù)第三步，直到各區(qū)間只有一個數(shù)。

操作可以分為以下5個步驟：

獲取中軸元素

1. i從左至右掃描，如果小于基準(zhǔn)元素，則i自增，否則記下a[i]

2. j從右至左掃描，如果大于基準(zhǔn)元素，則i自減，否則記下a[j]

3. 交換a[i]和a[j]

4. 重復(fù)這一步驟直至i和j交錯，然后和基準(zhǔn)元素比較，然后交換。

實現(xiàn)