排序算法基礎(chǔ)

排序算法蒂培，是一種能將一串?dāng)?shù)據(jù)按照特定的排序方式進(jìn)行排列的一種算法沙合，一個(gè)排序算法的好壞余境，主要從時(shí)間復(fù)雜度，空間復(fù)雜度灌诅，穩(wěn)定性來衡量。

時(shí)間復(fù)雜度

時(shí)間復(fù)雜度是一個(gè)函數(shù)含末，它描述了該算法的運(yùn)行時(shí)間猜拾，考察的是當(dāng)輸入值大小趨近無窮時(shí)的情況。數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用這個(gè)大 O 符號(hào)用來標(biāo)記不同”階“的無窮大佣盒。這里的無窮被認(rèn)為是一個(gè)超越邊界而增加的概念挎袜，而不是一個(gè)數(shù)。

想了解時(shí)間復(fù)雜度肥惭，我想講講常見的 O(1)盯仪，O(log n)，O(n)蜜葱，O(n log n)全景，O(n^2) ，計(jì)算時(shí)間復(fù)雜度的過程牵囤，常常需要分析一個(gè)算法運(yùn)行過程中需要的基本操作爸黄，計(jì)量所有操作的數(shù)量。

O（1）常數(shù)階

O（1）中的 1 并不是指時(shí)間為 1揭鳞，也不是操作數(shù)量為 1炕贵，而是表示操作次數(shù)為一個(gè)常數(shù)，不因?yàn)檩斎?n 的大小而改變野崇，比如哈希表里存放 1000 個(gè)數(shù)據(jù)或者 10000 個(gè)數(shù)據(jù)称开，通過哈希碼查找數(shù)據(jù)時(shí)所需要的操作次數(shù)都是一樣的，而操作次數(shù)和時(shí)間是成線性關(guān)系的，所以時(shí)間復(fù)雜度為 O（1）的算法所消耗的時(shí)間為常數(shù)時(shí)間鳖轰。

O（log n）對(duì)數(shù)階

O（log n）中的 log n 是一種簡(jiǎn)寫清酥，loga n 稱作為以 a 為底 n 的對(duì)數(shù)，log n 省略掉了 a脆霎，所以 log n 可能是 log2 n总处，也可能是 log10 n。但不論對(duì)數(shù)的底是多少睛蛛，O（log n）是對(duì)數(shù)時(shí)間算法的標(biāo)準(zhǔn)記法鹦马，對(duì)數(shù)時(shí)間是非常有效率的，例如有序數(shù)組中的二分查找忆肾，假設(shè) 1000 個(gè)數(shù)據(jù)查找需要 1 單位的時(shí)間荸频， 1000,000 個(gè)數(shù)據(jù)查找則只需要 2 個(gè)單位的時(shí)間，數(shù)據(jù)量平方了但時(shí)間只不過是翻倍了客冈。如果一個(gè)算法他實(shí)際的得操作數(shù)是 log2 n + 1000旭从， 那它的時(shí)間復(fù)雜度依舊是 log n， 而不是 log n + 1000场仲，時(shí)間復(fù)雜度可被稱為是漸近時(shí)間復(fù)雜度和悦，在 n 極大的情況，1000 相對(duì) 與 log2 n 是極小的渠缕，所以 log2 n + 1000 與 log2 n 漸進(jìn)等價(jià)鸽素。

O（n）線性階

如果一個(gè)算法的時(shí)間復(fù)雜度為 O(n)，則稱這個(gè)算法具有線性時(shí)間亦鳞，或 O(n) 時(shí)間馍忽。這意味著對(duì)于足夠大的輸入，運(yùn)行時(shí)間增加的大小與輸入成線性關(guān)系燕差。例如遭笋，一個(gè)計(jì)算列表所有元素的和的程序，需要的時(shí)間與列表的長度成正比徒探。遍歷無序數(shù)組尋最大數(shù)瓦呼，所需要的時(shí)間也與列表的長度成正比。

O（n log n）線性對(duì)數(shù)階

排序算法中的快速排序的時(shí)間復(fù)雜度即 O（n log n）测暗，它通過遞歸 log2n 次吵血，每次遍歷所有元素，所以總的時(shí)間復(fù)雜度則為二者之積偷溺， 復(fù)雜度既 O（n log n）蹋辅。

O（n^2）平方階

