一、简介
插入排序（Insertion Sort）算法是一个对少量元素进行排序的有效算法。
插入排序是稳定的（即：两个相等的数不会交换位置）。
二、分类
直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。
（注：此文只讲直接插入排序，其他插入排序有时间会另写博客。）
三、原理（直接插入排序思想）
每次从无序表中取出最后一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
详解：
从数组的第二个元素开始,将数组中的每一个元素按照（升序或者降序）规则插入到已排好序的数组中以达到排序的目的.
一般情况下将数组的第一个元素作为起始元素,从第二个元素开始依次插入。由于要插入到的数组是已经排好序的,所以只要从右向左（或者从后向前）找到排序插入点插入元素，以此类推，直到将最后一个数组元素插入到数组中,整个排序过程完成。
四、原理过程图（升序排列为例）
每次将数组最后一个元素作为插入元素，与它前面有序（已排好序）的数组元素进行比较后，插入正确的位置，排序完成。（如下图）
插入排序原理图.png
五、时间复杂度
将有n个元素的数组排序。
最佳情况就是，数组已经是正序排列了，在这种情况下，需要进行的比较操作是 （n-1）次即可。
最坏情况就是，数组是反序排列，那么此时需要进行的比较共有n(n-1)/2次。
插入排序的赋值操作是比较操作的次数加上 (n-1）次。
平均插入排序算法的时间复杂度为 O(n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小（eg：量级小于千），那么插入排序是一个不错的选择
Note：尽管插入排序的时间复杂度也是O(n²)，但一般情况下，插入排序会比冒泡排序快一倍，要比选择排序还要快一点。
六、性能分析(稳定性)
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
七、示例代码（ Java）
1.核心代码
/** * 插入排序: * 原理：每次将数组最后一个元素作为插入元素，与它前面有序（已排好序）的数组元素进行比较后，插入正确的位置，排序完成。 * 升序为例 */ private static int[] insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) {// i: 代表即将插入的元素角标,作为每一组比较数据的最后一个元素 for (int j = i; j > 0; j--) { //j:代表数组角标 if (arr[j] < arr[j - 1]) {//符合条件，插入元素（交换位置） int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } return arr; }
2.直接插入排序完整代码示例
import java.util.*; public class ArrayTest { public static void main(String[] args) { int[] arr={90,10,11,45,34,88}; //排序前； System.out.println("原数组："); printArray(arr); //排序 insertionSort(arr); System.out.println("升序排序后："); //排序后： printArray(arr); } /** * 插入排序: 升序为例 * 原理：每次将最后一个元素作为插入元素， 与有序数列比较后 插入正确位置 * */ private static int[] insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { //i<6 1,2,3,4,5 for (int j = i; j > 0; j--) { //j=i 代表数组角标 if (arr[j] < arr[j - 1]) {//符合条件，插入元素（交换位置） swap(arr,j,j-1); } } } return arr; } /* 发现无论什么排序。都需要对满足条件的元素进行位置置换。 所以可以把这部分相同的代码提取出来，单独封装成一个函数。 */ public static void swap(int[] arr,int a,int b) { int temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } public static void printArray(int[] arr) { System.out.print("["); for(int x=0; x<arr.length; x++) { if(x!=arr.length-1) System.out.print(arr[x]+", "); else System.out.println(arr[x]+"]"); } } }
运行结果：
