java - 相等元素在插入排序算法中是否保留它们的顺序？

Question

在 Robert Lafore 的“Data Structures and Algorithms in Java”一书中指出，插入排序是一种稳定的算法。这意味着相同的项目会保留它们的顺序。

这是书中的例子:

public void insertionSort() {
    int in, out;
    for (out = 1; out < nElems; out++) // out is dividing line
    {
        long temp = a[out]; // remove marked item
        in = out; // start shifts at out
        while (in > 0 && a[in - 1] >= temp) // until one is smaller,
        {
            a[in] = a[in - 1]; // shift item right,
            --in; // go left one position
        }
        a[in] = temp; // insert marked item
    } // end for
} // end insertionSort()

在 while 循环中，我们向左移动并为 temp 变量寻找位置。即使 a[in - 1] == temp，我们仍然向左移动一步并在 a[in - 1] 之前插入 tmp而在原始数组中，tmp 位于 a[in - 1] 的右侧。

排序后数组元素的顺序发生了变化。那么这个算法如何稳定呢？难道不应该只有 a[in - 1] > temp 而不是 a[in - 1] >= temp 吗？

也许我只是犯了一个错误，没有看到明显的东西？

Answer 1

你完全正确。这是 Thomas H. Cormen 的畅销书“算法导论”中插入排序算法的片段。

INSERTION-SORT(A)
1. for j=2 to A.length
2. key = A[j]
3. // Insert A[j] into the sorted sequence A[1..j-1].
4. i = j-1
5. while i > 0 and A[i] > key
6. A[i+1] = A[i]
7. i = i-1
8. A[i+1] = key

如您所见，A[i] > key 是正确的。在您的情况下，它应该是“a[in - 1] > temp”。 很好地注意到它。 :)