我猜是因为它只比较A[k]和A[k-1]，并在一次遍历中进行实现，但仍然不太清楚。有人能更好地解释一下吗？ 谢谢
4个回答
5
这个链接展示了不同类型数据集的排序算法的图形化表示。
如您所见，当数据被排序后，算法的复杂度降至N，即输入元素的数量。
提供的链接清晰地展示了它的更高效性。
- Kishore Bandi
2
谢谢！那帮了很多。 - Katrina
不客气，请问您能接受答案并结束问题吗？ - Kishore Bandi
4
你已经回答了自己的问题：对于接近排序的数组，插入排序只需要少数几个
O(n)遍历即可完成。相比之下，像归并排序这样的分治排序算法需要O(n*lgn)的时间。对于任何非微不足道的n值，分治算法都需要许多O(n)次遍历，即使数组几乎完全排序，插入排序也可能仅需要很少的遍历次数。- Tim Biegeleisen
0
排序算法的一般目标是尽量减少比较次数。排序算法对比较次数有一个下限和上限（归并排序和堆排序的最坏情况下为n log n，快速排序的平均情况下为n log n）。在最一般的情况下，你会选择一个具有最佳平均或最佳最坏比较次数的算法。然而，当你了解数据的某些信息时（例如，数组已经排序或几乎排序），你可以利用插入排序的下限远远低于“n log n”排序的事实。
例如，如果你有一个数组[1,2,3,4,5,6,7,9]，需要将8插入其中，你可以将其插入到末尾，并使用普通的n log n排序对数组进行排序（大约需要28次比较来将数据排序为[1,2,3,4,5,6,7,8,9]）。然而，插入排序只需要大约8次比较就可以让你将8插入到正确的位置。
例如，如果你有一个数组[1,2,3,4,5,6,7,9]，需要将8插入其中，你可以将其插入到末尾，并使用普通的n log n排序对数组进行排序（大约需要28次比较来将数据排序为[1,2,3,4,5,6,7,8,9]）。然而，插入排序只需要大约8次比较就可以让你将8插入到正确的位置。
- Srikanth
0
插入排序是一种比选择排序更快、更改进的排序算法。在选择排序中，算法通过每次遍历所有数据来进行排序，无论它是否已经排序。然而，插入排序的工作方式不同，它只遍历需要排序的数据段，直到该段被排序为止，而不是在每次遍历后遍历所有数据。同样，插入排序需要两个循环和两个主要变量，这些变量在本例中被命名为“i”和“j”。在第一个循环的每次遍历之后，“i”和“j”变量从相同的索引开始，只有当变量“j”大于索引0且arr[j] < arr[j - 1]时，第二个循环才会执行。换句话说，如果“j”没有达到数据的末尾，并且“j”所在的索引处的值小于“j”左侧索引处的值，则最终将减少“j”。只要第二个循环满足这两个条件，它就会继续执行，这就是插入排序与选择排序的区别所在。只有需要排序的数据才会被排序。
- Zohaib Nauman
2
2这是一个可以的答案，但完全无法阅读。请将您的文本拆分成短段落，并使用提供的工具格式化代码示例。这样很可能会吸引投票；至少我的投票会。 - Boris the Spider
好的，我会将它与其他算法进行比较，也会积极采纳您的建议，谢谢。 - Zohaib Nauman
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接