編排 |?strongerHuang 微信公眾號(hào)：strongerHuang

如果說各種編程語言是程序員的招式，那么數(shù)據(jù)結(jié)構(gòu)和算法就相當(dāng)于程序員的內(nèi)功。

想寫出精煉、優(yōu)秀的代碼，不通過不斷的錘煉，是很難做到的。

一、排序算法

排序算法作為數(shù)據(jù)結(jié)構(gòu)的重要部分，系統(tǒng)地學(xué)習(xí)一下是很有必要的。

1、排序的概念

排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序”的記錄序列調(diào)整為“有序”的記錄序列。

排序分為內(nèi)部排序和外部排序。

若整個(gè)排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序。

反之，若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。

2、排序分類

八大排序算法均屬于內(nèi)部排序。如果按照策略來分類，大致可分為：交換排序、插入排序、選擇排序、歸并排序和基數(shù)排序。如下圖所示：

3、算法分析 A.插入排序 *直接插入排序 *希爾排序 B.選擇排序 *簡單選擇排序 *堆排序 C.交換排序 *冒泡排序 *快速排序 D.歸并排序 E.基數(shù)排序 不穩(wěn)定排序：簡單選擇排序，快速排序，希爾排序，堆排序 穩(wěn)定排序：冒泡排序，直接插入排序，歸并排序，基數(shù)排序

進(jìn)一步描述八大排序：

①插入排序

將第一個(gè)和第二個(gè)元素排好序，然后將第3個(gè)元素插入到已經(jīng)排好序的元素中，依次類推（插入排序最好的情況就是數(shù)組已經(jīng)有序了）。

②希爾排序

因?yàn)椴迦肱判蛎看沃荒懿僮饕粋€(gè)元素，效率低。元素個(gè)數(shù)N，取奇數(shù)k=N/2，將下標(biāo)差值為k的數(shù)分為一組（一組元素個(gè)數(shù)看總元素個(gè)數(shù)決定），在組內(nèi)構(gòu)成有序序列，再取k=k/2，將下標(biāo)差值為k的數(shù)分為一組，構(gòu)成有序序列，直到k=1，然后再進(jìn)行直接插入排序。

③簡單選擇排序

選出最小的數(shù)和第一個(gè)數(shù)交換，再在剩余的數(shù)中又選擇最小的和第二個(gè)數(shù)交換，依次類推。

④堆排序

以升序排序?yàn)槔?，利用小根堆的性質(zhì)（堆頂元素最?。┎粩噍敵鲎钚≡?，直到堆中沒有元素

1.構(gòu)建小根堆

2.輸出堆頂元素

3.將堆低元素放一個(gè)到堆頂，再重新構(gòu)造成小根堆，再輸出堆頂元素，以此類推。

⑤冒泡排序

改進(jìn)1：如果某次冒泡不存在數(shù)據(jù)交換，則說明已經(jīng)排序好了，可以直接退出排序

改進(jìn)2：頭尾進(jìn)行冒泡，每次把最大的沉底，最小的浮上去，兩邊往中間靠1

⑥快速排序

選擇一個(gè)基準(zhǔn)元素，比基準(zhǔn)元素小的放基準(zhǔn)元素的前面，比基準(zhǔn)元素大的放基準(zhǔn)元素的后面，這種動(dòng)作叫分區(qū)，每次分區(qū)都把一個(gè)數(shù)列分成了兩部分，每次分區(qū)都使得一個(gè)數(shù)字有序，然后將基準(zhǔn)元素前面部分和后面部分繼續(xù)分區(qū)，一直分區(qū)直到分區(qū)的區(qū)間中只有一個(gè)元素的時(shí)候，一個(gè)元素的序列肯定是有序的嘛，所以最后一個(gè)升序的序列就完成啦。

⑦歸并排序

將一個(gè)無序的數(shù)列一直一分為二，直到分到序列中只有一個(gè)數(shù)的時(shí)候，這個(gè)序列肯定是有序的，因?yàn)橹挥幸粋€(gè)數(shù)，然后將兩個(gè)只含有一個(gè)數(shù)字的序列合并為含有兩個(gè)數(shù)字的有序序列，這樣一直進(jìn)行下去，最后就變成了一個(gè)大的有序數(shù)列

⑧基數(shù)排序

找到最大的數(shù)，開個(gè)比最大的數(shù)大一點(diǎn)的數(shù)組，遍歷每個(gè)元素，某個(gè)元素為k，則a[k]++,最好遍歷數(shù)組a，a[k]等于多少就輸出多少個(gè)k。只能處理整型數(shù)。

三、詳解八大排序算法

1.插入排序

直接插入排序的核心思想就是：將數(shù)組中的所有元素依次跟前面已經(jīng)排好的元素相比較，如果選擇的元素比已排序的元素小，則交換，直到全部元素都比較過。

因此，從上面的描述中我們可以發(fā)現(xiàn)，直接插入排序可以用兩個(gè)循環(huán)完成：

第一層循環(huán)：遍歷待比較的所有數(shù)組元素。

第二層循環(huán)：將本輪選擇的元素(selected)與已經(jīng)排好序的元素(ordered)相比較。如果：selected > ordered，那么將二者交換。

2.希爾排序

希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。

希爾排序的基本思想是：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行依次直接插入排序。

