アルゴリズム→並べ替えの挿入

並べ替えの挿入

考え方

              ，      ，            loc ，    ，    ，   
array[loc-1] < array[loc]    loc = 0 ，          loc   ，   loc      ( loc = loc -1 )
      ，      。

アルゴリズム複雑度

   挿入ソートの最悪時間複雑度はO(n)=n^2で、平均複雑度はO(n)=n^2です.
python実現

def shift_vac(arr,vac_loc,vac):
    loc = 0
    while vac_loc > 0:
        if arr[vac_loc-1] <= vac:
            loc = vac_loc
            break
        arr[vac_loc] = arr[vac_loc-1]
        vac_loc-=1

    return loc
def insert_sort(arr):
    for i in range(0,len(arr)):
        v = arr[i] 
        loc = shift_vac(arr,i,v)
        arr[loc] = v
    return arr

us = [1,2,0,-1]
us1 = [6,8,0,2,1]
print(insert_sort(us))
print(insert_sort(us1))