數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之如何分析一個(gè)排序算法余佃？

前言

現(xiàn)在IT這塊找工作暮刃，不會(huì)幾個(gè)算法都不好意思出門，排序算法恰巧是其中最簡(jiǎn)單的爆土，我接觸的第一個(gè)算法就是它椭懊，但是你知道怎么分析一個(gè)排序算法么？有很多時(shí)間復(fù)雜度相同的排序算法步势，在實(shí)際編碼中氧猬，那又如何選擇呢？下面我們帶著問題一起學(xué)習(xí)一下坏瘩。

正文

一盅抚、常見經(jīng)典的排序方法

（圖片來自于一像素）

插入排序

image

希爾排序（遞減增量排序算法）

image

歸并排序

image

快速排序

image

冒泡排序

image

選擇排序

image

計(jì)數(shù)排序

image

計(jì)數(shù)排序

image

堆排序

image

二、 按照時(shí)間復(fù)雜度歸類

時(shí)間復(fù)雜度O（n²）：

冒泡排序倔矾、插入排序妄均、選擇排序

時(shí)間復(fù)雜度O(nlogn)：
快速排序柱锹、歸并排序

時(shí)間復(fù)雜度O(n)：

計(jì)數(shù)排序、基數(shù)排序丰包、桶排序

三禁熏、如何分析一個(gè)“排序算法”？

從三個(gè)方面入手

a邑彪、算法的執(zhí)行效率

1.最好瞧毙、最壞、平均情況時(shí)間復(fù)雜度寄症。

從算法的核心宙彪，復(fù)雜度入手，給出最好最壞有巧，平均情況下的時(shí)間復(fù)雜度释漆，便于分析

2. 時(shí)間復(fù)雜度的系數(shù)、常數(shù)和低階剪决。

時(shí)間復(fù)雜度表示的是規(guī)模很大的一種增漲趨勢(shì)灵汪，很容易就忽略系數(shù)，低階柑潦，常數(shù)等，實(shí)際開發(fā)中排序的規(guī)模都是像10.100.1000這種小規(guī)模

3. 比較次數(shù)峻凫，交換（或移動(dòng)）次數(shù)渗鬼。

排序算法執(zhí)行過程中，涉及兩種操作荧琼，一種是元素比較大小譬胎，一種是元素交換或移動(dòng)位置，所以比較次數(shù)命锄，交換次數(shù)都得考慮進(jìn)去堰乔。

b、排序算法的內(nèi)存消耗

算法消耗可以通過空間復(fù)雜度來衡量

原地排序算法：特指空間復(fù)雜度是O(1)的排序算法脐恩。

c镐侯、排序算法的穩(wěn)定性

1. 穩(wěn)定性概念：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后驶冒，相等元素之間原有的先后順序不變苟翻。
2. 穩(wěn)定性重要性：可針對(duì)對(duì)象的多種屬性進(jìn)行有優(yōu)先級(jí)的排序。
3. 舉例：給電商交易系統(tǒng)中的“訂單”排序骗污，按照金額大小對(duì)訂單數(shù)據(jù)排序崇猫，對(duì)于相同金額的訂單以下單時(shí)間早晚排序。用穩(wěn)定排序算法可簡(jiǎn)潔地解決需忿。先按照下單時(shí)間給訂單排序诅炉，排序完成后用穩(wěn)定排序算法按照訂單金額重新排序蜡歹。

四、詳解冒泡排序

冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)涕烧。每次冒泡操作都會(huì)對(duì)相鄰的兩個(gè)元素進(jìn)行比較月而，看是否滿足大小關(guān)系要求，如果不滿足就讓它倆互換澈魄。

冒泡排序只涉及相鄰數(shù)據(jù)的交換景鼠，只需要常量級(jí)的臨時(shí)空間，所以它的空間復(fù)雜度未O（1）是原地排序算法

穩(wěn)定性：當(dāng)有相鄰的兩個(gè)元素大小相等時(shí)痹扇，不做交換铛漓，冒泡排序是穩(wěn)定的排序算法。

引入兩個(gè)概念：

默認(rèn)從小到大未有序

有序度：數(shù)組中具有有序關(guān)系的元素對(duì)的個(gè)數(shù)鲫构。

滿有序度：完全有序的數(shù)組

逆序度：數(shù)組中具有無序關(guān)系的元素對(duì)的個(gè)數(shù)浓恶。

逆序度=滿有序度-有序度

排序的過程實(shí)際上就是增加有序度，減少逆序度的過程

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

1. 最好情況（滿有序度）：O(n)结笨。
2. 最壞情況（滿逆序度）：O(n^2)包晰。
3. 平均情況：
   “有序度”和“逆序度”：對(duì)于一個(gè)不完全有序的數(shù)組，如4炕吸，5伐憾，6，3赫模，2树肃，1，有序元素對(duì)為3個(gè)（4瀑罗，5）胸嘴，（4，6）斩祭，（5劣像，6），有序度為3摧玫，逆序度為12耳奕；對(duì)于一個(gè)完全有序的數(shù)組，如1席赂，2吮铭，3，4颅停，5谓晌，6，有序度就是n(n-1)/2癞揉，也就是15纸肉，稱作滿有序度溺欧；逆序度=滿有序度-有序度；冒泡排序柏肪、插入排序交換（或移動(dòng)）次數(shù)=逆序度姐刁。
   最好情況下初始有序度為n(n-1)/2，最壞情況下初始有序度為0烦味，則平均初始有序度為n(n-1)/4聂使，即交換次數(shù)為n(n-1)/4，因交換次數(shù)<比較次數(shù)<最壞情況時(shí)間復(fù)雜度谬俄，所以平均時(shí)間復(fù)雜度為O(n²)柏靶。

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

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 冒泡排序，a 表示數(shù)組溃论，n 表示數(shù)組大小
public void bubbleSort(int[] a, int n) { if (n <= 1) return; for (int i = 0; i < n; ++i) { // 提前退出冒泡循環(huán)的標(biāo)志位
boolean flag = false; for (int j = 0; j < n - i - 1; ++j) { if (a[j] > a[j+1]) { // 交換
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有數(shù)據(jù)交換
}
} if (!flag) break; // 沒有數(shù)據(jù)交換屎蜓，提前退出
}
}</pre>

