algorithm - 将冒泡排序更改为插入排序，对迭代进行少量更改

Question

我相信以下伪代码对于冒泡排序算法是正确的：

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 1 TO 10 - I
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

如果我改变 I 和 J 的迭代模式，如下例所示，请问我是否将算法转换为插入排序？我想是的，但我很惊讶它可能如此简单，而且我看到的各种实现往往差异更大。

L = [8, 6, 7, 1, 5, 9, 4, 3, 10, 2] // 10 items
FOR I = 1 TO 9
    FOR J = 9 TO I STEP -1
        IF L[J] > L[J + 1] THEN
            TEMP = L[J]
            L[J] = L[J + 1]
            L[J + 1] = TEMP
        ENDIF
    ENDFOR J
ENDFOR I
OUTPUT L

标签： algorithmpseudocodebubble-sortinsertion-sort

Answer 1

第二种算法是冒泡排序的另一个版本。不是在每次传递时将最大值移向数组的末尾，而是将最小值移向数组的开头。在下图中，第一行是未排序的数组，随后的每一行都是执行一次内部循环后数组的状态。冒泡排序的两个值得注意的特征：

1. 行左侧的项目处于最终位置。
2. 右侧的项目也会重新排列，但不一定要重新排列到它们的最终位置。例如，在第三行，2 从数组的末尾移动到了中间。那时算法找到了 1。所以它把 2 抛在后面，开始移动 1。

下图显示了插入排序的操作。同样有两个特征值得注意：

1. 左侧的数组已排序，但元素不在其最终位置。
2. 右侧的项目完全未受影响。

插入排序的一般概念是算法（从概念上）将数组分为两部分：开始的已排序部分和末尾的未排序部分。每次执行内部循环时，它都会获取未排序部分的第一个元素，并将其向左移动，直到它正确定位在数组的已排序部分中。