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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java – 在插入排序算法中,相等的元素是否保留了它们的顺序？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1179字，纯文字阅读大概需要2分钟。

内容图文

在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循环中,我们向左走,寻找临时变量的位置.即使[in-1] == temp,我们仍然向左移动一步并在[in-1]之前插入tmp,而在原始数组中tmp则在[in-1]的右边.

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

也许我只是犯了一个错误而且看不到明显的东西？

解决方法:

你是绝对正确的.这是Thomas H. Cormen的畅销书“Introduction to Algorithms”中的插入排序算法的片段.

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]>关键是正确的.在你的情况下应该是“a [in – 1]> temp”.
很好地注意到它.

内容总结

以上是互联网集市为您收集整理的java – 在插入排序算法中,相等的元素是否保留了它们的顺序？全部内容，希望文章能够帮你解决java – 在插入排序算法中,相等的元素是否保留了它们的顺序？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---