数据结构和算法 - 插入排序

这是一种就地比较排序算法.这里，维护一个始终排序的子列表.例如，维护数组的下半部分以进行排序.要在此已排序的子列表中"插入"的元素必须找到其适当的位置，然后必须将其插入其中.因此，名称插入排序.

按顺序搜索数组，移动未排序的项并将其插入排序的子列表(在同一数组中).该算法不适用于大数据集，因为它的平均和最差情况复杂度为Ο(n ² )，其中 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编程语言中的插入排序实现.