今天我們來聊一聊插入排序。
插入排序（Insertion Sort）算法通過對未排序的資料執行逐個插入至合适的位置而完成排序工作。插入排序算法的思路比較簡單，應用比較多。
插入排序算法通過比較和插入來實作排序，其排序流程如下;
（1）首先對數組的前兩個資料進行從小到大的排序。
(2) 接着将第3個資料與排好序的兩個資料比較，将第3個資料插入合适的位置。
（3）然後，将第4個資料插入已排好序的前3個資料中。
（4）不斷重複上述過程，直到把最後一個資料插入合适的位置。最後，便完成了對原始數組從小大的排序。
為了更好地了解插入排序算法的執行過程，下面舉一個實際資料的例子來一步一步地執行插入排序算法。5 個整型資料 118、101、105、127、112是一組無序的資料。對其執行插入排序過程：
初始資料： 118 101 105 127 112
第一次排序：101 118 105 127 112
第二次排序：101 105 118 127 112
第三次排序：101 105 118 127 112
第四次排序：101 105 112 118 127
插入排序算法的執行步驟如下：
（1）第1次排序，首先對數組的前兩個資料118和101 排序，由于118大于101，是以将其交換。此時排序後的資料為 101、118、105、127、112。
（2）第2次排序，對于第3個資料105，其大于101，而小于118，将其插入它們之間。此時排序後的資料為 101、105、118、127、112。
（3）第3次排序，對于第4個資料127，其大于118，将其插入118之後。此時排序後的資料為101、105、118、127、112。
（4）第4次排序，對于第5個資料112，其大于105，小于118，将其插入105和118之間。此時排序後的資料為101、105、112、118、127。
從上面的例子可以非常直覺地了解到插入排序算法的執行過程。插入排序算法在對 n個資料進排序時，無論原資料有無順序，都需要進行」1步的中間排序。這種排序方法思路簡單直覺，在資料已有一定順序的情況下，排序效率較好。但如果資料無規則，則需要移動大量的資料，其排序率也不高。
下面就用代碼看一看插入排序的過程吧！
public static void insertSort(int[] a){//插入排序
for(int i=1;i<a.length;i++){//循環周遊數組
//定義要插入的數
int t=a[i];
int j=i-1;//a[i]前面數的下标
while (j>=0 && t<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=t;
System.out.print("第"+i+"步排序的結果：");
for(int h=0;h<a.length;h++){
System.out.print(" "+a[h]);
}
System.out.println();
}
}
大家是不是對這個算法的過程還是一頭霧水呀，别急，這就為大家詳解一番：
在上述代碼中，輸入參數a一般為一個數組的首位址，待排序的原資料便儲存在數組a中。
在程式中，首先将需要插入的元素儲存到變量t中。變量j表示需要插入的位置，一般就是插入數組元素的序号。設定變量j的值為i-1，表示準備将目前位置（序号為i）的數插入序号為i-1（即前一個元素的位置）
接着，算法程式通過while循環來進行判斷，如果序号為j元素的資料大于變量t（需要插入的資料)，則将序号為j的元素向後移，同時變量j減1，以判斷前一個資料是否還需要向後移。通過該 while 循環找到一個元素的值比t小，然後，将在序号為j的下一個元素進行資料插入操作。
好了，這就是執行過程啦，給大家看看運作結果吧。
結果截圖：
那這個算法的執行效率如何呢？
哇，80000個資料排序隻用了一秒哎，好快
========================================================
完整代碼為大家附上：
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* @Author DreamYee
* @Create 2019/10/22 07:00
*/
public class InsertSort {
static final int SIZE=5;
public static void main(String[] args) {
/*
int[] array = new int[SIZE];
for(int i=0;i<SIZE;i++){
array[i]=(int)(100+Math.random()*100+1);//初始化數組
}
System.out.println("排序前的數組：");
for(int i=0;i<array.length;i++){
System.out.print(" "+array[i]);
}
System.out.println();
insertSort(array);
System.out.println("排序後的數組：");
for(int i=0;i<array.length;i++){
System.out.print(" "+array[i]);
}
System.out.println();
*/
//測試效率
int[] array=new int[80000];
for(int i=0;i<80000;i++){
array[i]=(int)(Math.random()*8000000);//生成一個[0,8000000)數
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("排序前的時間：" + date1Str);
insertSort(array);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("排序後的時間：" + date2Str);
}
public static void insertSort(int[] a){//插入排序
for(int i=1;i<a.length;i++){//循環周遊數組
//定義要插入的數
int t=a[i];
int j=i-1;//a[i]前面數的下标
while (j>=0 && t<a[j]){
a[j+1]=a[j];
j--;
}
a[j+1]=t;
/*
System.out.print("第"+i+"步排序的結果：");
for(int h=0;h<a.length;h++){
System.out.print(" "+a[h]);
}
System.out.println();
*/
}
}
}
OK，以上就是插入算法的全部内容了。前三種算法你挑戰成功了嗎？
後續繼續更新中……^ _ ^
fighting！！！！