插入排序（Insertion Sort）

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

按顺序搜索数组，移动未排序的项并将其插入排序的子列表（在同一数组中）。 该算法不适用于大数据集，因为其平均和最差情况复杂度为0（n ² ），其中n是项目数。

插入排序如何工作？

我们以一个未排序的数组为例。

插入排序比较前两个元素。

它发现14和33都已按升序排列。 目前，14位于已排序的子列表中。

插入排序向前移动并将33与27进行比较。

并发现33不在正确的位置。

它将33与27交换。它还检查已排序子列表的所有元素。 在这里，我们看到排序的子列表只有一个元素14，而27大于14.因此，排序的子列表在交换后仍然排序。

到目前为止，我们在已排序的子列表中有14和27。 接下来，它将33与10进行比较。

这些值不是按排序顺序排列的。

所以我们交换它们。

但是，交换使27和10未分类。

因此，我们也交换它们。

我们再次以未排序的顺序找到14和10。

我们再次交换它们。 到第三次迭代结束时，我们有一个包含4个项目的已排序子列表。

此过程将继续，直到排序的子列表中包含所有未排序的值。 现在我们将看到插入排序的一些编程方面。

算法 (Algorithm)

现在我们对这种排序技术的工作原理有了更大的了解，因此我们可以推导出简单的步骤来实现插入排序。

<b>Step 1</b> − If it is the first element, it is already sorted. return 1;
<b>Step 2</b> − Pick next element
<b>Step 3</b> − Compare with all elements in the sorted sub-list
<b>Step 4</b> − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
<b>Step 5</b> − Insert the value
<b>Step 6</b> − Repeat until list is sorted

伪代码 (Pseudocode)

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

要了解C编程语言中的插入排序实现，请单击此处 。