算法步驟：

a.選擇一個(gè)增量序列t1，t2，…，tk，其中ti>tj，tk=1；

b.按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k 趟排序；

c.每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1 時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。

3.簡單選擇排序

簡單選擇排序的實(shí)現(xiàn)思想：比較+交換

從待排序序列中，找到關(guān)鍵字最小的元素；

如果最小元素不是待排序序列的第一個(gè)元素，將其和第一個(gè)元素互換；

從余下的 N - 1 個(gè)元素中，找出關(guān)鍵字最小的元素，重復(fù)(1)、(2)步，直到排序結(jié)束。因此我們可以發(fā)現(xiàn)，簡單選擇排序也是通過兩層循環(huán)實(shí)現(xiàn)。第一層循環(huán)：依次遍歷序列當(dāng)中的每一個(gè)元素 第二層循環(huán)：將遍歷得到的當(dāng)前元素依次與余下的元素進(jìn)行比較，符合最小元素的條件，則交換。

4.堆排序

堆：本質(zhì)是一種數(shù)組對(duì)象。特別重要的一點(diǎn)性質(zhì)：任意的葉子節(jié)點(diǎn)小于（或大于）它所有的父節(jié)點(diǎn)。對(duì)此，又分為大頂堆和小頂堆：

大頂堆要求節(jié)點(diǎn)的元素都要大于其孩子。

小頂堆要求節(jié)點(diǎn)元素都小于其左右孩子。

兩者對(duì)左右孩子的大小關(guān)系不做任何要求。

利用堆排序，就是基于大頂堆或者小頂堆的一種排序方法。下面，我們通過大頂堆來實(shí)現(xiàn)。

基本思想：堆排序可以按照以下步驟來完成：

a.首先將序列構(gòu)建稱為大頂堆；（這樣滿足了大頂堆那條性質(zhì)：位于根節(jié)點(diǎn)的元素一定是當(dāng)前序列的最大值）。

b.取出當(dāng)前大頂堆的根節(jié)點(diǎn)，將其與序列末尾元素進(jìn)行交換；（此時(shí)：序列末尾的元素為已排序的最大值；由于交換了元素，當(dāng)前位于根節(jié)點(diǎn)的堆并不一定滿足大頂堆的性質(zhì)）。

c.對(duì)交換后的n-1個(gè)序列元素進(jìn)行調(diào)整，使其滿足大頂堆的性質(zhì)。

d.重復(fù)2.3步驟，直至堆中只有1個(gè)元素為止。

5.冒泡排序

算法思想：冒泡遍歷所有的數(shù)據(jù)，每次對(duì)相鄰元素進(jìn)行兩兩比較，如果順序和預(yù)先規(guī)定的順序不一致，則進(jìn)行位置交換；這樣一次遍歷會(huì)將最大或最小的數(shù)據(jù)上浮到頂端，之后再重復(fù)同樣的操作，直到所有的數(shù)據(jù)有序。這個(gè)算法的名字由來是因?yàn)樵酱蟮脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

6.快速排序

快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個(gè)項(xiàng)目要Ο(n logn)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實(shí)上，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來

快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）。

算法步驟：

a.從數(shù)列中挑出一個(gè)元素，稱為 “基準(zhǔn)”（pivot）。

b.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作。

c.遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞歸下去，但是這個(gè)算法總會(huì)退出，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

7.歸并排序 歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。
算法步驟： a. 申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列；
b. 設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置；
c. 比較兩個(gè)指針?biāo)赶虻脑?，選擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置；
d. 重復(fù)步驟3直到某一指針達(dá)到序列尾；
e. 將另一序列剩下的所有元素直接復(fù)制到合并序列尾。

8.基數(shù)排序

基數(shù)排序：通過序列中各個(gè)元素的值，對(duì)排序的N個(gè)元素進(jìn)行若干趟的“分配”與“收集”來實(shí)現(xiàn)排序。

分配：我們將L[i]中的元素取出，首先確定其個(gè)位上的數(shù)字，根據(jù)該數(shù)字分配到與之序號(hào)相同的桶中 。

收集：當(dāng)序列中所有的元素都分配到對(duì)應(yīng)的桶中，再按照順序依次將桶中的元素收集形成新的一個(gè)待排序列L[ ] 。

對(duì)新形成的序列L[ ]重復(fù)執(zhí)行分配和收集元素中的十位、百位...直到分配完該序列中的最高位，則排序結(jié)束。

好了，本文就分享到這里，本文主要講解原理，不同編程語言實(shí)現(xiàn)方法不同，后面有機(jī)會(huì)再給大家分享具體實(shí)現(xiàn)方法。

------------ END ------------

推薦閱讀：

C語言實(shí)現(xiàn)面向?qū)ο蟮脑?/strong>

C/C++代碼規(guī)范注釋有哪些講究？

Embedded Studio中使用ST-Link調(diào)試教程

關(guān) 注 微信公眾號(hào)『strongerHuang』，后臺(tái)回復(fù)“1024”查看更多內(nèi)容，回復(fù)“加群”按規(guī)則加入技術(shù)交流群。

長按前往圖中包含的公眾號(hào)關(guān)注

點(diǎn)擊“ 閱讀原文 ”查看更多分享，歡迎點(diǎn)分享、收藏、點(diǎn)贊、在看。