簡介
插入排序算法顧名思義砸王，既要插入數(shù)據(jù)急膀，又不能打亂原來數(shù)組的順序。所以插入排序算法在插入數(shù)據(jù)前需要計算插入的位置并預(yù)留空間辆飘，然后將想要插入的數(shù)據(jù)直接放入即可。插入排序谓传，被插入數(shù)據(jù)的集合在插入前后總是有序的蜈项。
百度百科==>插入排序
本篇插入排序是基于冒泡排序算法的！
原理
- 在插入數(shù)據(jù)前保證被插入的數(shù)據(jù)已經(jīng)排序完畢
- 在插入數(shù)據(jù)后（下次插入數(shù)據(jù)前）保證數(shù)據(jù)有序
- 循環(huán)執(zhí)行以上過程续挟，直到所有要插入的數(shù)據(jù)插入完畢
例子
上面的原理是我自己總結(jié)的紧卒，雖然感覺我已經(jīng)提煉了出了精華，但還是顯得有些蒼白诗祸，所以上圖上實例
先看圖
這張圖片的意思很明白跑芳，展示了序列（數(shù)組）[5,1,7,3,1,6,9,4]的升序排序過程。
圖片中的每一行的總和表示了整個插入排序的過程直颅。
咦博个？不是說插入？怎么從頭到尾就是一個數(shù)據(jù)功偿，而且看起來很像冒泡排序芭栌丁！
的確械荷，整個過程就是一個數(shù)組里的元素排來排去共耍。但是請仔細(xì)觀察，在圖片左上右下對角線附近的階梯吨瞎，在階梯上半部的可以看作外部（待排序的）數(shù)據(jù)痹兜，在階梯下半部的每一行都是按升序排序過的序列，而且越往下下半部數(shù)據(jù)元素越多颤诀，上半部數(shù)據(jù)元素越少字旭。
因此可以看作每往下一行，都要將上半部的一個數(shù)據(jù)元素插入到下半部着绊。所以稱之為插入排序谐算。
之所以看起來像冒泡排序是因為，插入的數(shù)據(jù)元素的順序是按原序列的數(shù)據(jù)元素順序來的归露，而插入的元素后又要保持?jǐn)?shù)組有序洲脂，很多時候都要前面的元素挪出位置給新插入進(jìn)來的元素（如果插入進(jìn)來的元素值比較小，需要靠前排列），這個交換位置的過程和冒泡排序是很像的恐锦。
插入排序算法的Java實現(xiàn)
所以總結(jié)下來往果，對于一個給定的序列（不是有序的，有序就不要再排了）使用插入排序算法一铅，其實可以看作是將原序列分為兩部分陕贮，一部分是已排序好的，稱為內(nèi)部潘飘，一部分是待排序肮之，稱為外部。每次插入（從外部取一個元素放進(jìn)內(nèi)部）一個元素到下一次插入元素之間需要做的就是將內(nèi)部元素排列為有序卜录，至于內(nèi)部排序用什么算法可以根據(jù)需求選擇戈擒。
注：這里插入排序算法的Java實現(xiàn)是基于冒泡排序的
核心實現(xiàn)代碼
//插入排序算法核心方法，isAscending--是否升序
public void sort(boolean isAscending) {
int[] data = super.getData();
if (data == null || data.length < 2) {
return;
}
//外部數(shù)據(jù)不斷插入到內(nèi)部
for (int i = 0; i < data.length - 1; i++) {
//插入進(jìn)來的元素與相鄰元素（插入元素的前一個元素）比較是否需要交換艰毒，需要就交換筐高，不要則繼續(xù)插入下一個元素
//（因為之前的內(nèi)部元素已經(jīng)有序，如果插入新元素沒有與相鄰（前一個）元素發(fā)生交換表示插入新元素內(nèi)部仍然是有序的）
if (this.compare(data, i, i + 1, isAscending)) {
this.doSwap(data, i, i + 1, isAscending);
} else {
continue;
}
//對內(nèi)部進(jìn)行冒泡排序
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);
}
}
全部代碼（包導(dǎo)入信息自己設(shè)置）
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);
}
}
}