冒泡排序的時(shí)間復(fù)雜度既為 O（n^2），它通過平均時(shí)間復(fù)雜度為 O（n）的算法找到數(shù)組中最小的數(shù)放置在爭(zhēng)取的位置挫掏，而它需要尋找 n 次侦另，不難理解它的時(shí)間復(fù)雜度為 O（n^2）。時(shí)間復(fù)雜度為 O（n^2）的算法在處理大數(shù)據(jù)時(shí)，是非常耗時(shí)的算法褒傅，例如處理 1000 個(gè)數(shù)據(jù)的時(shí)間為 1 個(gè)單位的時(shí)間弃锐，那么 1000,000 數(shù)據(jù)的處理時(shí)間既大約 1000,000 個(gè)單位的時(shí)間。

時(shí)間復(fù)雜度又有最優(yōu)時(shí)間復(fù)雜度殿托，最差時(shí)間復(fù)雜度霹菊，平均時(shí)間復(fù)雜度。部分算法在對(duì)不同的數(shù)據(jù)進(jìn)行操作的時(shí)候支竹，會(huì)有不同的時(shí)間消耗旋廷，如快速排序，最好的情況是 O（n log n）礼搁，最差的情況是 O（n^2）饶碘，而平均復(fù)雜度就是所有情況的平均值，例如快速排序計(jì)算平均復(fù)雜度的公式為

時(shí)間復(fù)雜度效率比較

除了上述所說的時(shí)間復(fù)雜度馒吴，下表中展示了其他一些時(shí)間復(fù)雜度扎运，以及這些時(shí)間復(fù)雜度之間的比較。

想O(n^3)饮戳、O(n!)等這樣的時(shí)間復(fù)雜度豪治，過大的n會(huì)使算法變得不現(xiàn)實(shí)，都是時(shí)間的噩夢(mèng)扯罐，所以這種不切實(shí)際的復(fù)雜度负拟，一般都不會(huì)去考慮這樣的算法。

空間復(fù)雜度

和時(shí)間復(fù)雜度一樣篮赢，有 O(1)，O(log n)琉挖，O(n)启泣，O(n log n)，O(n^2)示辈，等等寥茫。實(shí)際寫代碼的過程中完全可以用空間來換取時(shí)間。比如判斷2017年之前的某一年是不是閏年矾麻，通成闯埽可以使通過一個(gè)算法來解決。但還有另外一種做法就是將2017年之前的閏年保存到一個(gè)數(shù)組中险耀。如果某一年存在這個(gè)數(shù)組中就是閏年弄喘，反之就不是。一般來說時(shí)間復(fù)雜度和空間復(fù)雜度是矛盾的甩牺。到底優(yōu)先考慮時(shí)間復(fù)雜度還是空間復(fù)雜度蘑志，取決于實(shí)際的應(yīng)用場(chǎng)景。

穩(wěn)定性

假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄急但，若經(jīng)過排序澎媒，這些記錄的相對(duì)次序保持不變，即在原序列中波桩，ri = rj戒努，且 ri 在 rj 之前，而在排序后的序列中镐躲，ri 仍在 rj 之前储玫，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的匀油。

當(dāng)相等的元素是無法分辨的缘缚，比如像是整數(shù)，穩(wěn)定性并不是一個(gè)問題敌蚜。然而桥滨，假設(shè)以下的數(shù)對(duì)將要以他們的第一個(gè)數(shù)字來排序。

(4, 1)  (3, 1)  (3, 7) （5, 6）

在這個(gè)狀況下弛车，有可能產(chǎn)生兩種不同的結(jié)果齐媒，一個(gè)是讓相等鍵值的紀(jì)錄維持相對(duì)的次序，而另外一個(gè)則沒有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  （維持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6)  （次序被改變）

不穩(wěn)定排序算法可能會(huì)在相等的鍵值中改變紀(jì)錄的相對(duì)次序纷跛，這導(dǎo)致我們無法準(zhǔn)確預(yù)料排序結(jié)果（除非你把數(shù)據(jù)在你的大腦里用該算法跑一遍）喻括，但是穩(wěn)定排序算法從來不會(huì)如此。例如冒泡排序即穩(wěn)定的存在贫奠，相等不交換則不打亂原有順序唬血。而快速排序有時(shí)候則是不穩(wěn)定的。

常見排序算法

本文介紹6種常用排序算法唤崭，包括冒泡拷恨、選擇、插入谢肾、快排腕侄、堆排、希爾排序芦疏。下面從排序算法的原理冕杠、解題步驟、實(shí)現(xiàn)代碼三個(gè)方面去介紹排序酸茴。

冒泡排序

原理解析

引自維基百科冒泡排序（英語：Bubble Sort）是一種簡(jiǎn)單的排序算法分预。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素薪捍，如果他們的順序錯(cuò)誤就把他們交換過來噪舀。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換魁淳，也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端与倡。

冒泡排序的理念十分簡(jiǎn)單：不斷比較相鄰的兩個(gè)元素界逛，如果它們的順序不符合要求就互相調(diào)換。

