這篇文章是對上周發(fā)的 11大排序?這個視頻中提到的 時間復(fù)雜度 和 空間復(fù)雜度 進(jìn)行一個解析，有問題可以在評論區(qū)提，覺得我說得不對也可以在評論區(qū)指出哈。

一、選擇排序

Python源碼

時間復(fù)雜度分析

當(dāng) i = 0 的時候，j 從 1 到 n-1，內(nèi)層循環(huán)執(zhí)行次數(shù)為 n-1 次；

當(dāng) i = 1 的時候，j 從 2 到 n-1，內(nèi)層循環(huán)執(zhí)行次數(shù)為 n-2 次；

... （根據(jù)數(shù)學(xué)歸納法）

當(dāng) i = n-2 的時候，j 從 n-1 到 n-1，內(nèi)層循環(huán)執(zhí)行次數(shù)為 1 次；

所以總的執(zhí)行次數(shù)就是 ?(1 + (n-1)) * (n-1) / 2 = n * (n - 1) / 2；

所以時間復(fù)雜度就是 O(n^2)

空間復(fù)雜度分析

由于在進(jìn)行循環(huán)計算的時候

只用到了一個 min 作為額外變量

所以空間復(fù)雜度就是 O(1)

算法優(yōu)化

內(nèi)層循環(huán)做的事情

是在一個區(qū)間內(nèi)尋找一個最小值

然后把最小值更新為另一個值

這樣的操作

可以用線段樹來進(jìn)行優(yōu)化

使得查找最小值和更新區(qū)間值的操作

內(nèi)層循環(huán)的時間復(fù)雜度降為 O(logn)

所以總的時間復(fù)雜度就是 O(nlogn)

二、冒泡排序

Python源碼

時間復(fù)雜度分析

當(dāng) i = n-1 時，j 從 0 到 n-2，內(nèi)層循環(huán)數(shù)是 n-1

當(dāng) i = n-2 時， j 從 0 到 n-3，內(nèi)層循環(huán)數(shù)是 n - 2

...（根據(jù)數(shù)學(xué)歸納法）

當(dāng) i = 1 時， j 從 0 到 0，內(nèi)層循環(huán)數(shù)是 1

所以總的執(zhí)行次數(shù)就是 ?(1 + (n-1)) * (n-1) / 2 = n * (n - 1) / 2；

所以時間復(fù)雜度就是 O(n^2)

空間復(fù)雜度分析

由于在進(jìn)行循環(huán)計算的時候

沒有用到額外變量

所以空間復(fù)雜度就是 O(1)

算法優(yōu)化

內(nèi)層循環(huán)中

如果發(fā)現(xiàn)已經(jīng)完全有序了

則置一個標(biāo)志位

并且無須繼續(xù)排序

這就是優(yōu)化

三、插入排序

Python源碼

空間復(fù)雜度分析

當(dāng)原本就是一個升序序列時

內(nèi)層循環(huán)每次只需要執(zhí)行一次

總共執(zhí)行 n 次

所以時間復(fù)雜度為 O(n)

當(dāng)原本是一個降序序列時

內(nèi)層循環(huán)每次需要執(zhí)行 i 次

總共需要執(zhí)行 (1 + n) * n / 2

所以時間復(fù)雜度為 O(n^2)

然而我們在說時間復(fù)雜度的時候

往往說的是最壞時間復(fù)雜度

所以這個算法的時間復(fù)雜度

就是 O(n^2)

空間復(fù)雜度分析

由于沒有用到任何的額外變量

所以空間復(fù)雜度是 O(1)

算法優(yōu)化

插入排序可以利用希爾排序進(jìn)行優(yōu)化

下文就會講到了

四、歸并排序

Python源碼

時間復(fù)雜度分析

假設(shè)比較和賦值的時間復(fù)雜度為O(1)

首先討論歸并排序最重要的子程序

是一個 O(n) 的歸并

給定兩個大小為 n1 和 ?n2 的排序樹組 A 和 B

我們可以在 O(n) 時間內(nèi)

將它們有效地歸并成一個大小為 n = n1 + n2 的排序數(shù)組

那么請問這個歸并過程

被調(diào)用了多少次？

由于每次都是對半切

所以整個歸并過程類似于一棵二叉樹的構(gòu)建過程

次數(shù)就是二叉樹的高度即 log n

所以歸并排序的時間復(fù)雜度為 O(nlogn)

空間復(fù)雜度分析

由于歸并排序在歸并過程中

需要額外的一個輔助數(shù)組

且最大長度為序列長度

所以歸并排序的空間復(fù)雜度為 O(n)

算法優(yōu)化

