Python|插入排序修改

说明

• 排序的定义

对一序列对象根据某个关键字进行排序。

• 术语说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 ：一个算法执行所耗费的时间。

空间复杂度 ：运行完一个程序所需内存的大小。

n: 数据规模

In-place: 占用常数内存，不占用额外内存

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

步骤1: 从第一个元素开始，该元素可以认为已经被排序；

步骤2: 取出下一个元素，在已经排序的元素序列中从后向前扫描；

步骤3: 如果该元素（已排序）大于新元素，将该元素移到下一位置；

步骤4: 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

步骤5: 将新元素插入到该位置后；

步骤6: 重复步骤2~5。

def insertSort(todoList):
    length = len(todoList)
    if length<2:
        return todoList
    for i in range(1, length):
        for j in range(0,i):
            if todoList[i]<todoList[j]:
                temp=todoList[i]
                todoList.pop(i)
                todoList.insert(j,temp)
                break
    return todoList

现在对10000个随机生成的数据进行排序，然后比较两者消耗的时间。

t1=time.time()
new1=quickSort(randomList)
t2=time.time()
print(t2-t1)

t3=time.time()
new2=insertSort(randomList)
t4=time.time()
print(t4-t3)

快速排序：

0.03491353988647461

插入排序：

16.80514669418335