解題步驟

步驟如下：
* 比較相鄰的元素纺座。如果第一個(gè)比第二個(gè)大息拜，就交換他們兩個(gè)，直到把最大的元素放到數(shù)組尾部净响。
* 遍歷長度減一少欺，對(duì)剩下的元素從頭重復(fù)以上的步驟。
* 直到?jīng)]有任何一對(duì)數(shù)字需要比較時(shí)完成馋贤。

假如需要對(duì) 1 4 6 2 8 這五個(gè)數(shù)按照從大到小的排序進(jìn)行排列赞别，那么我們應(yīng)該怎么入手解決呢？

首先配乓，比較第 1 位數(shù)和第 2 位數(shù)的大小仿滔。很明顯 1 要小于 4，所以我們把 1 和 4 的位置互換一下犹芹。

然后崎页，我們繼續(xù)比較第 2位數(shù)和第 3 位數(shù)，發(fā)現(xiàn) 1 要小于 6腰埂，因此把 1 和 6 的位置互換飒焦。

繼續(xù)比較第 3 位和第 4 位數(shù)，1 要小于 2屿笼，根據(jù)要求把 1 和 2 的位置互換牺荠。

最后比較第 4 位和第 5 位數(shù)，顯然 1 小于 8驴一，同理把 1 和 8 的位置互換休雌。

經(jīng)過這樣一輪操作，我們已經(jīng)不知不覺中把數(shù)字 1 的位置放好了蛔趴，1 是這五個(gè)數(shù)字中數(shù)值最小的挑辆，應(yīng)該排在最后一位例朱。
我們回過頭來孝情，看看剛剛才的排序過程，1 的位置經(jīng)由交換慢慢“浮”到數(shù)列的頂端洒嗤，是不是很像氣泡上浮的過程箫荡，這也是冒泡排序算法這個(gè)名字的由來。

第一輪操作結(jié)束后渔隶，我們把五個(gè)數(shù)字中數(shù)值最小的 1 擺放好了羔挡。第二輪操作我們將會(huì)把五個(gè)數(shù)字中數(shù)值第二小的 2 擺放好洁奈。仔細(xì)想想這個(gè)規(guī)律，是不是很有意思绞灼？同樣按照第一輪的規(guī)則進(jìn)行操作利术，先比較第 1 位和第 2 位數(shù)，依此類推低矮，過程如下印叁。

實(shí)現(xiàn)代碼

func bubbleSort() {//冒泡排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {//找到符合條件的數(shù)進(jìn)行交換
        for j in i+1..<list.count {
            if list[j] > list[i] {
                let temp = list[j]
                list[j] = list[i]
                list[i] = temp
            }
        }
    }
    
    print(list)
}

最好的情況下，即待排序的數(shù)組本身是有序的军掂，比較的次數(shù)是 n-1 次轮蜕，沒有數(shù)據(jù)交換，時(shí)間復(fù)雜度為O(n)蝗锥。最壞的情況下跃洛，即待排序的數(shù)組是完全逆序的情況，此時(shí)需要比較 n*(n-1)/2 次终议。因此時(shí)間復(fù)雜度是O(n^2)汇竭。

選擇排序

原理解析

引自維基百科選擇排序（Selection sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下痊剖。首先在未排序序列中找到最泻妗（大）元素，存放到排序序列的起始位置陆馁，然后找颓，再從剩余未排序元素中繼續(xù)尋找最小（大）元素叮贩，然后放到已排序序列的末尾击狮。以此類推，直到所有元素均排序完畢益老。

選擇排序的基本思想就是通過 n-i 次關(guān)鍵字之間的比較彪蓬，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i個(gè)記錄做交換捺萌，而不是像冒泡排序那樣档冬，每一次比較之后，符合條件的都做一次交換桃纯。選擇排序相對(duì)于冒泡排序做的交換次數(shù)更少酷誓。

解題步驟

步驟如下：
* 遍歷數(shù)組，找到最小的元素态坦，將其置于數(shù)組起始位置盐数。
* 從上次最小元素存放的后一個(gè)元素開始遍歷至數(shù)組尾，將最小的元素置于開始處伞梯。
* 重復(fù)上述過程玫氢，直到元素排序完畢帚屉。

以數(shù)組 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 為例，先直觀看一下每一步的變化漾峡，后面再介紹細(xì)節(jié)

第一次從數(shù)組 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的數(shù) 0攻旦，放到數(shù)組的最前面（與第一個(gè)元素進(jìn)行交換）：

                               min
                                ↓
8   5   2   6   9   3   1   4   0   7
↑                               ↑
└───────────────────────────────┘

交換后：

0   5   2   6   9   3   1   4   8   7

