我的排序代码是否考虑了插入排序 (Python)？

Question

我正在学习排序算法，现在 Insertion Sort。我想先根据自己对算法的理解写代码，再去网上抄代码。

我对Insertion Sort的理解是：要对list a进行排序，首先创建一个包含已排序元素的列表（称为a_sorted），第一个元素是a[0]。然后我将尝试将 a 的每个元素放入 a_sorted 中（希望我理解正确）。所以我实现了如下想法：

a = [4, 3, 1, 5, 7, 9, 6, 2]
n = len(a)

def insertion_sort(a, n):
    a_sorted = [a[0]] # Create a list contain sorted elements, first ele is a[0] => [4]
    for i in range(1,n): # Iterate through original list, from 1th ele (start from 3)

        if a[i] <= a_sorted[0]: 

# First check if the ith ele is smaller than the first ele in the sorted list (smallest). If so insert it to the start of a_sorted
# For example, a_sorted is [3,4], ith ele is 1, 1<3 so add 1 to the start of a_sorted => [1,3,4]
# Then continue to the next ith element
            a_sorted.insert(0, a[i])
            continue

        for j in range(len(a_sorted)-1,-1,-1):

# Compare ith ele to each ele of a_sorted, from largest to the smallest (right to left)
# If ith ele > jth ele in a_sorted, insert ith ele right after the position of jth ele in a_sorted
# For example ith ele is 6, a_sorted is [1, 3, 4, 5, 7, 9], then compare 6 to 9,7,5; 6>5 so insert 6 right after 5 => [1, 3, 4, 5, 6, 7, 9]
# Continue to next ith

            if a[i] > a_sorted[j]:
                a_sorted.insert(j+1, a[i])
                break

       
print(insertion_sort(a, n))

一切都很好，我得到了正确的输出。我只是尝试坚持 insert 的想法。但是当我在 google 上搜索插入排序算法的代码时。 代码看起来和我的完全不同（它无处不在所以我认为这是插入排序的标准优化代码）。下面是代码：

def insertionSort(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

它更短了。但我根本不明白它是如何工作的。不过，这不是我的问题，我的问题是：

我的代码还在考虑插入排序吗？
我的代码是否与互联网上的最优代码一样高效（时间复杂度 O(n^2) 平均，space 复杂度，...）

我只是想确保当他们要求插入排序时，我可以在面试或考试中使用我的代码。我更喜欢我的代码，因为我理解它并自己编写它，这样更容易记住。

Answer 1

是的，您的代码是 O(n²) 时间复杂度的插入排序：它维护一个排序列表，然后通过移动元素在线性时间内将项目插入到正确的位置。

您发现的常见实现有效 in-place（仅使用交换）。这意味着它有更好的 space 复杂度：它只需要常量辅助存储 O(1) 而你需要线性辅助存储 O(n) 来存储排序列表 a_sorted.

它通过将列表“划分”为“已排序”和“未排序”部分，并在每一步中不断增加“已排序”部分来做到这一点。我已经在您找到的实现中添加了注释来解释这一点。

def insertionSort(arr):
    # after this loop has run len(arr) - 1 times, the sorted part starting from the first index will have grown to the full array length and the unsorted part will be empty
    for i in range(1, len(arr)):
        # at this point, arr[:i] is sorted; you can verify this by doing
        # print(arr[:i]) here

        key = arr[i] # this element has to be inserted at the correct pos in arr[:i+1]
  
        # Move elements of arr[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position: These elements
        # have to be shifted "up" in order to allow inserting
        # the key at the right position; this step is responsible
        # for the quadratic complexity as it requires linear time
        j = i-1
        while j >= 0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        # the index to insert the key at is j, because arr[j] < key holds
        arr[j+1] = key
        # after this step, the sorted part has grown by one, from arr[:i] to arr[:i+1]

我的排序代码是否考虑了插入排序 (Python)？

Is my sorting code consider Insertion Sort (Python)?

python

sorting

algorithm

time-complexity

insertion-sort