C／C++ 七大排序算法 之 “插入排序”

排序：即将一组混乱的数据按从小到大或者从大到小的顺序进行有序的排列出来。

思路解答：

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
   重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
4. 将新元素插入到该位置；
   重复步骤 2~5。

时间复杂度： O(n²)

代码实现：

插入排序的另一种实现方式

插入排序是通过构建有序数组元素的存储，对未排序的数组元素在已排序的数组中从最后一个元素向第一个元素遍历，找到相应位置并插入。

其中，待排序数组的第1个元素被看作是是一个有序的数组，从第2个至最后一个元素被看作是一个无序数组。

从小到大的排序的顺序完成插入排序，具体排序过程如下图：

从图中可以看出，插入排序比较的次数与无序数组的长度相等，每次无序数组元素与有序数组中的所有元素进行比较，比较完成后找到对应位置插入，最后可得到一个有序数组。

具体插入排序算法代码如下：