在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的數(shù) 1漾唉，與該序列的第一個(gè)個(gè)元素進(jìn)行位置交換：

                       min
                        ↓
0   5   2   6   9   3   1   4   8   7
    ↑                   ↑
    └───────────────────┘

交換后：

0   1   2   6   9   3   5   4   8   7

在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的數(shù) 2谦铃，與該序列的第一個(gè)個(gè)元素進(jìn)行位置交換（實(shí)際上不需要交換）：

       min
        ↓
0   1   2   6   9   3   5   4   8   7
        ↑

重復(fù)上述過程，直到最后一個(gè)元素就完成了排序毒费。

                   min
                    ↓
0   1   2   6   9   3   5   4   8   7
            ↑       ↑
            └───────┘
                           min
                            ↓
0   1   2   3   9   6   5   4   8   7
                ↑           ↑
                └───────────┘
                       min
                        ↓
0   1   2   3   4   6   5   9   8   7
                    ↑   ↑
                    └───┘
                       min
                        ↓
0   1   2   3   4   5   6   9   8   7
                        ↑   
                                   min
                                    ↓
0   1   2   3   4   5   6   9   8   7
                            ↑       ↑
                            └───────┘  
                               min
                                ↓
0   1   2   3   4   5   6   7   8   9
                                ↑      
                                   min
                                    ↓
0   1   2   3   4   5   6   7   8   9
                                    ↑

實(shí)現(xiàn)代碼

func chooseSort() {//選擇排序
    var list = [61,5,33,44,22]
    for i in 0..<list.count {
        var min = i//記錄當(dāng)前最小的數(shù)牺陶，比較i+1后更大的數(shù)進(jìn)行記錄
        for j in i+1..<list.count {
            if list[j] < list[min] {
                min = j
            }
        }
        
        let temp = list[min]
        list[min] = list[i]
        list[i] = temp
    }
    
    print(list)
}

注意簡(jiǎn)單選擇排序中的數(shù)據(jù)交換是放在第一層for循環(huán)內(nèi)部伟阔，當(dāng)尋找到目標(biāo)下標(biāo)才進(jìn)行數(shù)據(jù)交換。而冒泡排序的數(shù)據(jù)交互是放在第二層for循環(huán)內(nèi)掰伸，因此排序相同的數(shù)據(jù)冒泡執(zhí)行的交換次數(shù)會(huì)大于或等于選擇排序皱炉。但是通過仔細(xì)分析時(shí)間復(fù)雜度可以得出，無論是在最好還是最差的情況下狮鸭，比較的次數(shù)都是n*(n-1)/2合搅。所以選擇排序的時(shí)間復(fù)雜度也是O(n^2)。雖然和冒泡排序的時(shí)間復(fù)雜度相等歧蕉，但簡(jiǎn)單選擇排序在性能上要略微優(yōu)于冒泡排序灾部。

插入排序

原理解析

引自維基百科插入排序（英語：Insertion Sort）是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過構(gòu)建有序序列惯退，對(duì)于未排序數(shù)據(jù)赌髓，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入催跪。插入排序在實(shí)現(xiàn)上锁蠕，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中懊蒸，需要反復(fù)把已排序元素逐步向后挪位荣倾，為最新元素提供插入空間。

它的工作原理是通過構(gòu)建有序序列骑丸，對(duì)于未排序數(shù)據(jù)舌仍，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入通危。

解題步驟

步驟如下：
* 從第一個(gè)元素開始铸豁，該元素可以認(rèn)為已經(jīng)被排序
* 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描
* 如果該元素（已排序）大于新元素黄鳍，將該元素移到下一位置
* 重復(fù)步驟3推姻，直到找到已排序的元素小于或者等于新元素的位置
* 將新元素插入到該位置后
* 重復(fù)步驟2~5

我們需要整理一個(gè)無序數(shù)組為［8平匈，3框沟，5藏古，4，6］忍燥。
取出第一個(gè)數(shù)字8拧晕，得到新的數(shù)組［8］。無序數(shù)組變?yōu)椋?梅垄，5厂捞，4，6］队丝。
取出第二個(gè)數(shù)字3靡馁，插入新的數(shù)組里，3比8小机久，得到［3臭墨，8］。無序數(shù)組變?yōu)椋?膘盖，4胧弛，6］。
取出第三個(gè)數(shù)字5侠畔，插入新的數(shù)組里结缚，5比3大，比8小软棺，得到［3红竭，5，8］喘落。無序數(shù)組變?yōu)椋?德崭，6］。
取出第四個(gè)數(shù)字4揖盘，插入新的數(shù)組里眉厨，4比3大，比5小兽狭，得到［3憾股，4，5箕慧，8］服球。無序數(shù)組變?yōu)椋?］。
最后取出6颠焦，插入新數(shù)組里斩熊，6比5大，比8小伐庭，得到［3粉渠，4分冈，5，6霸株，8］雕沉。排序完成。

