用Python實現(xiàn)插入排序和選擇排序

shiina 發(fā)布于2019-07-31 10:24 / 1146人閱讀

摘要：具體實現(xiàn)步驟為首先我們把整個數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個元素，就是數(shù)組的第一個元素。

這篇是我關于用Python實現(xiàn)50個經(jīng)典算法代碼的第一篇文章，主要目的是在自己手寫一遍算法之后，在文章中對算法的細節(jié)進行總結來加以鞏固。

話不多說，讓我們從最基本的排序算法開始吧

插入排序

如下圖所示，插入排序的實現(xiàn)思路顧名思義，就是不斷地在一個已經(jīng)是有序的數(shù)組中，尋找合適位置并插入新元素。

具體實現(xiàn)步驟為：

首先我們把整個數(shù)組拆分為有序區(qū)間和未排序區(qū)間，有序區(qū)間在插入排序一開始只有一個元素，就是數(shù)組的第一個元素。

接在有序區(qū)間之后的一個元素就是準備插入的元素，在圖中就是標為綠色的元素，在有序區(qū)間內(nèi)尋找位置并插入。

其尋找邏輯為：從后往前依次進行比較，如果待插入元素大于當前元素，則將待插入元素插入到當前元素的后一位，如果待插入元素小于當前元素，則將當前元素后移一位。不斷重復該過程直至到數(shù)組的最后一位

其實現(xiàn)的具體代碼為：

def insertion_sort(a):
    length = len(a)
    if length <=1:
        return 
    for i in range(1,length):
        j = i-1
        value = a[i]
        while j >=0:
            if a[j]
時間復雜計算為：我們需要將整個數(shù)組遍歷一遍，所以這一部分為O(n)，在每一次遍歷中都要執(zhí)行一次插入操作，其時間復雜度為O(n)，所以總時間復雜度為O(n2)
選擇排序
選擇排序跟插入排序算法類似，都是將數(shù)組分為有序區(qū)間和未排序區(qū)間，區(qū)別在于插入排序是將一個新元素插入到有序區(qū)間內(nèi)，而選擇排序則是在未排序區(qū)間中找到最小元素，并交換到有序區(qū)間之后。

實現(xiàn)代碼為：
def selection_sort(a):
    length = len(a)
    if length <=1:
        return
    for i in range(0,length-1):
        min_value = a[i]
        min_index = i
        j = i+1
        while j
時間復雜度計算：數(shù)組長度為n，一共需要尋找n次最小值，每次尋找最小值都要遍歷未排序區(qū)間一次，其時間復雜度為O(n)，乘以n次為O(n2)

云服務器 GPU云服務器用php實現(xiàn)插入排序實現(xiàn)插入排序選擇排序python 堆排序用python

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/43779.html

【算法日積月累】1-選擇排序

摘要：選擇排序算法實現(xiàn)實現(xiàn)選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數(shù)組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實現(xiàn)前面我們說到了，我們?yōu)榱送怀雠判蛩惴ǖ乃枷?，將所有的例子僅限在數(shù)組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

neuSnail 2019-07-31 11:21 評論0 收藏0
Github標星2w+，熱榜第一，如何用Python實現(xiàn)所有算法

摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚學會了Python基礎知識，想進階一下，那就來點算法吧！畢竟編程語言只...

zxhaaa 2019-07-31 10:23 評論0 收藏0
基本排序算法的Python實現(xiàn)

摘要：本篇主要實現(xiàn)九八大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序計數(shù)排序。希爾排序是非穩(wěn)定排序算法。歸并排序算法依賴歸并操作。但是，計數(shù)排序可以用在基數(shù)排序算法中，能夠更有效的排序數(shù)據(jù)范圍很大的數(shù)組。本篇主要實現(xiàn)九(八）大排序算法，分別是冒泡排序，插入排序，選擇排序，希爾排序，歸并排序，快速排序，堆排序,計數(shù)排序。希望大家回顧知識的時候也能從我的這...

zhangqh 2019-07-25 10:42 評論0 收藏0
python-八大算法

摘要：排序算法總結排序算法平均時間復雜度冒泡排序選擇排序插入排序希爾排序快速排序歸并排序堆排序基數(shù)排序一冒泡排序基本思想兩個數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來。排序算法總結排序算法平均時間復雜度冒泡排序O(n2) 選擇排序O(n2) 插入排序O(n2) 希爾排序O(n1.5) 快速排序O(N*logN) 歸并排序O(N*logN) 堆排序O(N*logN) 基數(shù)排序O(d(n+...

aboutU 2019-07-30 16:20 評論0 收藏0
前端面試必備——十大經(jīng)典排序算法

摘要：冒泡排序冒泡排序也是一種簡單直觀的排序算法。但希爾排序是非穩(wěn)定排序算法?？焖倥判蛴质且环N分而治之思想在排序算法上的典型應用。本質(zhì)上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。冒泡排序冒泡排序（Bubble Sort）也是一種簡單直觀的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有再需要交換，也就...

RebeccaZhong 2019-08-20 18:24 評論0 收藏0