logo图片
数据结构与算法

插入排序

这是一种基于就地比较的排序算法。在这里,维护一个始终排序的子列表。例如,数组的下部保持排序。一个要在这个排序的子列表中"插入"的元素必须找到它的适当位置,然后它必须被插入到那里。因此名称为 插入排序
数组被顺序搜索,未排序的项目被移动并插入到排序的子列表中(在同一个数组中)。该算法不适用于大型数据集,因为它的平均复杂度和最坏情况复杂度为 Ο(n 2),其中 n 是项目数。

插入排序的工作原理是什么?

我们以一个未排序的数组为例。
未排序数组
插入排序比较前两个元素。
插入排序
发现 14 和 33 都已经是升序了。目前,14 在已排序的子列表中。
插入排序
插入排序向前移动并将 33 与 27 进行比较。
插入排序
又发现33的位置不对。
插入排序
它将 33 与 27 交换。它还检查已排序子列表的所有元素。这里我们看到排序后的子列表只有一个元素 14,而 27 大于 14、因此,排序后的子列表在交换后保持排序状态。
插入排序
现在我们在排序的子列表中有 14 和 27、接下来,它将 33 与 10 进行比较。
插入排序
这些值没有排序。
插入排序
所以我们交换它们。
插入排序
但是,交换会使 27 和 10 未排序。
插入排序
因此,我们也交换它们。
插入排序
我们再次以未排序的顺序找到 14 和 10、
插入排序
我们再次交换它们。在第三次迭代结束时,我们有一个 4 项的排序子列表。
插入排序
这个过程一直持续到所有未排序的值都包含在排序的子列表中。现在我们将了解插入排序的一些编程方面。

算法

现在我们对这种排序技术的工作原理有了更大的了解,因此我们可以推导出实现插入排序的简单步骤。
Step 1if it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the 
         value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

伪代码

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
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4