我們可以將需要交換位置的數(shù)字直接向右移動(dòng)去件，然后將新的數(shù)字直接復(fù)制到正確的位置：

[ 3坡椒，5，8尤溜，4｜6 ]   記住4
          ＊

[ 3倔叼，5，8宫莱，8｜6 ]  將8轉(zhuǎn)移到右側(cè)
        -->

[ 3缀雳，5，5梢睛，8｜6 ]  將5轉(zhuǎn)移到右側(cè)
     -->

[ 3肥印，4，5绝葡，8｜6 ]  將4復(fù)制粘貼到新的位置
     ＊

實(shí)現(xiàn)代碼

func insertSort() {//插入排序
    var list = [61,5,33,44,22]
    
    var nlist = [list[0]]//建立一個(gè)空數(shù)深碱，符合條件的插入，沒插入的尾后添加
    for i in 1..<list.count {
        var max: Int? = nil
        for j in 0..<nlist.count {
            if list[i] > nlist[j] {
                max = i
                nlist.insert(list[i], at: j)
                break
            }
        }
        
        if max == nil {
            nlist.append(list[i])
        }
    }
    
    print(nlist)

}

func insertSortOne() {//插入排序 通過交換
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//從i往前找藏畅，符合條件交換
        
        while y>0 && list[y] > list[y-1] {
            let temp = list[y]
            list[y] = list[y-1]
            list[y-1] = temp
            y -= 1
        }
    }
    
    print(list)
    
}

func insertSortTwo() {//插入排序 通過移動(dòng)
    var list = [61,5,33,44,22]
    
    for i in 1..<list.count {
        var y = i//從i往前找敷硅，符合條件移動(dòng)
        let temp = list[y]
        while y>0 && temp > list[y-1] {
            list[y] = list[y-1]
            y -= 1
        }
        
        list[y] = temp//找到y(tǒng)賦值
    }
    
    print(list)
    
}

最好的情況下，完全沒有任何數(shù)據(jù)移動(dòng)愉阎，時(shí)間復(fù)雜度是O(n)绞蹦。最壞的情況下，比較的次數(shù)為 (n+2) * (n-1)/2榜旦，移動(dòng)的次數(shù)最大值為(n+4) * (n-1)/2幽七。如果按照序列的好壞程度是隨機(jī)的，且概率都是相同的溅呢，則平均比較次數(shù)以及平均移動(dòng)次數(shù)都約為 n^2/4次澡屡，所以時(shí)間復(fù)雜度為O(n ^ 2)。通過和冒泡以及簡(jiǎn)單選擇排序?qū)Ρ雀谰桑浑y看出直接插入排序的性能稍微比前兩者好上一些驶鹉。

對(duì)于插值排序算法來說，O(n^2)是它最差和平均性能表現(xiàn)铣墨。因?yàn)樗暮瘮?shù)里含有兩個(gè)循環(huán)室埋。其它類型的排序算法，比如快速排序和歸并排序，在輸入數(shù)據(jù)量很大的情況下姚淆，可以達(dá)到O(nlogn)的效果孕蝉。

插值排序?qū)τ谛?shù)據(jù)量的排序來說非常快肉盹。在一些標(biāo)準(zhǔn)程序庫里，如果數(shù)據(jù)大小不大于10疹尾，它們會(huì)用插值排序來取代快速排序上忍。

快速排序

原理解析

引自維基百科快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort）纳本，簡(jiǎn)稱快排窍蓝，一種排序算法，最早由東尼·霍爾提出繁成。在平均狀況下吓笙，排序n個(gè)項(xiàng)目要O(nlog n)次比較。在最壞狀況下則需要 O(n^2)次比較巾腕，但這種狀況并不常見面睛。事實(shí)上，快速排序O(nlog n)通常明顯比其他算法更快尊搬，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地達(dá)成叁鉴。

快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分佛寿，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小幌墓，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行冀泻，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列常侣。

解題步驟

步驟：
* 從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）弹渔，
* 重新排序數(shù)列胳施，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）肢专。在這個(gè)分區(qū)退出之后巾乳，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作鸟召。
* 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序胆绊。

實(shí)現(xiàn)從大到小排序，快排的思想就是從左向右查找欧募，比基準(zhǔn)小的交換到右邊區(qū)域压状，從右向左查找，比基準(zhǔn)大的交換到左邊區(qū)域。

