基础排序

插入排序

菜的要死 写个插入排序都有问题

def insertSort(nums):
    for i in range(1, len(nums)): # 被插入的元素
        cur = nums[i]
        for p in range(i - 1, -1, -1):
            if nums[p] > cur:
                nums[p + 1] = nums[p]
            else: # 出现第一个 nums[p] <= cur
                nums[p + 1] = cur # p + 1是最后一个nums[p] > cur
                break
    return nums

while循环版本

def insertSort_(nums):
    for i in range(1, len(nums)):
        cur, p = nums[i], i - 1  # 存在当前位置的值 等待被填充 期望p指向最后一个小于cur的位置
        while p >= 0 and nums[p] > cur:
            nums[p + 1] = nums[p]
            p -= 1
        nums[p + 1] = cur  # 因为需要找的是最后一个大于temp的数 而出循环时 p指向的小于等于temp的数
    return nums

while循环出来的时候 是第一个不满足条件的位置

要分析清楚自己要找的是满足条件的最后一个位置还是不满足条件的第一个位置..