文 | 莫若吻
一、简介
插入排序（Insertion Sort）算法是一个对少量元素进行排序的有效算法。
插入排序是稳定的（即：两个相等的数不会交换位置）。
二、分类
直接插入排序，二分插入排序（又称折半插入排序），链表插入排序，希尔排序（又称缩小增量排序）。
（注：此文只讲直接插入排序，其他插入排序有时间会另写博客。）
三、原理（直接插入排序思想）
每次从无序表中取出最后一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
详解：
从数组的第二个元素开始,将数组中的每一个元素按照（升序或者降序）规则插入到已排好序的数组中以达到排序的目的.
一般情况下将数组的第一个元素作为起始元素,从第二个元素开始依次插入。由于要插入到的数组是已经排好序的,所以只要从右向左（或者从后向前）找到排序插入点插入元素，以此类推，直到将最后一个数组元素插入到数组中,整个排序过程完成。
四、原理过程图（升序排列为例）
每次将数组最后一个元素作为插入元素，与它前面有序（已排好序）的数组元素进行比较后，插入正确的位置，排序完成。（如下图）
五、时间复杂度
将有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]+"]");
}
}
}
运行结果：
版权声明：本文为博主原创文章，转载请必须注明出处，谢谢！
