算法學習：直接插入排序

#方法1，從后往前，逐個比較
def insertSort(arr):
    for i in range(1,len(arr)):#若有n個元素，n-1個數需要比較
        for j in range(i,0,-1):#從第i個元素開始，從后往前比較（實際從索引1開始比）
            if arr[j]<arr[j-1]:#如果比前一個數小，交換位置
                arr[j],arr[j-1]=arr[j-1],arr[j]
            else:#否則結束此次循環
                break
    return arr

print(insertSort([1,22,-1,9,23,5])) #[-1, 1, 5, 9, 22, 23]

#方法2:
def insertSort02(arr):
    i = 1
    while i<len(arr):#若有n個數字，比較n-1次
        j = i #從索引為1的元素開始比較
        while j>=1:
            if arr[j]<arr[j-1]:#若當前元素比前一個元素小，交換位置
                arr[j],arr[j-1]=arr[j-1],arr[j]
                j-=1 #接下來比較前一個元素
            else:
                break
        i+=1#繼續比較下一輪
    return arr
print(insertSort02([1,22,-1,9,23,5])) #[-1, 1, 5, 9, 22, 23]