数据机构笔记之路很遥远，但是老四没有忘记，依然按照自己的节奏更新着自己关于技术的理解，尽可能的说的明白一些，希望对能看到的人有所帮助。本文要讲的是插入排序，相对来说是比较基础的排序算法。
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序，因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
原地算法（摘自维基百科）
原地算法（in-place algorithm）基本上不需要额外辅助的数据结构，然而，允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。
一个算法有时候会错误地被称为原地算法，只因为它用它的输出数据会覆盖掉它的输入数据。事实上这条件既不充分（在快速排序案例中所展示的）也非必要；输出数据的空间可能是固定的，或如果以输出为流数据而言，也甚至是可能无法被数清楚的。另一方面来看，有时候要决定一个算法是不是原地，而数它的输出空间可能是比较可行的，像是底下的第一个的reverse示例；如此使得它更难去严格地定义原地算法。在理论上的应用像是log-space reduction，更是典型的总是忽略输出的空间（在这些状况，更重要的是输出为仅能写入）。
老样子，还是将算法动画图解的动态展示一下，看起来更直观一些。
如果觉得 gif 加载太快可以下载下来使用播放器暂停查看
Java 代码模拟插入排序基本实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
package com.glorze.sort; import java.util.Arrays; /** * 插入排序 * @author Glorze * */ public class InsertSort { public static int[] insertSort(int[] arr){ int i，j，temp; for(i=1;i<arr.length;i++){ temp=arr[i]; for(j=i-1;j>=0&&temp<arr[j];j--){ arr[j+1]=arr[j]; } arr[j+1]=temp; } return arr; } public static void main(String[] args) { int arr[]={508，113，408，659，257}; arr=InsertSort.insertSort(arr); System.out.println("插入排序:"+Arrays.toString(arr)); } } |
综上，插入排序属于基本的排序算法，是我们必须要掌握的排序算法。在排序的分类中，我们都知道插入排序、交换排序、选择排序和归并排序都归属于内排序，插入排序的时间复杂度：O(n²)，不是很优秀，但是就像和冒泡一样，十分基础，务必重视。
更博不易，如果觉得文章对你有帮助并且有能力的老铁烦请捐赠盒烟钱，点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额（点击「给你买杜蕾斯」），也可扫描小站放的支付宝领红包二维码，线下支付享受优惠的同时老四也可以获得对应赏金，老四这里抱拳谢谢诸位了。捐赠时请备注姓名或者昵称，因为您的署名会出现在赞赏列表页面，您的捐赠钱财也会被用于小站的服务器运维上面，再次抱拳感谢。
