合并排序是一種基于比較的有效排序算法。該算法基于 "分而治之"，意味著在這種情況下，初始集合將被分割成更小的部分。這個(gè)概念可以遞歸地引入，這樣集合就會(huì)被分割成單個(gè)組件，然后重新構(gòu)建成一個(gè)排序的集合。重新構(gòu)建算法的合并部分是對(duì)組件進(jìn)行排序的階段。這篇文章為大家?guī)?lái)美國(guó)舊金山大學(xué)合并排序作業(yè)輔導(dǎo)。

一、自然合并排序

自然合并類型相當(dāng)于一種自下而上的合并，只是在輸入中利用了任何自然發(fā)生的運(yùn)行(排序序列)。位數(shù)以及單調(diào)運(yùn)行都可以被利用，列表是方便的數(shù)據(jù)結(jié)構(gòu)(作為后進(jìn)先出或先進(jìn)先出使用)。出發(fā)點(diǎn)是假設(shè)每個(gè)運(yùn)行在自下而上的合并類型中是一個(gè)項(xiàng)目。在實(shí)踐中，會(huì)有很多短暫的隨機(jī)輸入信息的運(yùn)行，只是發(fā)生了被排序。在典型的情況下，因?yàn)橐喜⒌倪\(yùn)行較少，自然合并類型可能不需要那么多遍。在最好的情況下，輸入已經(jīng)被排序了(即單次運(yùn)行)，所以只需要通過(guò)自然合并排序?qū)?shù)據(jù)進(jìn)行一次傳遞。長(zhǎng)的自然運(yùn)行在很多實(shí)際情況下都存在，這就是為什么要利用自然合并類型。我們的任務(wù)幫助專家現(xiàn)在將向你解釋關(guān)于

二、過(guò)程

合并排序的過(guò)程涉及三個(gè)部分

將問(wèn)題劃分為同一問(wèn)題的若干小的子問(wèn)題。

通過(guò)不斷解決這些子問(wèn)題來(lái)征服它們。如果子問(wèn)題足夠小，則將其作為基本案例進(jìn)行解決。

將子問(wèn)題的替代方案合并到最初的問(wèn)題解決方案中。

三、性能分析

合并排序算法的輸出是非常顯著的O(n log(n))。建議使用默認(rèn)庫(kù)。現(xiàn)在大多數(shù)語(yǔ)言在真實(shí)世界的實(shí)現(xiàn)中都使用性能更好的算法作為默認(rèn)的排序選擇。在Java中，在Util包的Arrays類中有一種排序技術(shù)。雙樞軸Quicksort，它的時(shí)間復(fù)雜度為O(n log(n))，是根據(jù)文檔來(lái)實(shí)現(xiàn)的。

根據(jù)下面的Java代碼，在函數(shù)mergeSort中，只有兩個(gè)語(yǔ)句可以創(chuàng)造額外的空間。一個(gè)是中心，它需要O(1)空間的復(fù)雜性。另一個(gè)是合并功能，由于臨時(shí)數(shù)組(tem)的存在，需要O(n)空間的復(fù)雜度。該算法也是一種深度優(yōu)先的算法。在某個(gè)階段，只有一個(gè)合并特征可以執(zhí)行。因此，這里的房間復(fù)雜度是O(n)。

合并排序n個(gè)對(duì)象的中位數(shù)和最壞情況下的性能是O(n log n)。考慮到一個(gè)長(zhǎng)度為n的列表在運(yùn)行狀態(tài)下的合并排序的時(shí)間是T(n)，那么遞推式T(n)= 2T(n/2)+n是由算法定義得出的，它要求把算法放到初始列表的兩個(gè)列表的一半大小，然后把為合并兩個(gè)輸出列表所做的n個(gè)步驟加上。該閉合式是由除法和征服遞歸主定理得出的。

隨著多級(jí)內(nèi)存層次的使用，在當(dāng)代個(gè)人電腦的軟件優(yōu)化中，參考的位置可能具有極其重要的意義。我們介紹了一些現(xiàn)有的合并算法，這些算法主要是意識(shí)到機(jī)器的高速緩沖存儲(chǔ)器，其任務(wù)主要是選擇減少?gòu)母咚倬彌_機(jī)器以及機(jī)器外部發(fā)生的頁(yè)面移動(dòng)。例如，當(dāng)達(dá)到大小為S的子陣列時(shí)，具有平鋪算法的合并排序?qū)⒘⒓赐Ｖ箘澐肿雨嚵校渲蠸被認(rèn)為是機(jī)器或CPU可以容納的緩存內(nèi)存的數(shù)量。為了防止內(nèi)存被包裹或不再被訪問(wèn)，在這個(gè)地方首先使用插入排序這樣的排序算法，以便沒(méi)有緩存內(nèi)存的問(wèn)題，然后用標(biāo)準(zhǔn)遞歸的模式，最后對(duì)其進(jìn)行合并排序，以使其按照給定的方式進(jìn)行排序，無(wú)論是升序還是降序。在那些受益于緩存優(yōu)化的計(jì)算機(jī)上，這種算法被證明有更好的效率。

海馬課堂留學(xué)生作業(yè)輔導(dǎo)，根據(jù)學(xué)生的輔導(dǎo)需求匹配背景相符的專業(yè)老師。1V1個(gè)性化備課，雙語(yǔ)教學(xué)，實(shí)時(shí)輔導(dǎo)，講解相關(guān)知識(shí)點(diǎn)和解題思路，提供大型作業(yè)任務(wù)的解決方案，輔導(dǎo)計(jì)算機(jī)編程語(yǔ)言操作，教授學(xué)生高效完成PPT和演講稿，針對(duì)性解決留學(xué)生各類作業(yè)中遇到的困擾，提高作業(yè)成績(jī)！