简介
插入排序算法顾名思义，既要插入数据，又不能打乱原来数组的顺序。所以插入排序算法在插入数据前需要计算插入的位置并预留空间，然后将想要插入的数据直接放入即可。插入排序，被插入数据的集合在插入前后总是有序的。
百度百科==>插入排序
本篇插入排序是基于冒泡排序算法的！
原理
- 在插入数据前保证被插入的数据已经排序完毕
- 在插入数据后（下次插入数据前）保证数据有序
- 循环执行以上过程，直到所有要插入的数据插入完毕
例子
上面的原理是我自己总结的，虽然感觉我已经提炼了出了精华，但还是显得有些苍白，所以上图上实例
先看图
这张图片的意思很明白，展示了序列（数组）[5,1,7,3,1,6,9,4]的升序排序过程。
图片中的每一行的总和表示了整个插入排序的过程。
咦？不是说插入？怎么从头到尾就是一个数据，而且看起来很像冒泡排序啊！
的确，整个过程就是一个数组里的元素排来排去。但是请仔细观察，在图片左上右下对角线附近的阶梯，在阶梯上半部的可以看作外部（待排序的）数据，在阶梯下半部的每一行都是按升序排序过的序列，而且越往下下半部数据元素越多，上半部数据元素越少。
因此可以看作每往下一行，都要将上半部的一个数据元素插入到下半部。所以称之为插入排序。
之所以看起来像冒泡排序是因为，插入的数据元素的顺序是按原序列的数据元素顺序来的，而插入的元素后又要保持数组有序，很多时候都要前面的元素挪出位置给新插入进来的元素（如果插入进来的元素值比较小，需要靠前排列），这个交换位置的过程和冒泡排序是很像的。
插入排序算法的Java实现
所以总结下来，对于一个给定的序列（不是有序的，有序就不要再排了）使用插入排序算法，其实可以看作是将原序列分为两部分，一部分是已排序好的，称为内部，一部分是待排序，称为外部。每次插入（从外部取一个元素放进内部）一个元素到下一次插入元素之间需要做的就是将内部元素排列为有序，至于内部排序用什么算法可以根据需求选择。
注：这里插入排序算法的Java实现是基于冒泡排序的
核心实现代码
//插入排序算法核心方法，isAscending--是否升序
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
//外部数据不断插入到内部
for (int i = 0; i < data.length - 1; i++) {
//插入进来的元素与相邻元素（插入元素的前一个元素）比较是否需要交换，需要就交换，不要则继续插入下一个元素
//（因为之前的内部元素已经有序，如果插入新元素没有与相邻（前一个）元素发生交换表示插入新元素内部仍然是有序的）
if (this.compare(data, i, i + 1, isAscending)) {
this.doSwap(data, i, i + 1, isAscending);
} else {
continue;
}
//对内部进行冒泡排序
for (int j = i; j > 0; j--) {
this.doSwap(data, j - 1, j, isAscending);
}
}
}
//比较两个相邻的元素是否需要交换位置
private boolean compare(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
return largeThan && isAscending || !largeThan && !isAscending;
}
//两个元素位置交换的方法
private void doSwap(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
if (largeThan && isAscending || !largeThan && !isAscending) {
super.swap(data, indexA, indexB);
}
}
全部代码（包导入信息自己设置）
AbstractSort.java
public abstract class AbstractSort {
private int[] data;
public AbstractSort(int[] data) {
this.data = data;
}
public abstract void sort(boolean isAscending);
public void sort() {
this.sort(true);
}
public int[] getData() {
return data;
}
public void print() {
for (int i : this.data) {
System.out.println(i);
}
}
protected void swap(int[] data, int indexA, int indexB) {
int temp = data[indexA];
data[indexA] = data[indexB];
data[indexB] = temp;
}
}
InsertionSort.java
public class InsertionSort extends AbstractSort {
public InsertionSort(int[] data) {
super(data);
}
@Override
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
for (int i = 0; i < data.length - 1; i++) {
if (this.compare(data, i, i + 1, isAscending)) {
this.doSwap(data, i, i + 1, isAscending);
} else {
continue;
}
for (int j = i; j > 0; j--) {
this.doSwap(data, j - 1, j, isAscending);
}
}
}
protected boolean compare(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
return largeThan && isAscending || !largeThan && !isAscending;
}
protected void doSwap(int[] data, int indexA, int indexB, boolean isAscending) {
int a = data[indexA];
int b = data[indexB];
boolean largeThan = a > b;
if (largeThan && isAscending || !largeThan && !isAscending) {
super.swap(data, indexA, indexB);
}
}
}
