为什么插入排序在排序的列表上运行O（n^2）？

Question

我在用Python做算法分析，简而言之，我遇到了一个问题。我需要分析排序数组上插入排序的运行时，因此我有以下代码

def insertionSort(arr1):
  t1 = time.time();
  insertion_sort.sort(arr1)
  t2 = time.time();
  print (len(arr1));
  print (str(t2-t1));
...
print ('Insertion Sort Beginning');

for x in range(0,15):
  #Creates arrays of various sizes with integers from 0-100 randomly sprawled about. They are named after the power of 10 the size is
  toSort1 = [randint(0,100)] * randint(100000,10000000);
  #Presorts the array, insertion sort is faster for small inputs
  sorted_list = insertion_sort.sort(toSort1);
  ##################################
  insertionSort(sorted_list);

问题是这个的输出是O（n^2）！我是Python新手，所以我想这可能是一个我没有发现的语义错误。insertion_sort应该被认为是正确的，但是可以被审查here。只有在定时时按相反顺序排序，但实际上是两次传递给同一个分拣机时，才会出现这种情况。怎么会这样？你知道吗

这是输出的图形表示

Answer 1

我得到了你程序的线性时间结果。

我添加了插入排序的实现，并对代码进行了少量修改，如下所示。你知道吗

from random import randint
import time

def insertion_sort(arr):

    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):

        key = arr[i]

        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key

def insertionSort(arr1):
  t1 = time.time();
  insertion_sort(arr1)
  t2 = time.time();
  print str(len(arr1)) + ", " +  str(t2-t1)


print ('Insertion Sort Beginning');

for x in range(0,15):
  #Creates arrays of various sizes with integers from 0-100 randomly sprawled about. They are named after the power of 10 the size is
  toSort1 = [randint(0,100)] * randint(100000,10000000);
  #Presorts the array, insertion sort is faster for small inputs
  sorted_list = sorted(toSort1);
  ##################################
  insertionSort(sorted_list);

希望有帮助！你知道吗