1. 簡(jiǎn)介
排序與我們?nèi)粘Ｉ钪邢⑾⑾嚓P(guān)击费，比如，我們要從電話簿中找到某個(gè)聯(lián)系人首先會(huì)按照姓氏排序笔咽、買(mǎi)火車(chē)票會(huì)按照出發(fā)時(shí)間或者時(shí)長(zhǎng)排序搔预、買(mǎi)東西會(huì)按照銷(xiāo)量或者好評(píng)度排序、查找文件會(huì)按照修改時(shí)間排序等等叶组。在計(jì)算機(jī)程序設(shè)計(jì)中拯田，排序和查找也是最基本的算法，很多其他的算法都是以排序算法為基礎(chǔ)甩十，在一般的數(shù)據(jù)處理或分析中船庇，通常第一步就是進(jìn)行排序，比如說(shuō)二分查找侣监，首先要對(duì)數(shù)據(jù)進(jìn)行排序
排序的算法有很多鸭轮，在維基百科上有這么一個(gè)分類(lèi)，另外大家有興趣也可以直接上維基百科上看相關(guān)算法
2. 選擇排序
原理
選擇排序很簡(jiǎn)單橄霉，他的步驟如下：
1. 從左至右遍歷窃爷，找到最小(大)的元素，然后與第一個(gè)元素交換。
2. 從剩余未排序元素中繼續(xù)尋找最邪蠢濉（大）元素医吊，然后與第二個(gè)元素進(jìn)行交換。
3. 以此類(lèi)推逮京，直到所有元素均排序完畢卿堂。
之所以稱之為選擇排序，是因?yàn)槊恳淮伪闅v未排序的序列我們總是從中選擇出最小的元素懒棉。
實(shí)現(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
```
*選擇排序需要花費(fèi) (N – 1) + (N – 2) + … + 1 + 0 = N(N- 1) / 2 ~ N2/2次比較 和 N-1次交換操作草描。
*對(duì)初始數(shù)據(jù)不敏感，不管初始的數(shù)據(jù)有沒(méi)有排好序漓藕，都需要經(jīng)歷N2/2次比較陶珠，這對(duì)于一些原本排好序，或者近似排好序的序列來(lái)說(shuō)并不具有優(yōu)勢(shì)享钞。在最好的情況下揍诽，即所有的排好序，需要0次交換栗竖，最差的情況暑脆，倒序，需要N-1次交換狐肢。
*數(shù)據(jù)交換的次數(shù)較少添吗，如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)份名。在最差情況下也只需要進(jìn)行N-1次數(shù)據(jù)交換碟联，在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诒容^好的一種僵腺。
3. 插入排序
原理
插入排序也是一種比較直觀的排序方式鲤孵。可以以我們平常打撲克牌為例來(lái)說(shuō)明辰如，假設(shè)我們那在手上的牌都是排好序的普监，那么插入排序可以理解為我們每一次將摸到的牌，和手中的牌從左到右依次進(jìn)行對(duì)比琉兜，如果找到合適的位置則直接插入凯正。具體的步驟為：
1. 從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序
2. 取出下一個(gè)元素豌蟋，在已經(jīng)排序的元素序列中從后向前掃描
3. 如果該元素小于前面的元素（已排序）廊散，則依次與前面元素進(jìn)行比較如果小于則交換，直到找到大于該元素的就則停止梧疲；
4. 如果該元素大于前面的元素（已排序）奸汇，則重復(fù)步驟2
5. 重復(fù)步驟2~4 直到所有元素都排好序
實(shí)現(xiàn)
3. 希爾排序
原理：
希爾排序也稱之為遞減增量排序施符，他是對(duì)插入排序的改進(jìn)。在第二部插入排序中擂找，我們知道，插入排序?qū)τ诮埔雅藕眯虻男蛄衼?lái)說(shuō)浩销，效率很高贯涎，可以達(dá)到線性排序的效率。但是插入排序效率也是比較低的慢洋，他一次只能將數(shù)據(jù)向前移一位塘雳。比如如果一個(gè)長(zhǎng)度為N的序列，最小的元素如果恰巧在末尾普筹，那么使用插入排序仍需一步一步的向前移動(dòng)和比較败明，要N-1次比較和交換。
希爾排序通過(guò)將待比較的元素劃分為幾個(gè)區(qū)域來(lái)提升插入排序的效率太防。這樣可以讓元素可以一次性的朝最終位置邁進(jìn)一大步妻顶，然后算法再取越來(lái)越小的步長(zhǎng)進(jìn)行排序，最后一步就是步長(zhǎng)為1的普通的插入排序的蜒车，但是這個(gè)時(shí)候讳嘱，整個(gè)序列已經(jīng)是近似排好序的，所以效率高酿愧。
實(shí)現(xiàn)：
可以看到沥潭，希爾排序的實(shí)現(xiàn)是在插入排序的基礎(chǔ)上改進(jìn)的，插入排序的步長(zhǎng)為1嬉挡，每一次遞減1钝鸽，希爾排序的步長(zhǎng)為我們定義的h，然后每一次和前面的-h位置上的元素進(jìn)行比較庞钢。算法中拔恰，我們首先獲取小于N/3 的最大的步長(zhǎng)，然后逐步長(zhǎng)遞減至步長(zhǎng)為1的一般的插入排序焊夸。
分析：
1. 希爾排序的關(guān)鍵在于步長(zhǎng)遞減序列的確定仁连，任何遞減至1步長(zhǎng)的序列都可以，目前已知的比較好的序列有：
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, ….
該序列由下面兩個(gè)表達(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, …
“比較在希爾排序中是最主要的操作，而不是交換揪阶〔伲”用這樣步長(zhǎng)的希爾排序比插入排序和堆排序都要快，甚至在小數(shù)組中比快速排序還快鲁僚，但是在涉及大量數(shù)據(jù)時(shí)希爾排序還是比快速排序慢炊苫。
2. 希爾排序的分析比較復(fù)雜裁厅，使用Hibbard’s 遞減步長(zhǎng)序列的時(shí)間復(fù)雜度為O(N3/2)，平均時(shí)間復(fù)雜度大約為O(N5/4) ,具體的復(fù)雜度目前仍存在爭(zhēng)議侨艾。
3. 實(shí)驗(yàn)表明执虹，對(duì)于中型的序列( 萬(wàn))，希爾排序的時(shí)間復(fù)雜度接近最快的排序算法的時(shí)間復(fù)雜度nlogn唠梨。
4. 快速排序
原理：
快速排序的基本思想如下：
1. 對(duì)數(shù)組進(jìn)行隨機(jī)化袋励。
2. 從數(shù)列中取出一個(gè)數(shù)作為中軸數(shù)(pivot)。
3. 將比這個(gè)數(shù)大的數(shù)放到它的右邊当叭，小于或等于它的數(shù)放到它的左邊茬故。
4. 再對(duì)左右區(qū)間重復(fù)第三步，直到各區(qū)間只有一個(gè)數(shù)蚁鳖。
操作可以分為以下5個(gè)步驟：
獲取中軸元素
1. i從左至右掃描磺芭，如果小于基準(zhǔn)元素，則i自增醉箕，否則記下a[i]
2. j從右至左掃描钾腺，如果大于基準(zhǔn)元素，則i自減琅攘，否則記下a[j]
3. 交換a[i]和a[j]
4. 重復(fù)這一步驟直至i和j交錯(cuò)垮庐，然后和基準(zhǔn)元素比較，然后交換坞琴。
實(shí)現(xiàn)
