python - 插入排序算法：哪些代码在其结构上是高效的，怎么来的？

Question

我做了两个插入排序算法的源代码。

def insertsort(iterable) :
    
    for current in range(len(iterable)) : # 'current' is the index of the element being sorted

        compare, n = 0,0 # Initializes 'compare' and 'n' which is used in for-loop in each current for-loop
        current_value = iterable[current] # Saves the element being sorted since the corresponding space will be assigned by the leading value
        
        for compare in range(0,current) : # Compares the element from [0] to the element right ahead of [current]            
            if iterable[compare] > iterable[current] : # Finds where to insert 'current_value,' stored value of [current]

                for n in range(current,compare,-1) : # Translate the values to one space to make the space where 'current_value' will be put empty
                    iterable[n] = iterable[n-1]
                    
                iterable[compare] = current_value # Insert the saved value of [current] to the right place
                
    return(iterable)

第一个是我自己制作的，没有任何指导。

def insertsort(iterable) :
    for current in range(1,len(iterable)) : # iterable[0] is consdiered as resorted in the beginning
        current_value = iterable[current] # saving current value
        compare = current
        while 0 < compare and iterable[compare-1] > current_value : # finding out where to put the sorted current value
            iterable[compare] = iterable[compare-1] # this line in the while loop moves the elements not sorted
            compare -= 1 

        iterable[compare] = current_value # put current value into the right place that the while loop found out


    return(iterable)

第二个是我看一些网页的。

比较两个，我发现网上的第二个比我做的要短。

根据 10 次平均运行时间，第二个也展示了看似高效的性能，对 10000 个连续元素进行排序（数据 = [i for i in range(10000, 0, -1)]

它快了大约 0.4 秒，而将它们全部排序大约需要 16 秒。

但是，当使用 100,000 个连续元素进行测试时（data = [i for i in range(100000, 0 ,-1)]），第一个（我制作的）比第二个快。

第一个大约 1700 秒，比第二个快 200 秒。

这是我的问题。

1. 每个代码的时间复杂度是多少？我假设两者都是 n^2 虽然我不确定。
2. 为什么我做的那个似乎表现更好？我在第二个循环中将 for 循环和 if 语句放入 while 循环，但我猜它让它变慢了。

以防万一，我附上了我使用的时间测量方法。我提到了https://stackoverflow.com/a/1557584

标签： pythonpython-3.xalgorithmsortinginsertion-sort