數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)筆記之 適合大規(guī)模的數(shù)據(jù)排序

前言

在數(shù)據(jù)排序的算法中告希，不同數(shù)據(jù)規(guī)模應(yīng)當(dāng)使用合適的排序算法才能達(dá)到最好的效果姑曙，如小規(guī)模的數(shù)據(jù)排序模叙，可以使用冒泡排序严里、插入排序新啼，選擇排序，他們的時(shí)間復(fù)雜度都為O（n²）刹碾，大規(guī)模的數(shù)據(jù)排序就可以使用歸并排序和快速排序燥撞，時(shí)間復(fù)雜度為O（nlogn）。今天我們就來(lái)看一下歸并排序和快速排序迷帜。

正文

歸并排序的原理

核心思想（分治思想）：

排序數(shù)組物舒，將數(shù)組從中間分成前后兩部分，對(duì)前后兩部分分別排序戏锹，然后合在一起冠胯，這個(gè)數(shù)組就是有序的。

歸并排序的性能分析

1.歸并排序是一個(gè)穩(wěn)定的排序算法：在合并的過(guò)程中景用，如果A[p...q]和A[q+1...r]之間中有相同的元素涵叮，先把A[p...q]中的元素放入tmp數(shù)組。這樣就保證了值相同的元素伞插，在合并前后的先后順序不變割粮。

2.歸并排序的時(shí)間復(fù)雜度是O（nlogn）：在解決遞歸問(wèn)題時(shí)，我們得出一個(gè)結(jié)論：遞歸問(wèn)題可以寫成遞推公式媚污，遞歸代碼的時(shí)間復(fù)雜度也可以寫成遞推公式

我們假設(shè)對(duì)n個(gè)元素進(jìn)行歸并排序需要的時(shí)間是T（n）舀瓢，那分解成兩個(gè)子數(shù)組排序的時(shí)間都是T(n/2)，套用結(jié)論可以得到歸并排序的時(shí)間復(fù)雜度的計(jì)算公式就是：

<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;">T(1) = C耗美； n=1 時(shí)京髓，只需要常量級(jí)的執(zhí)行時(shí)間航缀，所以表示為 C。
T(n) = 2*T(n/2) + n堰怨； n>1</pre>

再次將這個(gè)公式分解:

<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;">T(n) = 2T(n/2) + n = 2(2T(n/4) + n/2) + n = 4T(n/4) + 2n = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n = 8(2T(n/16) + n/8) + 3n = 16T(n/16) + 4*n
...... = 2^k * T(n/2^k) + k * n
......</pre>

我們可以得到T(n)=2^kT(n/2k)+kn.當(dāng)T(n/2^{k)=T(1)時(shí)芥玉，也就是n/2}k=1,我們將得到k=log₂n，問(wèn)你將k帶入公式得到

T(n)=Cn+nlog2n

用大O標(biāo)記法來(lái)表示為T(n) 就等于 O(nlogn)

而且時(shí)間復(fù)雜度是非常穩(wěn)定的：最好情況备图，最壞情況灿巧，還是平均情況偶垮，時(shí)間復(fù)雜度都是O（nlogn）

3倦西、歸并排序的空間復(fù)雜度為O（n）

歸并排序的致命缺點(diǎn)：歸并排序不是原地排序算法（在合并兩個(gè)有序數(shù)組時(shí)汞扎，需要借助額外的存儲(chǔ)空間）

遞歸代碼的空間復(fù)雜度并不能像時(shí)間復(fù)雜度那樣累加铛碑、盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間提鸟，但在合并完成之后癣籽、臨時(shí)開(kāi)辟的內(nèi)存空間就被釋放掉了氓涣、臨時(shí)內(nèi)存空間最大也不會(huì)超過(guò) n 個(gè)數(shù)據(jù)的大小

快速排序的原理

如果要排序數(shù)組中下標(biāo)從p到r之間的一組數(shù)據(jù)渊抽，我們選擇p到r之間的任意一個(gè)數(shù)據(jù)作為pivot（分區(qū)點(diǎn)）雪标，遍歷數(shù)據(jù)零院，見(jiàn)小于pivot的放在右邊，大于pivot放在左邊汰聋。這樣數(shù)組就分成了三部分门粪，用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1.到r之間的數(shù)據(jù)，直到區(qū)間縮小為1烹困，說(shuō)明數(shù)據(jù)都有序
　　快速排序的時(shí)間復(fù)雜度為O（1）：在排序過(guò)程中玄妈，假如遇到需要移動(dòng)數(shù)據(jù)的，我們可以之間用交換的思想

image

（圖片來(lái)源于網(wǎng)絡(luò)髓梅，侵刪）

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

快速排序和歸并排序的區(qū)別拟蜻？

看圖：

image

（圖片來(lái)源于網(wǎng)絡(luò)，侵刪）

處理過(guò)程的差異：

遞歸排序：先處理子問(wèn)題再合并

快速排序：先分區(qū)枯饿，再處理子問(wèn)題

歸并排序雖然穩(wěn)定酝锅，是時(shí)間復(fù)雜度為O（nlogn）的排序算法，但是它不是原地排序算法奢方，合并過(guò)程中需要額外的空間搔扁。

快速排序的性能分析

遞歸代碼的時(shí)間復(fù)雜度，如果每次分區(qū)操作蟋字，都能正好將數(shù)組分為兩個(gè)大小相等的兩個(gè)小區(qū)間稿蹲，那快速排序的遞推公式和遞推排序是相同的，所以鹊奖，快排的時(shí)間復(fù)雜度為O（nlogn）

但是苛聘，每次都分得那么均勻是非常難實(shí)現(xiàn)的。

T（n）在大部分情況下的時(shí)間復(fù)雜度都可以做到O（nlogn），只有在極端情況下才會(huì)退化為O（n²）.

后記

遞歸和快排都是分治的思想设哗，代碼都通過(guò)遞歸來(lái)實(shí)現(xiàn)唱捣，過(guò)程非常相似。歸并排序時(shí)間復(fù)雜度都非常穩(wěn)定為O（nlogn）网梢，但是每次合并的時(shí)候都需要額外的空間震缭，空間復(fù)雜度非常高為是O(n)，快速排序算法雖然最壞時(shí)間復(fù)雜度為O（n²）澎粟，但是平均時(shí)間復(fù)雜度為O（nlogn）蛀序，最壞的情況我們也可以避免欢瞪。

相關(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)潔的編碼技巧“遞歸”

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

以上內(nèi)容為個(gè)人的學(xué)習(xí)筆記遣鼓，僅作為學(xué)習(xí)交流之用啸盏。

![LT8[X9E7]RLI}L]UROFK(`D.png](https://upload-images.jianshu.io/upload_images/14464859-7c72a73cc3dbc875.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

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

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

小舟從此逝回懦，江海寄余生。 --狐貍