也就是找到一個(gè)pivot种冬，從左向右查找镣丑，如果比基準(zhǔn)大的，繼續(xù)查找娱两，比基準(zhǔn)小的莺匠，記錄當(dāng)前位置，然后從右向左查找十兢，如果比基準(zhǔn)小的趣竣，繼續(xù)查找，比基準(zhǔn)大的旱物，記錄當(dāng)前位置遥缕，然后和左邊的記錄進(jìn)行交換，再把基準(zhǔn)數(shù)和中間數(shù)進(jìn)行交換宵呛，保證基準(zhǔn)在中間单匣，兩邊分的區(qū)大于或小于基準(zhǔn)。查找結(jié)束以左邊等于右邊的查找位置結(jié)束宝穗，然后繼續(xù)以上步驟繼續(xù)分區(qū)查找户秤。

根據(jù)下圖理解步驟

實(shí)現(xiàn)代碼

func quickSort(list: inout [Int], left: Int, right: Int) {
    if left > right {//左邊往右邊移，右邊往左邊移動(dòng)逮矛，最后過了就停止
        return
    }
    
    var i, j, pivot: Int
    
    i = left
    j = right
    pivot = list[left]
    
    while i != j {
        
        while list[j] <= pivot && i < j {//右邊大的往左移動(dòng)
            j -= 1
        }
        
        while list[i] >= pivot && i < j {//左邊小的往右移動(dòng)
            i += 1
        }
        
        if i < j {//找到兩個(gè)對(duì)方區(qū)域的值進(jìn)行交換
            let temp = list[i]
            list[i] = list[j]
            list[j] = temp
        }
    }
    
    list[left] = list[i]//此時(shí)i和j相等虎忌，處于中間位置，替換pivot值
    list[i] = pivot
    
    //重復(fù)以上動(dòng)作
    quickSort(list: &list, left: left, right: i-1)
    quickSort(list: &list, left: i+1, right: right)
}

快排的時(shí)間復(fù)雜度為時(shí)間復(fù)雜度 O(n log n)橱鹏。最差情況膜蠢，遞歸調(diào)用 n 次，即空間復(fù)雜度為 O(n)莉兰。最好情況挑围，遞歸調(diào)用 log n 次，空間復(fù)雜度為 O(log n)糖荒，空間復(fù)雜度一般看最差情況杉辙，時(shí)間可以平均，但空間一定得滿足捶朵，所以空間復(fù)雜度為 O(n)蜘矢。

當(dāng)待排序元素類似[6,1,3,7,3]且基準(zhǔn)元素為6時(shí)，經(jīng)過分區(qū)综看，形成[1,3,3,6,7],兩個(gè)3的相對(duì)位置發(fā)生了改變品腹，所是快速排序是一種不穩(wěn)定排序。

堆排序

原理解析

引自維基百科堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法红碑。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)舞吭，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)泡垃。

堆排序（Heap Sort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆是一個(gè)近似完全二叉樹的結(jié)構(gòu)羡鸥，并同時(shí)滿足堆性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)蔑穴。

解題步驟

步驟：
*   最大堆調(diào)整（Max_Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
*   創(chuàng)建最大堆（Build_Max_Heap）：將堆所有數(shù)據(jù)重新排序
*   堆排序（HeapSort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)惧浴，并做最大堆調(diào)整的遞歸運(yùn)算

通常堆是通過一維數(shù)組來實(shí)現(xiàn)的存和。在數(shù)組起始位置為0的情形中：

* 父節(jié)點(diǎn) i 的左子節(jié)點(diǎn)在位置 (2 * i + 1);
* 父節(jié)點(diǎn) i 的右子節(jié)點(diǎn)在位置 (2 * i + 2);
* 子節(jié)點(diǎn) i 的父節(jié)點(diǎn)在位置 floor((i - 1) / 2);

floor 函數(shù)的作用是向下取整，所以左子節(jié)點(diǎn)右子節(jié)點(diǎn)都能通過這個(gè)公式找到正確的父節(jié)點(diǎn)衷旅。

最大堆調(diào)整（MAX‐HEAPIFY）的作用是保持最大堆的性質(zhì)捐腿，是創(chuàng)建最大堆的核心子程序，作用過程如圖所示：

調(diào)整大頂堆的公式要準(zhǔn)守任意一個(gè)節(jié)點(diǎn)i可以實(shí)現(xiàn)：i>=2i+1芜茵，i>=2i+2叙量。也就是父節(jié)點(diǎn)大于等于左右兩個(gè)子節(jié)點(diǎn)倡蝙。

所以從小到大的排序思路是：把一堆數(shù)字調(diào)整成大頂堆-->堆頂元素和末尾元素交換-->去掉末尾元素九串，繼續(xù)大頂堆調(diào)整-->重復(fù)以上動(dòng)作

