数据结构与算法系列之一：八大排序之插入排序

本文主要是介绍数据结构与算法系列之一：八大排序之插入排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载请注明作者和出处：http://blog.csdn.net/u011475210
个人博客：https://wordzzzz.github.io/ && https://wordzzzz.gitee.io/
代码地址：https://github.com/WordZzzz/Note/tree/master/DS-A
博客作者：WordZzzz，一只热爱技术的文艺青年

- 插入排序
  - 前言
  - 简介
  - 步骤
  - 演示
  - 代码
  - 算法复杂度
  - 分析

插入排序

前言

建议先看排序综述，传送门：数据结构与算法系列之一：八大排序综述。

简介

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

步骤

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

演示

wikipedia的大数据规模演示：

wordzzzz的小数据规模演示：

代码

/* * 插入排序*/ template <typename T> 
void InsertSort(T *array, const int length) {if (array == NULL)throw invalid_argument("Array must not be empty"); if (length <= 0)return; for (int i = 1; i < length; ++i){                   //外循环，一次插入一个数据T tmp = array[i]; int j = i - 1;                                  //内循环，从i-1开始while (j >= 0 && array[j] > tmp){               array[j+1] = array[j]; --j; } array[j+1] = tmp; } 
}

算法复杂度

数据结构数组
最坏时间复杂度 $O(n^{2})$
最优时间复杂度 $O(n)$
平均时间复杂度 $O(n^{2})$
空间复杂度总共 $O(n)$ ，需要辅助空间 $O(1)$

分析

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 $n-1$ 次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 ${\frac {1}{2}}n(n-1)$ 次。插入排序的赋值操作是比较操作的次数减去 $n-1$ 次，（因为 $n-1$ 次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为 $O(n^{2})$ 。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。