本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
插入排序是一种最容易理解的排序，我给搓麻将和打牌的大妈都能讲明白。因为，它和打牌一样，每当接到一张牌，我们都选择性的插入到手中已有序的牌中。
插入排序往往会和冒泡排序拿来相比之下，主要原因是，插入排序比冒泡排序更受欢迎！比如，我们把执行一个赋值语句的时间粗略地计为单位时间（unit_time)，然后分别用冒泡排序和插入排序对同一个逆序度是 K 的数组进行排序。用冒泡排序，需要k次交换操作，每次需要3个赋值语句，所以交换操作总耗时就是 3*K 单位时间。而插入排序中数据移动操作只需要 K 个单位时间。这也是，很多底层系统宁愿选插入排序也不愿选冒泡排序的原因之一。虽然，冒泡排序不管怎么优化，元素交换的次数是一个固定值，就是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序度。
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
将有n个元素的数组排序。 最佳情况就是，数组已经是正序排列了，在这种情况下，需要进行的比较操作是（n-1）次即可。 最坏情况就是，数组是反序排列，那么此时需要进行的比较共有n(n-1)/2次。 插入排序的赋值操作是比较操作的次数加上(n-1）次。
以数据结构为数组为例，插入排序的最坏时间复杂度 O(n^2)、最优时间复杂度 O(n)、平均时间复杂度 O(n^2)、最坏空间复杂度总共O(n) ，需要辅助空间 O(1)。
排序过程：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
插入排序的 Java 案例代码如下所示：
public void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
}也或者类似下面的这种实现方式：
//将arr[i] 插入到arr[0]...arr[i - 1]中
public static void insertion_sort(int[] arr) {
for (int i = 1; i < arr.length; i++ ) {
int temp = arr[i];
int j = i - 1;
//如果将赋值放到下一行的for循环内, 会导致在第10行出现j未声明的错误
for (j >= 0 && arr[j] > temp; j-- ) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}排序动态效果图如下所示：
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需 n-1 次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有 n*(n-1)/2 次。插入排序的赋值操作是比较操作的次数减去 n-1 次，（因为 n-1 次循环中，每一次循环的比较都比赋值多一个，多在最后那一次比较并不带来赋值）。平均来说插入排序算法复杂度为 O(n^2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千；或者若已知输入元素大致上按照顺序排列，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在 STL 的 sort 算法和 stdlib 的 qsort 算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
插入排序还可以采用二分查找法来减少“比较操作”的数目，这样的算法可以认为是插入排序的一个变种，称为二分查找插入排序。
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！