我們將會詳細(xì)的介紹冒泡排序、插入排序、希爾排序以及選擇排序，下篇博客將繼續(xù)介紹堆排序、歸并排序以及快速排序的相關(guān)內(nèi)容。當(dāng)然上述內(nèi)容的代碼實(shí)現(xiàn)我們依然采用Swift面向?qū)ο笳Z言來實(shí)現(xiàn)。
本篇的思路與以往博客的思路一直，先分析每種排序的規(guī)則，然后給出原理示意圖，最后根據(jù)示意圖給出相應(yīng)的代碼實(shí)現(xiàn)。編程這東西，只要是思路清晰，給出相應(yīng)的代碼實(shí)現(xiàn)并不困難，本篇是使用Swift語言來實(shí)現(xiàn)的，如果你對Swift語言不熟悉，你可以選擇其他你熟悉的語言來實(shí)現(xiàn)。雖然語言不同，但是思路和方法都是一樣的。廢話少說，開始今天博客的主題。
一、排序協(xié)議的定義
在博客的開頭的，我們先給出排序協(xié)議的定義。因?yàn)槲覀儽酒┛秃卸喾N排序方式，為了使每種排序方法對外調(diào)用方式一致，我們需要定義一個(gè)排序的相關(guān)協(xié)議。所有排序的相關(guān)類都必須遵循該協(xié)議，讓此協(xié)議來定義具體的排序類對外的調(diào)用方式。
下方的SortType協(xié)議就是我們定義的排序類型的協(xié)議。其中的sort()方法是遵循該協(xié)議的類必須要實(shí)現(xiàn)的方法。sort()函數(shù)的參數(shù)是一個(gè)含有Int類型的數(shù)組，該數(shù)組就是要排序的數(shù)組。該方法的返回值是已經(jīng)被排好序的數(shù)組。具體代碼如下所示。
** 二、冒泡排序**
接下來我們來聊一下冒泡排序，冒泡排序就像其名字一樣，還是比較生動的。在冒泡排序過程中會將數(shù)組分成兩部分，一部分是已經(jīng)有序的數(shù)列，一部分是無序的數(shù)列。無序數(shù)列中不斷的將其中最小的值往有序序列中冒泡，泡冒完后，我們的序列就創(chuàng)建好了。本部分，我們將要給出冒泡排序的示意圖，已經(jīng)相應(yīng)的代碼實(shí)現(xiàn)。
1、冒泡排序示意圖
下方就是第一輪冒泡的具體過程，我們要對[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]序列進(jìn)行冒泡排序。經(jīng)過第一輪的冒泡后，該序列中最小的值35被冒到了數(shù)列的最前方。因?yàn)槊芭莸倪^程是<typo id="typo-802" data-origin="挨個(gè)" ignoretag="true">挨個(gè)</typo>比較已經(jīng)交換的過程。元素狀態(tài)我們的泡中是93，93與前一個(gè)值37進(jìn)行比較，發(fā)現(xiàn)37要小于93，所以將泡中的值改成37，并往前移動。緊接著37在與前面的99比較，發(fā)現(xiàn)泡中的值要小，此刻不更新泡中的值并往前移動一個(gè)格。以此類推，無序序列中最小的值就會被冒到序列的起始位置。
每輪冒泡都會從無序序列中冒出那個(gè)最小的值，所以經(jīng)過n(數(shù)列有n個(gè)值)次冒泡后，我們的數(shù)列就是有序的了。冒泡過程中的比較與交換的具體步驟如下所示：
2.代碼實(shí)現(xiàn)
根據(jù)上述示意圖，我們很容易給出下方的代碼。下方就是冒泡排序的代碼，BubbleSort這個(gè)類就是冒泡排序所對應(yīng)的類，此類為了統(tǒng)一對外的調(diào)用方式，所以必須要遵循我們上一部分所定義的SortType協(xié)議。
說白了，冒泡的過程就是不斷比較和交換的過程，如果前一個(gè)值比后一個(gè)值要大，那么就要進(jìn)行交換了
3、運(yùn)行結(jié)果
下方代碼就是上述BubbleSort類所運(yùn)行的具體結(jié)果。排序結(jié)果中詳細(xì)的打印了冒泡排序在每一輪冒泡中每一步要做的事情，具體如下所示。
三、插入排序
插入排序算是比較好理解的排序方式，插入排序也是將要排序的數(shù)列分為兩部分，前半部分是已經(jīng)排好序的，后半部分則是無序的。插入排序中的插入是指“取出無序數(shù)列中第一個(gè)值，插入到有序數(shù)列中相應(yīng)的位置”。其實(shí)這個(gè)插入過程也是不斷比較和交換的過程。
1、插入排序示意圖
下方就是插入排序的示意圖，紅色部分是有序數(shù)列，而綠色部分是無序數(shù)列。每一輪插入都會取出無序數(shù)列中的第一個(gè)元素插入到有序數(shù)列中，這個(gè)插入的過程其實(shí)就是一個(gè)比較交換的過程，如果要插入的值比前面的值要小，就要交換，直到不能交換為止。下方就是插入排序的過程。具體如下所示：
2、代碼實(shí)現(xiàn)
有了上述的示意圖，給出相應(yīng)的代碼實(shí)現(xiàn)并不困難。代碼的核心思想就是通過循序不斷從無序數(shù)列中取出值，然后循環(huán)遍歷有序數(shù)列尋找合適的插入點(diǎn)。在下方中有兩個(gè)循環(huán)嵌套，外層循環(huán)負(fù)責(zé)不斷從無序序列中取值，然后通過內(nèi)層循環(huán)將外層循環(huán)取出的值插入到有序數(shù)列中相應(yīng)的位置，具體如下代碼所示：
3、運(yùn)行結(jié)果
下方是運(yùn)行結(jié)果的截圖，該運(yùn)行結(jié)果其實(shí)就是插入排序的詳細(xì)過程。每一輪插入的過程就是有序序列增加，無序序列減少的過程。下方就是插入過程的詳細(xì)信息。
四、希爾排序
因?yàn)檫@個(gè)排序是一個(gè)叫希爾的人發(fā)明的，所以就叫希爾排序了。其實(shí)希爾排序是插入排序的升級版， 希爾排序根據(jù)其排序的特點(diǎn)又叫做縮小增量排序。希爾排序的大體步驟就是先將無序序列按照一定的步長（增量）分為幾組，分別將這幾組中的數(shù)據(jù)通過插入排序的方式將其進(jìn)行排序。然后縮小步長（增量）分組，然后將組內(nèi)的數(shù)據(jù)再次進(jìn)行排序。知道增量為1位置。經(jīng)過上述這些步驟，我們的序列就是有序的了。其實(shí)上述的插入排序就是增量為1的希爾排序，下方會給出相應(yīng)的示意圖以及代碼實(shí)現(xiàn)。
1.希爾排序示意圖
下方就是希爾排序的詳細(xì)步驟，接下來我們將會對每一步進(jìn)行詳細(xì)的解說。如下所示：
- (1)、首先按照增量進(jìn)行分組，因?yàn)槲覀円判虻臄?shù)列有11個(gè)，增量初始值是step = 11 / 2 = 5。也就是按照增量為5的步長對數(shù)組進(jìn)行分組。在下方第一步中就是按照增量為5的方式進(jìn)行分組的。我們將為一組的元素使用直線進(jìn)行相連，分完組后，我們就將組內(nèi)中的元素進(jìn)行插入排序。
- (2)、將上一步使用的增量進(jìn)行縮小，也就是本步驟的step = 5 / 2 = 2。 本部分，就要按照2的增量將上一步排序后的數(shù)組進(jìn)行分組，然后再次將每個(gè)組內(nèi)的數(shù)據(jù)進(jìn)行插入排序。
- (3)、再次縮小增量，此刻step = 2 / 2 = 1, 當(dāng)增量為1時(shí)，其實(shí)就是我們上一部分的插入排序。將整個(gè)數(shù)組進(jìn)行插入排序，然后我們的數(shù)組就是有序的了。
具體示意圖如下所示：
2、希爾排序的代碼實(shí)現(xiàn)
根據(jù)上述的步驟，然后再結(jié)合著插入排序的代碼，給出希爾排序相應(yīng)的代碼并不困難。就是將插入排序的步長從1修改成我們每次生成的步長即可，每次增量排序完畢后，我們要對增量按照相應(yīng)的規(guī)則進(jìn)行縮小即可。下方就是希爾排序的代碼實(shí)現(xiàn)。
在下方代碼中，最外層循環(huán)負(fù)責(zé)增量的生成和縮減，里邊的雙重循環(huán)就是我們之前我們插入排序的代碼，不步長要使用我們希爾排序生成的step，具體代碼如下所示：
3、運(yùn)行結(jié)果
下方就是Shell排序的運(yùn)行結(jié)果，從下方結(jié)果中我們不難看出增量是逐漸減小的。下方的輸出結(jié)果結(jié)合著本部分第一部分的示意圖看更為直觀一些。
** 五、選擇排序**
接下來來聊聊選擇排序，選擇排序也是比較好理解的。在選擇排序過程中，數(shù)組仍然被分作有序和無序兩部分。而選擇排序中的“選擇”是指不斷從無序序列中選擇最小的值放入到有序序列的最后的位置，換句話說就是從現(xiàn)有的無序序列中找出那個(gè)最小的值，然后與無序序列的第一個(gè)值進(jìn)行交換，然后縮小無序序列的范圍即可。因?yàn)橛行蛐蛄械淖詈笠粋€(gè)值與無序序列的第一個(gè)值緊挨著，交換后，這個(gè)無序序列中的第一個(gè)值就成了有序序列的最后一個(gè)值。重復(fù)這個(gè)選擇的過程，我們的數(shù)組就會變得有序。下方將會給出詳細(xì)的示意圖以及相應(yīng)的代碼實(shí)現(xiàn)。
**1.選擇排序示意圖 **
下方就是簡單選擇排序的部分步驟，只需要重復(fù)下方的步驟就可以通過選擇排序?qū)⑽覀兊臄?shù)組變成有序的序列。下方是對下方步驟的詳細(xì)介紹：
- 初識狀態(tài)下，我們整個(gè)數(shù)組就是無序的，從整個(gè)數(shù)組中我們找到了最小的元素35，其下標(biāo)為5。然后將35與無序序列第一個(gè)元素62進(jìn)行交換。交換后，有序序列中就有了一個(gè)值：35，而無序序列中就少了一個(gè)值：35。無序序列中的第一個(gè)值也就是變成了88。
- 再次從無序序列中選擇那個(gè)最小的值。于是乎我們又找到了37，然后讓37與88進(jìn)行交換。有序序列就成了{(lán)35，37}。
- 再次從無序序列中選擇最小的那個(gè)值，經(jīng)過查找我們找到了47，然后將47與58進(jìn)行交換。此刻有序序列就成了{(lán)35, 37, 47}。
- 重復(fù)的從無序序列中選擇最小的值進(jìn)行交換......
2.選擇排序具體代碼實(shí)現(xiàn)
有了上述選擇的示意圖，根據(jù)思路敲代碼。下方就是選擇排序的具體代碼實(shí)現(xiàn)。代碼實(shí)現(xiàn)起來還是比較簡單的，就是通過一個(gè)循環(huán)，不斷的從無序序列中選出那個(gè)最小的值與無序序列中的第一個(gè)值進(jìn)行交換即可。下方第一個(gè)框中就是從無序序列中查找最小的那個(gè)值的代碼，第二個(gè)框就是交換的過程。如下所示：
3、運(yùn)行結(jié)果
與上幾個(gè)排序一樣，我們輸出的運(yùn)行結(jié)果就是選擇排序的詳細(xì)的過程。下方就是選擇排序的詳細(xì)過程，如下所示：
六、測試用例
在博客要結(jié)尾的部分，我們?nèi)匀粫o出本篇博客所使用的測試用例。下方就是本篇博客所使用的測試用例。上述的運(yùn)行結(jié)果就是下方我們測試用例的輸出結(jié)果。雖然輸出的結(jié)果不同，但是我們用的都是一個(gè)測試函數(shù)，只是傳入的排序?qū)ο蟛煌?。這也就是我們在程序的第一部分為什么要給出相應(yīng)的協(xié)議定義的原因。測試用例如下所示：
