數(shù)據(jù)結構與算法學習筆記之 適合大規(guī)模的數(shù)據(jù)排序前言

在數(shù)據(jù)排序的算法中，不同數(shù)據(jù)規(guī)模應當使用合適的排序算法才能達到最好的效果，如小規(guī)模的數(shù)據(jù)排序，可以使用冒泡排序、插入排序，選擇排序，他們的時間復雜度都為O（n²），大規(guī)模的數(shù)據(jù)排序就可以使用歸并排序和快速排序，時間復雜度為O（nlogn）。今天我們就來看一下歸并排序和快速排序。

創(chuàng)新互聯(lián)公司是一家專業(yè)提供云城企業(yè)網(wǎng)站建設,專注與網(wǎng)站設計、成都做網(wǎng)站、H5高端網(wǎng)站建設、小程序制作等業(yè)務。10年已為云城眾多企業(yè)、政府機構等服務。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設計公司優(yōu)惠進行中。正文　　歸并排序的原理　　核心思想（分治思想）：

排序數(shù)組，將數(shù)組從中間分成前后兩部分，對前后兩部分分別排序，然后合在一起，這個數(shù)組就是有序的。

歸并排序的性能分析

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

2.歸并排序的時間復雜度是O（nlogn）：在解決遞歸問題時，我們得出一個結論：遞歸問題可以寫成遞推公式，遞歸代碼的時間復雜度也可以寫成遞推公式

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

T(1) = C；   n=1 時，只需要常量級的執(zhí)行時間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1

再次將這個公式分解:

T(n) = 2*T(n/2) + n     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......     = 2^k * T(n/2^k) + k * n
     ......

我們可以得到T(n)=2^kT(n/2^k)+kn.當T(n/2^k)=T(1)時，也就是n/2^k=1,我們將得到k=log₂n，問你將k帶入公式得到

T(n)=Cn+nlog2n

用大O標記法來表示為T(n) 就等于 O(nlogn)

而且時間復雜度是非常穩(wěn)定的：最好情況，最壞情況，還是平均情況，時間復雜度都是O（nlogn）

3、歸并排序的空間復雜度為O（n）

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

遞歸代碼的空間復雜度并不能像時間復雜度那樣累加、盡管每次合并操作都需要申請額外的內(nèi)存空間，但在合并完成之后、臨時開辟的內(nèi)存空間就被釋放掉了、臨時內(nèi)存空間大也不會超過 n 個數(shù)據(jù)的大小

快速排序的原理

如果要排序數(shù)組中下標從p到r之間的一組數(shù)據(jù)，我們選擇p到r之間的任意一個數(shù)據(jù)作為pivot（分區(qū)點），遍歷數(shù)據(jù)，見小于pivot的放在右邊，大于pivot放在左邊。這樣數(shù)組就分成了三部分，用遞歸排序下標從 p 到 q-1 之間的數(shù)據(jù)和下標從 q+1.到r之間的數(shù)據(jù)，直到區(qū)間縮小為1，說明數(shù)據(jù)都有序
快速排序的時間復雜度為O（1）：在排序過程中，假如遇到需要移動數(shù)據(jù)的，我們可以之間用交換的思想

（圖片來源于網(wǎng)絡，侵刪）

空間復雜度為O（1）

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

看圖：

（圖片來源于網(wǎng)絡，侵刪）

處理過程的差異：

遞歸排序：先處理子問題再合并

快速排序：先分區(qū)，再處理子問題

歸并排序雖然穩(wěn)定，是時間復雜度為O（nlogn）的排序算法，但是它不是原地排序算法，合并過程中需要額外的空間。

快速排序的性能分析

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

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

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

后記

遞歸和快排都是分治的思想，代碼都通過遞歸來實現(xiàn)，過程非常相似。歸并排序時間復雜度都非常穩(wěn)定為O（nlogn），但是每次合并的時候都需要額外的空間，空間復雜度非常高為是O(n)，快速排序算法雖然最壞時間復雜度為O（n²），但是平均時間復雜度為O（nlogn），最壞的情況我們也可以避免。

相關文章

數(shù)據(jù)結構與算法學習筆記之寫鏈表代碼的正確姿勢（下）

數(shù)據(jù)結構與算法學習筆記之 提高讀取性能的鏈表（上）

數(shù)據(jù)結構與算法學習筆記之 從0編號的數(shù)組

數(shù)據(jù)結構與算法學習筆記之后進先出的“桶”

數(shù)據(jù)結構與算法學習筆記之先進先出的隊列

數(shù)據(jù)結構與算法學習筆記之高效、簡潔的編碼技巧“遞歸”

數(shù)據(jù)結構與算法學習筆記之如何分析一個排序算法？

以上內(nèi)容為個人的學習筆記，僅作為學習交流之用。

歡迎大家關注公眾號，不定時干貨，只做有價值的輸出

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

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

分享標題：數(shù)據(jù)結構與算法學習筆記之適合大規(guī)模的數(shù)據(jù)排序-創(chuàng)新互聯(lián)
鏈接分享：http://www.chinadenli.net/article30/doidso.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、手機網(wǎng)站建設、定制網(wǎng)站、網(wǎng)站改版、關鍵詞優(yōu)化、動態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)