時間復(fù)雜度

已經(jīng)是比較排序中最優(yōu)的了

無須繼續(xù)優(yōu)化

但是空間復(fù)雜度是可以優(yōu)化的

由于在排序的過程中

需要額外的一個輔助數(shù)組

所以申請輔助數(shù)組內(nèi)存空間

帶來的空間消耗會比較大

所有輔助數(shù)組干的事情

都可以在傳參進(jìn)去的數(shù)組上進(jìn)行

這樣就省去了內(nèi)存的頻繁申請和釋放

五、桶排序

Python源碼

時間復(fù)雜度分析

上面說了

時間復(fù)雜度一定要看最壞情況

所以如果數(shù)據(jù)導(dǎo)致

分成 x 個桶

但是只有第一個桶有元素

其他桶都沒有元素

這時候就會退化成 O(n^2) 的選擇排序

所以每個桶中的排序

我們可以采用歸并排序

這樣一來

最壞情況下

時間復(fù)雜度也只是 O(nlogn)

空間復(fù)雜度分析

由于要把所有元素

放到桶中

所以總共需要放置的空間為 O(n)

于是空間復(fù)雜度就是 O(n)

算法優(yōu)化

桶排序?qū)?shù)據(jù)要求比較高

并不是適用所有數(shù)據(jù)類型的排序

所以局限性也比較大

一般不會直接用

除非數(shù)據(jù)分布比較特殊

一般用到的是 計數(shù)排序 和 基數(shù)排序

六、計數(shù)排序

Python源碼

時間復(fù)雜度分析

由于計數(shù)排序

將所有數(shù)字哈希到了哈希表中

所以插入和查找的時間復(fù)雜度為O(1)

每個數(shù)字插入一次取出一次

總的時間復(fù)雜度為 O(n)

空間復(fù)雜度分析

假設(shè)序列中的元素

都是整數(shù)并且返回為 [a, b]

那么令 m = b - a + 1

空間復(fù)雜度就是 O(m)

算法優(yōu)化

由于計數(shù)排序?qū)?shù)據(jù)范圍是有要求的

如果是非整數(shù)

則排序過程需要乘上對應(yīng)的精度

如果數(shù)值太大

則無法完成我們的預(yù)期

如果出現(xiàn)了負(fù)數(shù)

需要加上偏移

總的來說

雖然時間復(fù)雜度非常優(yōu)秀

但是對數(shù)據(jù)本身的要求會很高

七、基數(shù)排序

Python源碼

時間復(fù)雜度分析

和數(shù)字的數(shù)據(jù)范圍有關(guān)

假設(shè)一個數(shù)字最高位為 m 位數(shù)

那么 while 循環(huán) m 次

每次內(nèi)部執(zhí)行 n 次

總的時間復(fù)雜度為 O(mn)

空間復(fù)雜度分析

需要建立10個桶

每個桶的元素加起來

總的大小為 n

所以空間復(fù)雜度為 O(n)

算法優(yōu)化

基數(shù)排序是對計數(shù)排序的優(yōu)化

計算數(shù)字再大

也可以映射到桶中

容錯性會更好

八、快速排序

Python源碼

時間復(fù)雜度分析

如果本身就是升序的序列

那么快速排序的時間復(fù)雜度是 O(n^2)

也就是最壞時間復(fù)雜度

空間復(fù)雜度分析

類似冒泡排序

使用交換的方式進(jìn)行排序

如果不算堆棧的消耗

空間復(fù)雜度為 O(1)

算法優(yōu)化

采用隨機(jī)快速排序就可以了

九、隨機(jī)快速排序

Python源碼

時間復(fù)雜度分析

由于基準(zhǔn)點采用了隨機(jī)

所以基本不可能次次都是最壞情況

平均時間復(fù)雜度降為 O(nlogn)

空間復(fù)雜度分析

和普通的快速排序一致

算法優(yōu)化

非常優(yōu)秀的算法

唯一的缺點就是

它是不穩(wěn)定的

十、希爾排序

Python源碼

時間復(fù)雜度分析

網(wǎng)上說是 O(n^(2/3))

具體怎么證明（先留個坑，今天太困了，留給評論區(qū)）

空間復(fù)雜度分析

希爾排序是原地排序

所以空間復(fù)雜度為 O(1)

十一、堆排序

Python源碼

時間復(fù)雜度分析

由于堆是一棵完全二叉樹

所以樹的高度為 logn

所以每一次操作最多執(zhí)行 logn次

所以時間復(fù)雜度為 O(nlogn)

空間復(fù)雜度分析

由于沒有采用任何的空間

所以空間復(fù)雜度為 O(1)