創(chuàng)建最大堆（Build-Max-Heap）的作用是將一個(gè)數(shù)組改造成一個(gè)最大堆，接受數(shù)組和堆大小兩個(gè)參數(shù)寺鸥，Build-Max-Heap 將自下而上的調(diào)用 Max-Heapify 來改造數(shù)組猪钮，建立最大堆。因?yàn)?Max-Heapify 能夠保證下標(biāo) i 的結(jié)點(diǎn)之后結(jié)點(diǎn)都滿足最大堆的性質(zhì)胆建，所以自下而上的調(diào)用 Max-Heapify 能夠在改造過程中保持這一性質(zhì)烤低。如果最大堆的數(shù)量元素是 n，那么 Build-Max-Heap 從 Parent(n) 開始笆载，往上依次調(diào)用 Max-Heapify扑馁。流程如下：

實(shí)現(xiàn)代碼

func heapSort(arr:inout Array<Int>) {
    //1.構(gòu)建大頂堆
    for i in (0...(arr.count/2-1)).reversed(){//從二叉樹的一邊的最后一個(gè)節(jié)點(diǎn)開始
        //從第一個(gè)非葉子結(jié)點(diǎn)從下至上，從右至左調(diào)整結(jié)構(gòu)
        adjustHeap(arr: &arr, i: i, length: arr.count)
    }
    //2.調(diào)整堆結(jié)構(gòu)+交換堆頂元素與末尾元素
    for j in (1...(arr.count-1)).reversed(){
        arr.swapAt(0, j)//將堆頂元素與末尾元素進(jìn)行交換
        adjustHeap(arr: &arr, i: 0, length: j)//重新對(duì)堆進(jìn)行調(diào)整
    }
}

/**
 * 調(diào)整大頂堆（僅是調(diào)整過程凉驻，建立在大頂堆已構(gòu)建的基礎(chǔ)上）
 */
func adjustHeap(arr:inout Array<Int>,i:Int,length:Int) {
    var i = i;
    let temp = arr[i];//先取出當(dāng)前元素i
    var k=2*i+1
    while k<length {//從i結(jié)點(diǎn)的左子結(jié)點(diǎn)開始腻要，也就是2i+1處開始
        if(k+1<length && arr[k]<arr[k+1]){//如果左子結(jié)點(diǎn)小于右子結(jié)點(diǎn)，k指向右子結(jié)點(diǎn)
            k+=1;
        }
        if(arr[k] > temp){//如果子節(jié)點(diǎn)大于父節(jié)點(diǎn)涝登，將子節(jié)點(diǎn)值賦給父節(jié)點(diǎn)（不用進(jìn)行交換）
            arr[i] = arr[k];
            i = k;//記錄當(dāng)前節(jié)點(diǎn)
        }else{
            break;
        }
        k=k*2+1//下一個(gè)節(jié)點(diǎn)
    }
    arr[i] = temp;//將temp值放到最終的位置
}

上述代碼中總過分為兩個(gè)for循環(huán)雄家。第一個(gè)for循環(huán)就是將現(xiàn)在的待排序序列構(gòu)建為一個(gè)最大堆，也就是maxHeap()函數(shù)的任務(wù)胀滚。第二個(gè)for循環(huán)就是逐步將每個(gè)最大值的根節(jié)點(diǎn)和末尾元素進(jìn)行交換趟济，然后再調(diào)整為最大堆。

在構(gòu)建堆的過程中咽笼，由于是是完全二叉樹從最下層最右邊非終端節(jié)點(diǎn)開始構(gòu)建顷编，將它與子節(jié)點(diǎn)進(jìn)行比較，對(duì)于每個(gè)非終端節(jié)點(diǎn)而言剑刑，最多進(jìn)行兩次比較和交換操作勾效，因此構(gòu)建堆的時(shí)間復(fù)雜度為O(n)。在整個(gè)排序過程中，第 i 次去堆頂記錄重建堆需要時(shí)間為logi ,并且需要取 n - 1次堆記錄层宫，所以重建對(duì)的時(shí)間復(fù)雜度為O(nlogn)杨伙。所以對(duì)的時(shí)間復(fù)雜度為O(nlogn)。
空間上只需一個(gè)暫存單元萌腿。由于記錄的比較是跳躍進(jìn)行的限匣，所以堆排序是一種不穩(wěn)定的排序。最后要提醒一點(diǎn)毁菱，由于初始構(gòu)建堆的所需的比較次數(shù)比較多米死。所以，一般不適合排序個(gè)數(shù)較少的數(shù)組贮庞。

希爾排序

原理解析

引自維基百科希爾排序峦筒，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本窗慎。希爾排序是非穩(wěn)定排序算法物喷。

希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：

