數(shù)據(jù)科學(xué)家每天都在處理算法。然而，數(shù)據(jù)科學(xué)學(xué)科作為一個(gè)整體已經(jīng)發(fā)展成為一個(gè)不涉及復(fù)雜算法實(shí)現(xiàn)的角色。盡管如此，從業(yè)者仍然可以從對(duì)算法的理解和掌握中獲益。

本文介紹、解釋、評(píng)估和實(shí)現(xiàn)了排序算法merge-sort 。本文的目的是為您提供有關(guān)合并排序算法的可靠背景信息，該算法是更復(fù)雜算法的基礎(chǔ)知識(shí)。

盡管合并排序不被認(rèn)為是復(fù)雜的，但是理解該算法將有助于您認(rèn)識(shí)到選擇最有效的算法來(lái)執(zhí)行與數(shù)據(jù)相關(guān)的任務(wù)時(shí)需要考慮的因素。創(chuàng)建于 1945 年的 約翰·馮·諾依曼 使用分治方法開發(fā)了合并排序算法。

分而治之

要理解合并排序算法，您必須熟悉分治范式，以及遞歸的編程概念。計(jì)算機(jī)科學(xué)領(lǐng)域中的遞歸是指定義用于解決問題的方法在其實(shí)現(xiàn)體中調(diào)用自身。

換句話說(shuō)，函數(shù)會(huì)反復(fù)調(diào)用自身。

圖 1 。遞歸的視覺圖解——作者的圖像 .

分治算法（合并排序是一種）在其方法中使用遞歸來(lái)解決特定問題。分治算法將復(fù)雜問題分解為更小的子部分，其中定義的解決方案遞歸地應(yīng)用于每個(gè)子部分。然后分別求解每個(gè)子部分，并重新組合解決方案以解決原始問題。

分而治之的算法設(shè)計(jì)方法結(jié)合了三個(gè)主要元素：

將較大的問題分解為較小的子問題。（分開）

遞歸使用函數(shù)來(lái)解決每個(gè)較小的子問題。（征服）

最終的解決方案是對(duì)較大問題的較小子問題的解決方案的組合。（合并）

其他算法使用分治范式，如快速排序、二進(jìn)制搜索和 Strassen 算法。

合并排序

在按升序?qū)α斜碇械脑剡M(jìn)行排序的上下文中， merge-sort 方法將列表分成兩半，然后迭代新的兩半，不斷地將它們進(jìn)一步分成更小的部分。

隨后，對(duì)較小的一半進(jìn)行比較，并將結(jié)果組合在一起，形成最終的排序列表。

步驟和實(shí)施

合并排序算法的實(shí)現(xiàn)分為三步。分而治之，然后結(jié)合。

分而治之方法的分而治之部分是第一步。這個(gè)初始步驟將整個(gè)列表分成兩個(gè)較小的部分。然后，列表被進(jìn)一步分解，直到它們不能再被分割，在每個(gè)減半的列表中只留下一個(gè)元素項(xiàng)。

合并排序的第二階段中的遞歸循環(huán)與按特定順序排序的列表元素有關(guān)。在這種情況下，初始數(shù)組按升序排序。

在下圖中，您可以看到合并排序算法中涉及的分割、比較和組合步驟。

圖 2 。按作者劃分合并排序算法圖像的組件插圖。

圖 3 。征服和結(jié)合的組成部分形象的作者。

要自己實(shí)現(xiàn)這一點(diǎn)：

創(chuàng)建一個(gè)名為 merge _ sort 的函數(shù)，該函數(shù)接受整數(shù)列表作為參數(shù)。以下所有說(shuō)明均在此功能范圍內(nèi)。

首先把清單分成兩半。記錄列表的初始長(zhǎng)度。

檢查記錄的長(zhǎng)度是否等于 1 。如果條件的計(jì)算結(jié)果為 true ，則返回列表，因?yàn)檫@意味著列表中只有一個(gè)元素。因此，不需要?jiǎng)澐智鍐巍?/p>

獲取元素?cái)?shù)大于 1 的列表的中點(diǎn)。使用 Python 語(yǔ)言時(shí)，//執(zhí)行除法，不帶余數(shù)。它將除法結(jié)果四舍五入到最接近的整數(shù)。這也被稱為樓層劃分。

使用中點(diǎn)作為參考點(diǎn)，將列表拆分為兩半。這是分而治之算法范例的分而治之的一面。

Recursion is leveraged at this step to facilitate the division of lists into halved components. The variables ‘left_half’ and ‘right_half’ are assigned to the invocation of the ‘ merge_sort’ function, accepting the two halves of the initial list as parameters.

“ merge_sort ”函數(shù)返回對(duì)一個(gè)函數(shù)的調(diào)用，該函數(shù)將兩個(gè)列表合并，以返回一個(gè)組合的排序列表。

• 序列表。

def merge_sort(list: [int]): list_length = len(list) if list_length == 1: return list mid_point = list_length // 2 left_half = merge_sort(list[:mid_point]) right_half = merge_sort(list[mid_point:]) return merge(left_half, right_half)

