java歸并排序如何實(shí)現(xiàn)

本篇內(nèi)容主要講解“java歸并排序如何實(shí)現(xiàn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“java歸并排序如何實(shí)現(xiàn)”吧!

歸并排序相對(duì)于冒泡、插入、選擇這三種排序時(shí)間復(fù)雜度是O(n2)來(lái)說(shuō)適合大規(guī)模的數(shù)據(jù)排序，它的時(shí)間復(fù)雜度都是O(nlogn)。

它用到了分治的思想，把大問(wèn)題分解成小問(wèn)題，小問(wèn)題再分，分而治之。

先來(lái)說(shuō)說(shuō)歸并排序的思想：把要排序的數(shù)組從中間一分為二，分為左邊和右邊，然后左右分別排序，排好了之后再合并到一起(如果左右兩邊還能分繼續(xù)一分為二，遞歸思想)這樣就排好了！是不是感覺(jué)挺簡(jiǎn)單的？

來(lái)看一下圖

上代碼！我們利用遞歸來(lái)實(shí)現(xiàn)歸并排序

代碼關(guān)鍵點(diǎn)就是,recursion這個(gè)遞歸，就是把數(shù)組一分為二，然后排序！

merge方法的思路就是申請(qǐng)一個(gè)左邊數(shù)組和右邊數(shù)組一樣長(zhǎng)度的空數(shù)組用來(lái)存放結(jié)果，然后搞了兩個(gè)游標(biāo)i和j分別指向左數(shù)組和右數(shù)組，對(duì)比left[i]和right[j],哪個(gè)小就放入result中，然后對(duì)應(yīng)的游標(biāo)+1。循環(huán)結(jié)束之后，再把剩余的沒(méi)塞入result的數(shù)據(jù)塞入result。這樣就大功告成了！

歸并排序的時(shí)間復(fù)雜度是O(nlogn)，并且從代碼可以看left[i]小于等于right[j]的時(shí)候是塞入result所以它是穩(wěn)定的排序！

例如[3,2,2,3]。當(dāng)分為left和right之后并且內(nèi)部排序之后是left[2,3]，right[2,3]。這時(shí)候還沒(méi)破壞兩個(gè)2直接的順序，之后合并還是left的2先塞入result,所以是穩(wěn)定的！

但是歸并有一個(gè)不好點(diǎn)它不是原地排序，可以看到它需要額外的數(shù)組空間存放排序之后的結(jié)果。它的空間復(fù)雜度是O(n)。

到此，相信大家對(duì)“java歸并排序如何實(shí)現(xiàn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！