五、詳解插入排序

將數(shù)據(jù)分為兩個(gè)區(qū)間钥勋，已排序區(qū)間和未排序區(qū)間炬转，初始已排序區(qū)間只有一個(gè)元素(即第一個(gè)數(shù)據(jù))，我們?nèi)∥磁判騾^(qū)間的元素算灸，在已排序的區(qū)間中找到合適的位置插入位置插入扼劈，并保證已排序區(qū)間數(shù)據(jù)一直有序，重復(fù)過程菲驴，直到未排序區(qū)間中沒有元素

運(yùn)行過程中看得出來测僵，不需要額外的存儲(chǔ)空間，所以空間復(fù)雜度為0（1）谢翎，也是原地排序算法

同樣值的元素，前后順序保持不變沐旨，是穩(wěn)定的排序算法

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

最好時(shí)間復(fù)雜度為O(n)

最壞時(shí)間復(fù)雜度為O(n²)

平均時(shí)間復(fù)雜度為O(n²)

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

<pre style="margin: 0px 0px 15px; padding: 0px; white-space: pre-wrap; overflow-wrap: break-word; font-family: Monaco, Menlo, Consolas, "Courier New", monospace; font-size: 12px !important; line-height: 1.72222; color: inherit; border-radius: 2px; background: rgb(238, 238, 238); border: 0px; overflow: auto;">// 插入排序森逮，a 表示數(shù)組，n 表示數(shù)組大小
public void insertionSort(int[] a, int n) { if (n <= 1) return; for (int i = 1; i < n; ++i) { int value = a[i]; int j = i - 1; // 查找插入的位置
for (; j >= 0; --j) { if (a[j] > value) {
a[j+1] = a[j]; // 數(shù)據(jù)移動(dòng)
} else { break;
}
}
a[j+1] = value; // 插入數(shù)據(jù)
}
}</pre>

六磁携、詳解選擇排序

選擇排序?qū)?shù)組數(shù)據(jù)分成已排序區(qū)間和未排序區(qū)間褒侧。初始已排序區(qū)間只有一個(gè)元素，即數(shù)組第一個(gè)元素谊迄。在未排序區(qū)間找到最小的數(shù)據(jù)闷供，將其放在已排序區(qū)間的末尾

空間復(fù)雜度為O(1)，選擇排序是原地排序算法统诺。

未排序區(qū)間的元素和已排序區(qū)間的元素相同時(shí)歪脏，它可以放在已排序區(qū)間相同值的前或后，所以為不穩(wěn)定的排序

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

1. 最好情況：O(n²)粮呢。
2. 最壞情況：O(n²)婿失。
3. 平均情況：O(n²)（往數(shù)組中插入一個(gè)數(shù)的平均時(shí)間復(fù)雜度是O(n)钞艇，一共重復(fù)n次）。

七豪硅、各種排序方法的匯總比較

image

八哩照、選擇排序和插入排序的時(shí)間復(fù)雜度相同，都是O(n^2)懒浮，在實(shí)際的軟件開發(fā)中飘弧，為什么我們更傾向于使用插入排序而不是冒泡排序算法呢？

答：它們的元素比較次數(shù)以及交換元素的次數(shù)都是原始數(shù)據(jù)的逆序度砚著，是一個(gè)固定值次伶，但是從代碼實(shí)現(xiàn)上來看，冒泡排序的數(shù)據(jù)交換要比插入排序的數(shù)據(jù)移動(dòng)要復(fù)雜赖草，冒泡排序需要3個(gè)賦值操作学少，而插入排序只需要1個(gè)，他們 的時(shí)間復(fù)雜度上都是O(n²)秧骑，但是為了追求極致的性能版确，所以首選插入排序算法

結(jié)尾

大家不妨試著分析一下其他的幾種算法。

看再多遍都不如寫一篇來得深刻乎折，建議大家多敲绒疗。

相關(guān)文章

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之寫鏈表代碼的正確姿勢(shì)（下）

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 提高讀取性能的鏈表（上）

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 從0編號(hào)的數(shù)組

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之后進(jìn)先出的“桶”

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之先進(jìn)先出的隊(duì)列

數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之高效、簡(jiǎn)潔的編碼技巧“遞歸”

以上內(nèi)容為個(gè)人的學(xué)習(xí)筆記骂澄，僅作為學(xué)習(xí)交流之用吓蘑。

Dawnzhang公眾號(hào).jpg

歡迎大家關(guān)注公眾號(hào)，不定時(shí)干貨坟冲，只做有價(jià)值的輸出

作者：Dawnzhang
出處：https://www.cnblogs.com/clwydjgs/p/9815690.html

小舟從此逝磨镶，江海寄余生。 --狐貍