算法在數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)領(lǐng)域很常見(jiàn)。算法為社交媒體應(yīng)用程序、谷歌搜索結(jié)果、銀行系統(tǒng)等提供動(dòng)力。因此，數(shù)據(jù)科學(xué)家和 機(jī)器學(xué)習(xí) 實(shí)踐者在分析、設(shè)計(jì)和實(shí)現(xiàn)算法方面擁有直覺(jué)是至關(guān)重要的。

當(dāng)應(yīng)用于大規(guī)模計(jì)算任務(wù)時(shí)，高效算法為公司節(jié)省了數(shù)百萬(wàn)美元，并減少了內(nèi)存和能源消耗。本文介紹了一種簡(jiǎn)單的算法，插入排序。

雖然知道如何實(shí)現(xiàn)算法是必不可少的，但本文也包括了數(shù)據(jù)科學(xué)家在選擇利用時(shí)應(yīng)該考慮的插入算法的細(xì)節(jié)。因此，本文提到了算法復(fù)雜性、性能、分析、解釋和利用等因素。

為什么？

重要的是要記住為什么數(shù)據(jù)科學(xué)家應(yīng)該在解釋和實(shí)現(xiàn)之前研究數(shù)據(jù)結(jié)構(gòu)和算法。

數(shù)據(jù)科學(xué)和 ML 庫(kù)和包抽象了常用算法的復(fù)雜性。此外，由于抽象，需要 100 行代碼和一些邏輯推導(dǎo)的算法被簡(jiǎn)化為簡(jiǎn)單的方法調(diào)用。這并沒(méi)有放棄數(shù)據(jù)科學(xué)家研究算法開(kāi)發(fā)和數(shù)據(jù)結(jié)構(gòu)的要求。

當(dāng)給定一組要使用的預(yù)構(gòu)建算法時(shí)，確定哪種算法最適合這種情況需要了解基本算法的參數(shù)、性能、限制和魯棒性。數(shù)據(jù)科學(xué)家可以在分析并在某些情況下重新實(shí)現(xiàn)算法后了解所有這些信息。

選擇正確的特定于問(wèn)題的算法和排除算法故障的能力是理解算法的兩個(gè)最重要的優(yōu)勢(shì)。

K-Means 、 BIRCH 和 Mean Shift 都是常用的 clustering 算法，數(shù)據(jù)科學(xué)家決不具備從頭開(kāi)始實(shí)施這些算法的知識(shí)。盡管如此，數(shù)據(jù)科學(xué)家仍有必要了解每種算法的特性及其對(duì)特定數(shù)據(jù)集的適用性。

例如，基于質(zhì)心的算法有利于高密度數(shù)據(jù)集，在這些數(shù)據(jù)集中可以清楚地定義集群。相反，在處理噪聲數(shù)據(jù)集時(shí)，首選基于密度的算法，如 DBSCAN （基于密度的帶噪聲應(yīng)用程序空間聚類(lèi)）。

在排序算法的上下文中，數(shù)據(jù)科學(xué)家遇到了數(shù)據(jù)湖和數(shù)據(jù)庫(kù)，在這些數(shù)據(jù)湖和數(shù)據(jù)庫(kù)中，如果對(duì)包含的數(shù)據(jù)進(jìn)行排序，則遍歷元素以識(shí)別關(guān)系的效率更高。

識(shí)別適用于數(shù)據(jù)集的庫(kù)子例程需要了解各種排序算法和首選的數(shù)據(jù)結(jié)構(gòu)類(lèi)型。使用數(shù)組時(shí)，快速排序算法是有利的，但如果數(shù)據(jù)以鏈表形式顯示，則合并排序的性能更高，尤其是在大數(shù)據(jù)集的情況下。不過(guò)，兩者都使用分而治之的策略對(duì)數(shù)據(jù)進(jìn)行排序。

出身背景

什么是排序算法？

排序問(wèn)題是數(shù)據(jù)科學(xué)家和其他軟件工程師面臨的一個(gè)眾所周知的編程問(wèn)題。排序問(wèn)題的主要目的是按升序或降序排列一組對(duì)象。排序算法是執(zhí)行的順序指令，用于將列表或數(shù)組中的元素有效地重新排序?yàn)樗璧捻樞颉?/p>

分類(lèi)的目的是什么？

在數(shù)據(jù)領(lǐng)域中，數(shù)據(jù)集中元素的結(jié)構(gòu)化組織支持高效遍歷和快速查找特定元素或組。在宏觀層面上，使用高效算法構(gòu)建的應(yīng)用程序轉(zhuǎn)化為引入我們生活的簡(jiǎn)單性，如導(dǎo)航系統(tǒng)和搜索引擎。

插入排序是什么？

插入排序算法涉及基于列表中每個(gè)元素與其相鄰元素的迭代比較創(chuàng)建的排序列表。

