这是一种就地比较排序算法.这里,维护一个始终排序的子列表.例如,维护数组的下半部分以进行排序.要在此已排序的子列表中"插入"的元素必须找到其适当的位置,然后必须将其插入其中.因此,名称插入排序.
按顺序搜索数组,移动未排序的项并将其插入排序的子列表(在同一数组中).该算法不适用于大数据集,因为它的平均和最差情况复杂度为Ο(n 2 ),其中 n 是项目数.
我们为示例提供了一个未排序的数组.
插入排序比较前两个元素.
它发现14和33都已按升序排列.目前,14位于已排序的子列表中.
插入排序向前移动并将33与27进行比较.
并发现33不在正确位置.
它将33与27交换.它还检查已排序子列表的所有元素.在这里,我们看到排序的子列表只有一个元素14,27大于14.因此,排序的子列表在交换后仍然排序.
现在我们在排序的子列表中有14和27.接下来,它将33与10进行比较.
这些值不是按排序顺序.
所以我们交换他们.
然而,交换使27和10未分类.
因此,我们也交换它们.
我们再次以未排序的顺序找到14和10./p>
我们再次交换它们.到第三次迭代结束时,我们有一个有4个项目的已排序子列表.
此过程一直进行,直到排序的子列表中包含所有未排序的值.现在我们将看到插入排序的一些编程方面.
现在我们可以更全面地了解这种排序技术是如何工作的,所以我们可以我们可以通过简单的步骤来实现插入排序.
: 如果它是第一个元素,则它已经排序.返回1; : 选择下一个元素 : 与排序子列表中的所有元素进行比较 : 将已排序子列表中所有大于 值的元素移位到 : 插入值 : 重复直到列表排序
procedure insertionSort( A : array of items ) int holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* select value to be inserted */ valueToInsert = A[i] holePosition = i /*locate hole position for the element to be inserted */ while holePosition > 0 and A[holePosition-1] > valueToInsert do: A[holePosition] = A[holePosition-1] holePosition = holePosition -1 end while /* insert the number at hole position */ A[holePosition] = valueToInsert end for end procedure
To了解C编程语言中的插入排序实现.