python 插入排序_python插入排序

插入排序首先将数列分成两部分。数列的第一个数为left部分， 其他的数为right部分。然后将right部分中的数逐一取出，插入left 部分中合适的位置。当right部分为空时，left部分就成为了一个有序 数列

import timeit
import random
 
def randomList(n):
    '''返回一个长度为n的整数列表，数据范围[0,1000) '''
    iList = []
    for i in range(n):
        iList.append(random.randrange(1000))
    return iList
 
def insertionSort(iList):
    if len(iList) <= 1:
        return iList
    for right in range(1, len(iList)):
        ##将一个序列分为左右两边
        target = iList[right]
        for left in range(0, right):
            #将左右
            if target <= iList[left]:
                iList[left+1:right+1] = iList[left:right] #使用Python的切片赋值
                iList[left] = target
                break
        print("第 %d 轮排序结果:" %(right), end="")
        print(iList)
    return iList
 
if __name__ == "__main__":
    iList = randomList(20)
    print(iList)
    print(insertionSort(iList))
    # print(timeit.timeit("insertionSort(iList)", "from __main__ import insertionSort,iList", number=100))