Python中的插入排序算法,插入排序的優缺點,中級python技術點

2021-01-07 叮噹大數據

像冒泡排序一樣，插入排序算法也易於實現和理解。但是與冒泡排序不同，它通過將每個項目與列表的其餘部分進行比較並將其插入正確的位置，來一次構建一個列表。此「插入」過程為算法命名。

一個很好的類比來解釋插入排序是您對一副紙牌進行排序的方式。想像一下，您手裡拿著一組卡片，並且想要按順序排列它們。首先，將一張卡片與其餘卡片進行逐步比較，直到找到正確的位置為止。屆時，您需要將卡插入正確的位置，然後重新開始製作新卡，重複進行直到您手上的所有卡都被排序為止。

在Python中實現插入排序

插入排序算法的工作原理與紙牌示例完全相同。這是Python中的實現：

與冒泡排序不同，此插入排序的實現通過將較小的項目向左推來構造排序列表。讓我們insertion_sort()逐行細分：

第4行建立了一個循環，該循環確定key_item函數在每次迭代期間的位置。請注意，循環從列表中的第二個項目開始，一直到最後一個項目。第7行key_item使用函數嘗試放置的項目進行初始化。第12行初始化一個變量，該變量將連續指向左側的每個元素key item。這些是將與連續比較的元素key_item。第18行key_item使用while循環將每個值與左側的值進行比較，將元素移位以留出放置空間key_item。第27行在算法將所有較大的值向右移動之後將key_item放置在正確的位置。下圖顯示了對數組進行排序時算法的不同迭代[8, 2, 6, 4, 5]：

現在，這裡是對數組進行排序時算法步驟的摘要：

該算法始於key_item = 2子數組，然後通過其左側的子數組以找到正確的位置。在這種情況下，子數組為[8]。由於2 < 8，算法會將元素8向右移動一個位置。此時的結果數組為[8, 8, 6, 4, 5]。由於子key_item數組中沒有其他元素，因此將放置在新位置，最終數組為[2, 8, 6, 4, 5]。第二遍從key_item = 6此處開始並經過位於其左側的子數組，在這種情況下為[2, 8]。由於6 < 8，算法向右移8。此時的結果數組為[2, 8, 8, 4, 5]。由於6 > 2，該算法不需要繼續遍歷子數組，因此可以定位key_item並完成第二遍。此時，結果數組為[2, 6, 8, 4, 5]。列表的第三遍將元素放置4在正確的位置，第四遍將元素5放置在正確的位置，對數組進行排序。測量插入排序的大O運行時複雜度

與您的冒泡排序實現類似，插入排序算法具有兩個嵌套循環，遍歷整個列表。內部循環非常有效，因為它僅遍歷列表，直到找到元素的正確位置為止。也就是說，該算法在平均情況下仍具有O（n 2）運行時複雜度。

最壞的情況發生在所提供的數組以相反順序排序時。在這種情況下，內部循環必須執行每個比較，以將每個元素放置在正確的位置。這仍然使您的運行時複雜度為O（n 2）。

最好的情況是對提供的數組進行了排序。在這裡，永遠不會執行內部循環，這會導致O（n）運行時複雜性，就像冒泡排序的最佳情況一樣。

儘管冒泡排序和插入排序具有相同的Big O運行時複雜性，但實際上，插入排序比冒泡排序有效得多。如果您查看兩種算法的實現，那麼您將看到插入排序如何減少對列表進行排序的比較。

定時插入排序實施

為了證明插入排序比冒泡排序更有效的主張，您可以對插入排序算法進行計時，並將其與冒泡排序的結果進行比較。為此，您只需要

run_sorting_algorithm()

使用插入排序實現的名稱替換對的調用：

您可以像以前一樣執行腳本：

shell

$ python sorting.py

Algorithm: insertion_sort. Minimum execution time: 56.71029764299999

請注意插入排序實現對相同數組進行排序的時間比冒泡排序實現少了大約17秒。儘管它們都是O(n2)算法，插入排序的效率更高。

分析插入排序的優點和缺點

就像冒泡排序一樣，插入排序算法的實現也很簡單。儘管插入排序是O（n 2）算法，但在實踐中它也比其他二次實現（例如冒泡排序）更有效。

有更強大的算法，包括合併排序和快速排序，但是這些實現是遞歸的，在處理小型列表時通常無法擊敗插入排序。如果列表足夠小，可以提供更快的整體實現，則某些快速排序實現甚至在內部使用插入排序。Timsort還在內部使用插入排序對輸入數組的一小部分進行排序。

也就是說，插入排序不適用於大型陣列，這為可以更有效地擴展規模的算法打開了大門。

關於算法的重要性，不用多說，python就是為大數據而生的，所有關於python算法的書籍，也有很多很多

補充：排序算法的重要性

