插入排序是一種簡(jiǎn)單直觀且穩(wěn)定的排序算法。

將一個(gè)數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)。

基本思想：
每步將一個(gè)待排序的記錄，按其關(guān)鍵碼值的大小插入前面已經(jīng)排序的列表中適當(dāng)位置上，直到全部插入完為止。

將排序的數(shù)組分成兩部分：第一部分已排好序的元素，第二部分包含即待插入元素。在排序過程中，分別從待插入元素中取出元素，插入到已排好序的元素列表中。

分類：
直接插入排序，二分插入排序（又稱折半插入排序）
二分插入排序在后面的文章會(huì)寫到。

直接插入排序

實(shí)例，將用戶輸入的列表按照從小到大排列

思路：

<1> 將列表分為兩部分，一部分為已排序好的元素，另一部分為待排序的元素。（若此列表無已排好的元素，直接將第一個(gè)元素視為已拍好的部分）；

<2> 對(duì)待排序的部分進(jìn)行遍歷，從第一個(gè)開始往已排好的部分進(jìn)行插入；

<3> 假設(shè)待排序的元素坐標(biāo)為 i ，則已排好序的最后一位坐標(biāo)為 j = i-1；

<4> 將 i 與 j 坐標(biāo)所對(duì)應(yīng)的元素大小進(jìn)行比較，若待排元素 i 小，則將此時(shí)的待排元素儲(chǔ)存為臨時(shí)變量，將已排好的元素 j 向后移動(dòng)一位；

<5> 繼續(xù)向已排好序列前方進(jìn)行尋找比較。此過程中，比臨時(shí)變量大的元素均向后移一位，直到找到比臨時(shí)變量小或者到達(dá)列表頂端為止。

<6> 將剛才的臨時(shí)變量賦值到合適的位置。

代碼實(shí)現(xiàn)：

            
              
                def
              
              
                Sorting
              
              
                (
              
              self
              
                )
              
              
                :
              
              
    len_list 
              
                =
              
              
                len
              
              
                (
              
              new_list
              
                )
              
              
                for
              
               i 
              
                in
              
              
                range
              
              
                (
              
              
                0
              
              
                ,
              
               len_list
              
                -
              
              
                1
              
              
                )
              
              
                :
              
              
        j 
              
                =
              
               i
              
                -
              
              
                1
              
              
                if
              
               new_list
              
                [
              
              i
              
                ]
              
              
                <
              
               new_list
              
                [
              
              j
              
                ]
              
              
                :
              
              
            temp 
              
                =
              
               new_list
              
                [
              
              i
              
                ]
              
              
            new_list
              
                [
              
              i
              
                ]
              
              
                =
              
               new_list
              
                [
              
              j
              
                ]
              
              
            j 
              
                -=
              
              
                1
              
              
                while
              
               j 
              
                >
              
              
                0
              
              
                and
              
               new_list
              
                [
              
              j
              
                ]
              
              
                >
              
               temp
              
                :
              
              
                new_list
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               new_list
              
                [
              
              j
              
                ]
              
              
                j 
              
                -=
              
              
                1
              
              
            new_list
              
                [
              
              j
              
                +
              
              
                1
              
              
                ]
              
              
                =
              
               temp            

new_list 
              
                =
              
              
                list
              
              
                (
              
              
                input
              
              
                (
              
              
                'please input new numbers:'
              
              
                )
              
              
                )
              
              
Sorting
              
                (
              
              new_list
              
                )
              
            
          

具體的流程可以參考上圖