插入排序算法运行库

Question

当我发现一个版本的插入排序比另一个版本的插入排序的运行时更快时，我试图看到不同排序算法在运行时的差异。算法的版本似乎几乎相同(仅差1)。我不知道为什么。一个版本(较慢的版本)来自w3resource，另一个版本(更快的版本)来自极客健忘者。我正在用python进行比较。

极客为极客

def insertion_sort_geeks(a):
    """
    https://www.geeksforgeeks.org/insertion-sort/
    :param a: Array
    :return:  time to sort
    """
    start = time.time()
    for i in range(1, len(a)):
        current_val = a[i]
        j = i - 1
        while j >= 0 and a[j] > current_val:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = current_val
    end = time.time()
    return end - start

W3Resource算法

def insertion_sort_w3(a):
    """
    https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php
    :param a: array
    :return: time to sort
    """
    start = time.time()
    for i in range(1, len(a)):
        current_val = a[i]
        j = i
        while j > 0 and a[j - 1] > current_val:
            a[j] = a[j - 1]
            j -= 1
        a[j] = current_val
    end = time.time()
    return end - start

当我运行这些算法时，我总是发现极客健忘算法更快，但我无法弄清楚为什么？

-对10,000个ints进行排序(随机)

Insertion Sort Geek     Insertion Sort W3
4.727362155914307       5.441751718521118
4.595118761062622       5.537100791931152
4.742804050445557       5.453729867935181
4.684415102005005       5.44006609916687
4.790072202682495       5.50256085395813
4.789106845855713       5.894493818283081
5.104598045349121       6.107465982437134
5.100121021270752       5.738892078399658
4.825102090835571       5.55505895614624
4.877285003662109       5.7944769859313965

https://github.com/ShamsAnsari/Algorithms

https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-6.php https://www.geeksforgeeks.org/insertion-sort/

Answer 1

最上面的一个定义了每一个外循环一次j。10.000次。在底部的一个，你必须降低j在每一个内环控制进行测试。这是(10.000 * 10.000 - 10.000)/2作为上限(感谢@trincot纠正这个)操作更多。

较慢版本：

j = i
       while j > 0 and a[j - 1] > current_val:

更快的版本：

j = i - 1
        while j >= 0 and a[j] > current_val:

我认为AJ-1是主要的区别。