Data Structures Algorithms 简明教程
Insertion Sort Algorithm
插入排序是一种非常简单的方法，按升序或降序对数字进行排序。此方法遵循增量方法。可以将它与在玩游戏时对卡片进行排序技术进行比较。
这是一个基于比较的就地排序算法。在这里，始终维护一个已排序的子列表。例如，数组的下半部分被维护为已排序。一个要“插入”到此已排序子列表中的元素，必须找到它合适的位置，然后必须在那里插入。因此得名， insertion sort 。
对数组进行顺序搜索，将未排序的项目移动并插入到已排序的子列表中（在同一数组中）。此算法不适用于大数据集，因为它的平均和最坏情况复杂度为 Ο(n2)，其中 n 是项目数。
Insertion Sort Algorithm
现在，我们对这种排序技术如何工作有了更大的了解，因此我们可以得出可以实现插入排序的简单步骤。
*步骤 1 *− 如果它是第一个元素，则它已经排序。返回 1；
*步骤 2 *− 挑选下一个元素
*步骤 3 *− 在已排序的子列表中与所有元素进行比较
步骤 4 − 移动已排序子列表中大于待排序值的所有元素
步骤 5 − 插入值
步骤 6 − 重复执行，直到列表排序完成
Pseudocode
Algorithm: Insertion-Sort(A)
for j = 2 to A.length
key = A[j]
i = j – 1
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i -1
A[i + 1] = keyExample
我们对示例采用了未排序的数组。
插入排序将前两个元素进行比较。
它发现 14 和 33 已按升序排列。现在，14 在已排序子列表中。
插入排序继续并比较 33 和 27。
并发现 33 未处于正确位置。它将 33 与 27 交换。它还将已排序子列表的所有元素进行检查。在此，我们看到已排序子列表仅包含一个元素 14，而 27 大于 14。因此，已排序子列表在交换后仍保持已排序状态。
现在已排序子列表中包含 14 和 27。接下来，它将 33 与 10 进行比较。这些值未按排序顺序排列。
因此它们被交换。
但是，交换会使 27 和 10 无序。
因此，我们也对它们进行交换。
我们再次发现 14 和 10 未按排序顺序排列。
我们再次对它们进行交换。
在第三次迭代结束时，我们得到了包含 4 个条目的已排序子列表。
此过程将一直持续到已排序子列表中包含所有未排序值为止。现在，我们将看到插入排序的一些编程方面的知识。