目录

DSA - 插入排序(Insertion Sort)

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

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

插入排序如何工作?

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

未排序的数组

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

插入排序

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

插入排序

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

插入排序

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

插入排序

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

插入排序

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

插入排序

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

插入排序

所以我们交换它们。

插入排序

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

插入排序

因此,我们也交换它们。

插入排序

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

插入排序

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

插入排序

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

算法 (Algorithm)

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

<b class="notranslate">Step 1</b> − If it is the first element, it is already sorted. return 1;
<b class="notranslate">Step 2</b> − Pick next element
<b class="notranslate">Step 3</b> − Compare with all elements in the sorted sub-list
<b class="notranslate">Step 4</b> − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
<b class="notranslate">Step 5</b> − Insert the value
<b class="notranslate">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编程语言中的插入排序实现,请单击此处

↑回到顶部↑
WIKI教程 @2018