數(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ù)雜度，便于分析

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

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

比較次數(shù)，交換（或移動(dòng)）次數(shù)。

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

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

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

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

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

穩(wěn)定性概念：如果待排序的序列中存在值相等的元素，經(jīng)過排序之后，相等元素之間原有的先后順序不變。
穩(wěn)定性重要性：可針對(duì)對(duì)象的多種屬性進(jìn)行有優(yōu)先級(jí)的排序。
舉例：給電商交易系統(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ù)雜度：

最好情況（滿有序度）：O(n)。
最壞情況（滿逆序度）：O(n^2)。
平均情況：
“有序度”和“逆序度”：對(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ù)雜度：

最好情況：O(n²)。
最壞情況：O(n²)。
平均情況：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é)尾

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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