• 插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高遮斥，即可以達(dá)到線性排序的效率
• 但插入排序一般來說是低效的峦失，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位

與插入排序通過對(duì)比相鄰的兩個(gè)元素的大小并在必要時(shí)候交換位置，希爾排序是通過比較相隔很遠(yuǎn)的兩個(gè)元素术吗。

兩個(gè)元素之間的距離稱為間隔尉辑。如果兩個(gè)元素在比較之后需要交換位置，則直接更換彼此的位置较屿。這個(gè)過程減少了插值排序中很多不必要的中間復(fù)制過程隧魄，即從兩個(gè)元素更換位置前需要不斷交換相鄰元素的位置直到目的位置。
這里的最主要的思想就是隘蝎，元素通過每次移動(dòng)較大間隔购啄，整個(gè)數(shù)組可以快速形成局部排序好的情況。這個(gè)會(huì)讓接下來的交換變得更加快速末贾。因?yàn)樵刂g不需要進(jìn)行過多次的位置交換闸溃。

一旦某一距離長度的間隔比值交換完成，間隔會(huì)變得越來越小拱撵，然后進(jìn)行相應(yīng)間隔的比值交換辉川，這樣的過程不斷重復(fù)，直到間隔為1拴测，也就是與插值排序同樣過程的情況乓旗。然而，在希爾排序中集索，由于大部分?jǐn)?shù)據(jù)在此時(shí)已經(jīng)整理完畢屿愚，所以最后間隔為1的比值交換速度非郴憧纾快。

解題步驟

步驟如下：
* 希爾排序是把記錄按下標(biāo)的一定增量分組妆距，對(duì)每組使用直接插入排序算法排序穷遂；
* 隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多娱据，當(dāng)增量減至1時(shí)蚪黑，整個(gè)文件恰被分成一組，算法便終止中剩。

以n=10的一個(gè)數(shù)組49, 38, 65, 97, 26, 13, 27, 49, 55, 4為例

第一次增量 gap = 10 / 2 = 5

49   38   65   97   26   13   27   49   55   4

1A                       1B

     2A                       2B

          3A                       3B

               4A                       4B

                    5A                       5B

1A,1B忌穿，2A,2B等為分組標(biāo)記，數(shù)字相同的表示在同一組结啼，大寫字母表示是該組的第幾個(gè)元素掠剑， 每次對(duì)同一組的數(shù)據(jù)進(jìn)行直接插入排序。即分成了五組(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)這樣每組排序后就變成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)郊愧，下同朴译。

第二次增量 gap = 5 / 2 = 2

13   27   49   55   4    49   38   65   97   26

1A        1B        1C        1D        1E

     2A        2B        2C        2D        2E

第三次增量 gap = 2 / 2 = 1

4   26   13   27   38    49   49   55   97   65

1A  1B   1C   1D   1E    1F   1G   1H   1I   1J

第四次增量 gap = 1 / 2 = 0 排序完成得到數(shù)組：

4   13   26   27   38    49   49   55   65   97

實(shí)現(xiàn)代碼

func shellSort(arr: inout [Int]) {//希爾排序
    var j: Int
    var gap = arr.count / 2//獲取增量
    
    while  gap > 0 {
        for i in 0 ..< gap {
            j = i + gap
            while j < arr.count {
                if arr[j] < arr[j - gap] {
                    let temp = arr[j]
                    var k = j - gap
                    while (k >= 0 && arr[k] > temp) {//插入排序
                        arr[k + gap] = arr[k]
                        k -= gap
                    }
                    arr[k + gap] = temp
                }
                
                j += gap
            }
            
        }
        gap /= 2//增量減半
    }
}

• 希爾排序時(shí)間復(fù)雜度
  希爾排序的時(shí)間復(fù)雜度與增量(即，步長gap)的選取有關(guān)糕珊。例如动分，當(dāng)增量為1時(shí)毅糟，希爾排序退化成了直接插入排序红选，此時(shí)的時(shí)間復(fù)雜度為O(N2)，而Hibbard增量的希爾排序的時(shí)間復(fù)雜度為O(N3/2)姆另。

• 希爾排序穩(wěn)定性
  希爾排序是不穩(wěn)定的算法喇肋，它滿足穩(wěn)定算法的定義。對(duì)于相同的兩個(gè)數(shù)迹辐，可能由于分在不同的組中而導(dǎo)致它們的順序發(fā)生變化蝶防。
  算法穩(wěn)定性 -- 假設(shè)在數(shù)列中存在a[i]=a[j]，若在排序之前明吩，a[i]在a[j]前面间学；并且排序之后，a[i]仍然在a[j]前面印荔。則這個(gè)排序算法是穩(wěn)定的低葫！