指向當(dāng)前元素的索引指示排序的位置。排序開(kāi)始時(shí)（索引= 0 ），將當(dāng)前值與左側(cè)相鄰的值進(jìn)行比較。如果該值大于當(dāng)前值，則不修改列表；如果相鄰值和當(dāng)前值是相同的數(shù)字，也會(huì)出現(xiàn)這種情況。

但是，如果當(dāng)前值左側(cè)的相鄰值較小，則相鄰值位置將向左移動(dòng)，并且僅當(dāng)其左側(cè)的值較小時(shí)才停止向左移動(dòng)。

該圖說(shuō)明了插入算法在未排序列表上執(zhí)行的步驟。下圖中的列表按升序排列（從低到高）。

圖 1 ： GIF 中的插入排序 （此文件在 Creative Commons 下獲得許可）。

算法步驟和實(shí)現(xiàn)（ Python 和 JavaScript ）

臺(tái)階

要按升序排列元素列表，插入排序算法需要以下操作：

從未排序元素的列表開(kāi)始。

從第一項(xiàng)到最后一項(xiàng)遍歷未排序元素的列表。

在每個(gè)步驟中，將當(dāng)前元素與前面所有位置左側(cè)的元素進(jìn)行比較。

如果當(dāng)前元素小于前面列出的任何元素，則將其向左移動(dòng)一個(gè)位置。

Python 實(shí)現(xiàn)

JavaScript 實(shí)現(xiàn)

性能和復(fù)雜性

在計(jì)算機(jī)科學(xué)領(lǐng)域，“大 O ”表示法是一種測(cè)量算法復(fù)雜性的策略。在這里，我們不會(huì)對(duì)大 O 符號(hào)太過(guò)技術(shù)化。不過(guò)，值得注意的是，計(jì)算機(jī)科學(xué)家使用這個(gè)數(shù)學(xué)符號(hào)來(lái)根據(jù)時(shí)間和空間需求對(duì)算法進(jìn)行量化。

大 O 表示法是根據(jù)輸入定義的函數(shù)。字母“ n ”通常表示函數(shù)輸入的大小。簡(jiǎn)單地說(shuō)， n 表示列表中的元素?cái)?shù)。在不同的場(chǎng)景中，實(shí)踐者關(guān)心函數(shù)的最壞情況、最佳情況或平均復(fù)雜度。

插入排序算法的最壞情況（和平均情況）復(fù)雜度為 O （ n 2）。這意味著，在最壞的情況下，對(duì)列表進(jìn)行排序所需的時(shí)間與列表中元素?cái)?shù)量的平方成正比。

插入排序算法的最佳時(shí)間復(fù)雜度為 O （ n ）時(shí)間復(fù)雜度。這意味著對(duì)列表進(jìn)行排序所需的時(shí)間與列表中元素的數(shù)量成正比；當(dāng)列表的順序已經(jīng)正確時(shí)，就是這種情況。在這種情況下，只有一次迭代，因?yàn)楫?dāng)列表已經(jīng)有序時(shí)，內(nèi)部循環(huán)操作是微不足道的。

插入排序常用于排列小列表。另一方面，插入排序并不是處理包含大量元素的大型列表的最有效方法。值得注意的是，在使用鏈表時(shí)，最好使用插入排序算法。雖然該算法可以應(yīng)用于數(shù)組中結(jié)構(gòu)化的數(shù)據(jù)，但其他排序算法，如快速排序，也可以應(yīng)用于其他排序算法。

總結(jié)

最簡(jiǎn)單的排序方法之一是插入排序，它涉及一次一個(gè)元素構(gòu)建一個(gè)排序列表。通過(guò)將每個(gè)未檢查的元素插入排序列表中，在小于它和大于它的元素之間進(jìn)行排序。正如本文所演示的，這是一個(gè)簡(jiǎn)單的算法，可以在多種語(yǔ)言中掌握和應(yīng)用。

通過(guò)清晰地描述插入排序算法，伴隨著所涉及的算法程序的逐步分解。數(shù)據(jù)科學(xué)家能夠更好地實(shí)現(xiàn)插入排序算法，并探索其他類(lèi)似的排序算法，如快速排序和氣泡排序等。

對(duì)于許多數(shù)據(jù)科學(xué)家來(lái)說(shuō)，算法可能是一個(gè)敏感的話題。這可能是由于主題的復(fù)雜性。“算法”一詞有時(shí)與復(fù)雜性有關(guān)。有了適當(dāng)?shù)墓ぞ?、培?xùn)和時(shí)間，即使是最復(fù)雜的算法，當(dāng)您有足夠的時(shí)間、信息和資源時(shí)也很容易理解。算法是數(shù)據(jù)科學(xué)中使用的基本工具，不容忽視。

關(guān)于作者

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

審核編輯：郭婷