插入排序 by Python

最好时间复杂度：O(n)
最坏时间复杂度：O(n²)
平均时间复杂度：O(n²)
空间复杂度：O(1)
是否为稳定排序：Yes
sort in place：Yes
python 实现：

class Solution:
    def insertionSort(self, nums):
        m = 0
        for i in range(1, len(nums)):
            val = nums[i]
            for j in range(i, -1, -1):
                m = j
                if nums[j-1] > val:
                    nums[j] = nums[j-1]
                else:
                    break
            nums[m] = val
        return

if __name__ == "__main__":
    nums = [20,1,3,2,4,6,8,4,5,6,7,3,2,1,10,15,21,12]
    s = Solution()
    s.selectionSort(nums)
    print(nums)