• 創(chuàng)建一個(gè)‘merge’函數(shù)，該函數(shù)接受兩個(gè)整數(shù)列表作為其參數(shù)。此函數(shù)包含分治算法范例的征服和合并方面。以下所有步驟均在此函數(shù)體中執(zhí)行。
• 為保存已排序整數(shù)的變量“ output ”分配一個(gè)空列表。
• 指針‘i’和‘j’分別用于為左列表和右列表編制索引。
• 在 while 循環(huán)中，對(duì)左列表和右列表的元素進(jìn)行比較。每次比較后，輸出列表將填充在兩個(gè)比較的元素中。追加元素列表的指針遞增。
• 要添加到排序列表的其余元素是從當(dāng)前指針值到相應(yīng)列表末尾的元素。

def merge(left, right): output = [] i = j = 0 while (i < len(left) and j < len(right)): if left[i] < right[j]: output.append(left[i]) i +=1 else: output.append(right[j]) j +=1 output.extend(left[i:]) output.extend(right[j:]) return output unsorted_list = [2, 4, 1, 5, 7, 2, 6, 1, 1, 6, 4, 10, 33, 5, 7, 23]
sorted_list = merge_sort(unsorted_list)
print(unsorted_list)
print(sorted_list)

性能和復(fù)雜性

大 O 表示法是一種標(biāo)準(zhǔn)，用于定義和組織算法在空間需求和執(zhí)行時(shí)間方面的性能。

合并排序算法在最佳、最差和平均情況下的時(shí)間復(fù)雜度相同。對(duì)于大小為 n 的列表，合并排序算法要完成的預(yù)期步驟數(shù)、最小步驟數(shù)和最大步驟數(shù)都是相同的。

正如本文前面提到的，合并排序算法分為三個(gè)步驟：劃分、征服和合并?！胺指睢辈襟E涉及到列表中點(diǎn)的計(jì)算，無(wú)論列表大小如何，它都只需要一個(gè)操作步驟。因此，該操作的符號(hào)表示為 O（1） 。

“征服”步驟包括劃分和遞歸求解子數(shù)組—— logn 表示這一點(diǎn)。“合并”步驟包括將結(jié)果合并到最終列表中；此操作執(zhí)行時(shí)間取決于列表大小，并表示為 O（n） 。

平均、最佳和最差時(shí)間復(fù)雜度的合并排序表示法是 log n * n * O （ 1 ） 。在大 O 表示法中，低階項(xiàng)和常數(shù)可以忽略不計(jì)，這意味著合并排序算法的最終表示法是 O （ n 日志 n ） 。有關(guān)合并排序算法的詳細(xì)分析，請(qǐng)參閱 article 。

評(píng)價(jià)

合并排序在對(duì)大型列表進(jìn)行排序時(shí)表現(xiàn)良好，但在較小列表上使用時(shí)，其操作時(shí)間比其他排序解決方案慢。合并排序的另一個(gè)缺點(diǎn)是，即使初始列表已經(jīng)排序，它也會(huì)執(zhí)行操作步驟。在鏈表排序的用例中，合并排序是最快的排序算法之一。合并排序可用于外部存儲(chǔ)系統(tǒng)（如硬盤）中的文件排序。

關(guān)鍵外賣

本文描述了合并排序技術(shù)，將其分解為組成操作和逐步過(guò)程。

合并排序算法是常用的，與其他排序算法相比，該算法背后的直覺和實(shí)現(xiàn)相當(dāng)簡(jiǎn)單。本文包括 Python 中合并排序算法的實(shí)現(xiàn)步驟。

您還應(yīng)該知道，在不同情況下，合并排序方法的執(zhí)行時(shí)間的時(shí)間復(fù)雜度在最佳、最差和平均情況下保持不變。建議在以下情況下使用合并排序算法：

處理較大的數(shù)據(jù)集時(shí)，請(qǐng)使用合并排序算法。與其他排序算法相比，合并排序在小數(shù)組上的性能較差。

鏈表中的元素引用了列表中的下一個(gè)元素。這意味著在合并排序算法操作中，指針是可修改的，使得元素的比較和插入具有恒定的時(shí)間和空間復(fù)雜性。

確定數(shù)組是未排序的。即使在排序的數(shù)組上， Merge-sort 也會(huì)執(zhí)行其操作，這是對(duì)計(jì)算資源的浪費(fèi)。

當(dāng)考慮到數(shù)據(jù)的穩(wěn)定性時(shí)，使用合并排序。穩(wěn)定排序涉及保持?jǐn)?shù)組中相同值的順序。與未排序的數(shù)據(jù)輸入相比，穩(wěn)定排序中整個(gè)數(shù)組中相同值的順序在排序后的輸出中保持在相同的位置。

關(guān)于作者

Richmond Alake 是一名機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺工程師，他與多家初創(chuàng)公司和公司合作，整合深度學(xué)習(xí)模型，以解決商業(yè)應(yīng)用中的計(jì)算機(jī)視覺任務(wù)。

審核編輯：郭婷