在插入排序算法中，相等的元素是否保留其顺序？

Question

在Robert Lafore的《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，我们仍然向左移动一步，并将tmp插入到a[in - 1]之前，在原始数组中tmp在a[in - 1]右侧。

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

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

- ITisha

---

“有序的项保持它们的顺序”适用于所有（正确的）排序算法，这是根据定义的。稳定排序意味着相等的项目保留它们的顺序。 - Blorgbeard

从我所看到的心理调试来看，算法不稳定，因此是错误的，应该是 > temp。你应该通过真正的调试来验证它。 - Oleg

尝试调试，“> =”更改顺序，而“>”似乎工作正常。示例中似乎存在错误，我简直不敢相信。 - ITisha

有时候会发生这种情况...。有时出版商或作者会在网上发布修复补丁。请检查是否发生了这种情况，如果没有，请考虑发送电子邮件给他们。 - Oleg

你可以在这里完成它（http://www.informit.com/store/data-structures-and-algorithms-in-java-9780672324536），有可能你是第一个注意到的人。 - Oleg

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"。 很高兴你能注意到它。

- Aakash Choubey