排序算法是計算機科學中研究最深入的算法之一。您可以使用許多不同的排序實現和應用程式來使代碼更高效。

您可以使用排序來解決各種問題：

搜索：如果對列表進行排序，則搜索列表中的項目會更快。選擇：使用排序後的數據，可以根據列表與其餘項目的關係從列表中選擇項目。例如，當值以升序或降序排列時，找到第k 個最大或最小值，或找到列表的中值會容易得多。重複項：對列表進行排序後，可以非常快速地找到列表中的重複值。分布：如果對列表進行排序，則分析列表中項目的頻率分布非常快。例如，使用排序列表查找最頻繁或最少出現的元素相對簡單。

相關焦點

  • Python中排序算法的重要性,希爾排序 ShellSort,中級python技術
    Python中的Timsort算法，Timsort算法的優缺點，中級python技術點Python中的快速排序算法，快速排序的優缺點，中級python技術點Python中的合併排序算法，合併排序的優缺點，中級python技術點
  • Python中的合併排序算法,合併排序的優缺點,中級python技術點
    Python中的合併排序算法合併排序是一種非常有效的排序算法。它基於分治法，這是一種用於解決複雜問題的強大算法技術。為了正確理解分治法，您應該首先了解遞歸的概念。遞歸涉及將問題分解成較小的子問題，直到它們足夠小以至於無法解決。在編程中，遞歸通常由調用自身的函數表示。
  • Python中的快速排序算法,快速排序的優缺點,中級python技術點
    Python中的快速排序算法就像合併排序一樣，快速排序算法採用分治法的原理將輸入數組分為兩個列表，第一個包含小項目，第二個包含大項目。然後，該算法將對兩個列表進行遞歸排序，直到對結果列表進行完全排序為止。劃分輸入列表稱為對列表進行分區。
  • Python中的冒泡排序算法,冒泡排序的優缺點,中級python技術點
    Python中的冒泡排序算法冒泡排序是最直接的排序算法之一。它的名字來自於算法的工作方式:每經過一個新遍歷，列表中最大的元素就會向正確的位置「冒泡」。冒泡排序包括對列表進行多次遍歷、逐個比較元素以及交換順序混亂的相鄰項。
  • Python中的Timsort算法,Timsort算法的優缺點,中級python技術點
    Python中的Timsort算法Timsort算法被認為是一種混合排序算法，因為它採用了插入排序和合併排序的兩種方法的最佳組合。Timsort對於Python社區來說非常重要，因為它是由Tim Peters在2002年創建的，用於作為Python語言的標準排序算法。Timsort的主要特點是它利用了存在於大多數真實數據集中的已經排序的元素。
  • 算法基礎:五大排序算法Python實戰教程
    不同的排序算法很好地展示了算法設計上如何強烈的影響程序的複雜度、運行速度和效率。讓我們看一下前6種排序算法，看看如何在Python中實現它們！插入排序插入排序比冒泡排序和選擇排序既快又簡單。有趣的是，有多少人在玩紙牌遊戲時會整理自己的牌！在每個循環迭代中，插入排序從數組中刪除一個元素。
  • 排序算法之插入排序
    若您對公眾號有什麼意見或建議，請在公眾號中回復或在任意文章底部留言！排序算法在編程領域中起著舉足輕重的作用，在目標檢索、機器學習、數值計算、圖像處理等領域有著廣泛地應用。為了追本溯源，公眾號特推出常用經典排序算法系列推文，讓小夥伴們深入了解排序算法的實現原理，同時也提升matlab編程能力。
  • 玩轉算法 - Python歸併排序
    /一個元素若此時序列數不是1個則將上述序列再次歸併，形成 ceil(n/4)個序列，每個序列包含四/三個元素重複步驟2，直到所有元素排序完畢，即序列數為1算法分析最壞時間複雜度 O(nlogn)最優時間複雜度 O(nlogn)平均時間複雜度 O(nlogn)手撕代碼代碼託管於github:liuzhen153/play-algorithm-python
  • 用 python 實現各種排序算法
    /usr/bin/python  import sys    def insert_sort(a):      ''''' 插入排序    有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，    但要求插入後此數據序列仍然有序。
  • 排序算法專題之插入排序
    經典插入排序例題1.使用插入排序算法對列表a升序排序。函數名：insert_sort(a)參數表：a -- 待排序列表。返回值：該方法沒有返回值，但是會對列表的對象進行升序排序。算法思想：外層循環控制待排序數組的左邊界，即a[i:]為待排序部分；內層循環掃描a[:i]，將元素a[i]插入到適當位置def insert_sort (a):    for i in range(1, len(a)):        t, j =  ①                           while j >
  • 插入排序算法,就這麼簡單
    確定該算法重要的指標：第一是否能解決問題；第二算法運行時間，即解決問題出結果需要多少時間；還有所需的空間資源，比如內存等。很多時候，寫一個工作程序並不夠。因為遇到大數據下，運行時間就是一個重要的問題。算法性能用大 O 標記法表示。大 O 標記法是標記相對增長率，精度是粗糙的。比如 2N 和 3N + 2 ，都是 O(N)。
  • 經典 | Python實現八大排序算法,面試必備
    本文使用python實現了一些常用的排序方法。文章結構如下如下：直接插入排序希爾排序冒泡排序快速排序簡單選擇排序堆排序歸併排序基數排序上述所有的排序均寫在一個python自定義類中，作為成員函數。排序方法詳細介紹直接插入排序直接插入排序(Straight Insertion Sort)是一種最簡單的排序方法，它的基本操作是一個值插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表。如下圖所示：由上圖可知若最初始的有序表即為數組的第一個元素。
  • 八十七、Python|十大排序算法系列(上篇)
    關於排序就是下面的十大排序算法冒泡排序python實現冒泡排序的核心思想是通過從列表一端迭代循環元素，再通過一個循環讓這個元素之後的元素相鄰兩個比較，從而依次將最大值移動到最末端，如下圖示意。Python冒泡排序的代碼實現。
  • 用Python手寫五大經典排序算法,看完這篇終於懂了!
    作為Python忠實愛好者，本篇東哥將通過Python來手撕5大經典排序算法，結合例圖剖析內部實現邏輯，對比每種算法各自的優缺點和應用點。相信我，耐心看完絕對有收穫。因此，一般對大型數組進行排序的時候，不會考慮使用冒泡排序。Python中的插入排序算法像冒泡排序一樣，插入排序算法也易於實現和理解。但是與冒泡排序不同，它通過將每個元素與列表的其餘元素進行比較並將其插入正確的位置，來一次構建一個排序的列表元素。此「插入」過程為算法命名。
  • Python實現經典排序算法,再也不怕面試官讓我手寫快排了!
    算法作為程式設計師的必修課，是每位程式設計師必須掌握的基礎。本篇我們將通過Python來實現5大經典排序算法，結合例圖剖析內部實現邏輯，對比每種算法各自的優缺點和應用點。相信我，耐心看完絕對有收穫。因此，一般對大型數組進行排序的時候，不會考慮使用冒泡排序。Python中的插入排序算法像冒泡排序一樣，插入排序算法也易於實現和理解。但是與冒泡排序不同，它通過將每個元素與列表的其餘元素進行比較並將其插入正確的位置，來一次構建一個排序的列表元素。此「插入」過程為算法命名。
  • 十大經典排序算法之希爾排序算法
    今天我們要講的希爾排序雖然也是插入排序的一種，但是它是插入排序的一個高效變形，脫離了 主要思想希爾排序的思想簡單點說就是有跨度的插入排序，這個跨度會逐漸變小，直到變為 1,變為 1 的時候也就是我們之前講的簡單插入排序了。規範點的描述就是,選擇一組遞減的整數作為增量序列，最小的增量必須為 1。
  • 算法系列: 10大常見排序算法(3)插入排序
    算法介紹插入排序最好的示例是撲克牌，很多書都以抓撲克牌的過程為例子講述插入的排序過程。現在你需要將手牌從左到右按小到大排序。和選擇排序法的比較插入排序法和選擇排序法接近。在選擇排序法中，經過k次掃描（整個）數組，最初的k個元素完成排序。
  • C語言插入排序算法及代碼
    插入排序是排序算法的一種，它不改變原有的序列（數組），而是創建一個新的序列，在新序列上進行操作。這裡以從小到大排序為例進行講解。基本思想及舉例說明插入排序的基本思想是，將元素逐個添加到已經排序好的數組中去，同時要求，插入的元素必須在正確的位置，這樣原來排序好的數組是仍然有序的。
  • 算法一看就懂之「 插入排序 」
    「 插入排序 」與「 冒泡排序 」一樣都屬於時間複雜O(n*n)的排序算法，並且也都是基於元素之間比較的方式來完成排序的。不過「 插入排序 」比「 冒泡排序 」在實際應用中更廣泛一些，因為它的執行效率更高一點。一、「 插入排序 」是什麼？
  • 一文圖解 Java 源碼的插入排序算法
    排序問題，是古老，但一直流行的問題。從 ACM 接觸到現在工作，每次涉及算法，或品讀 JDK 源碼中一些算法，經常會有排序的算法出現。排序算法是為了將一組數組（或序列）重新排列，排列後數據符合從大到小（或從小到大）的次序。這樣數據從無序到有序，會有什麼好處？通過維基百科查閱資料得到：在主內存中完成的排序叫做，內部排序。那需要在磁碟等其他存儲完成的排序，叫做外部排序 external sorting。