这个算法可以称为插入排序还是其他算法？

Question

def insertionsort(ar):
    j = None
    for i in range(0, len(ar)):
        j = i + 1
        while j != len(ar):
            if ar[j] < ar[i]:
                ar[j], ar[i] = ar[i], ar[j]
            j += 1
    return ar

我很好奇这种排序方式能不能叫插入排序，我的代码与原始实现之间存在一些差异。在插入排序中，我们从虚拟 'unsorted' 子数组中选取键，并将其与已排序的左子数组进行比较。我的代码没有这样做，它从左边的子数组中选择键并将它们与右边的子数组进行比较，如果遇到一个元素使得键 > current_element 它交换这两个。我的代码和原始代码之间有一些相似之处，一个是它们都需要 O(n^2) 时间，而且左边的子数组总是排序的，基本上，这就是我选择键的方式以及将它们插入正确位置的方式地点不同

随时欢迎任何想法或意见，谢谢！ 2.

Answer 1

Insertion sort 从输入中取出下一个值，在已经排序的子数组中找到它的插入点，然后将它插入到那里。一些特点：

内部迭代查找索引，ar[i] 应该移动到该索引。
内部迭代将遍历 sorted 子数组。
排序后的子数组通过插入增长，不一定通过附加到它。

Selection sort 在未排序的子数组中找到最小值并将其追加到已排序的子数组中。一些特点：

内部迭代查找应移动到给定索引 i.

value

内部迭代将遍历 未排序 子数组。
已排序的子数组通过追加增长。

根据这些特征验证，你的算法不是插入排序，更像是选择排序。

您的实现与标准选择排序仍略有不同：

它每次外迭代执行多次交换，而标准选择排序每次外迭代最多执行一次交换。
它使用 ar[i] 存储到目前为止在未排序子数组中找到的最小值，而标准选择排序保留找到该最小值的位置的索引。

为了进行比较，我首先建议对内部循环使用更多 pythonic 代码。这相当于你拥有的：

def selectionsort(ar):
    for i in range(0, len(ar)):
        for j in range(i + 1, len(ar)):
            if ar[j] < ar[i]:
                ar[j], ar[i] = ar[i], ar[j]
    return ar

以下是该代码如何成为标准选择排序：

def selectionsort(ar):
    for i in range(0, len(ar)):
        k = i
        for j in range(i + 1, len(ar)):
            if ar[j] < arr[k]:
                k = j  # Don't swap, just remember...
        if k > i:  # Now perform just one swap:
            ar[k], ar[i] = ar[i], ar[k]
    return ar

这个算法可以称为插入排序还是其他算法？

Can this algorithm be called insertion sort or is it some other algorithm?

python

list

algorithm

sorting

insertion-sort