插入排序（Insertion Sort）算法通過對未排序的數據執(zhí)行逐個插入至合適的位置而完成排序工作舀武。插入排序算法的思路比較簡單，應用比較多捻撑。
插入排序算法
插入排序算法通過比較和插入來實現排序乎折，其排序流程如下：
⑴首先對數組的前兩個數據進行從小到大的排序蒸其。
⑵接著將第3個數據與排好序的兩個數據比較，將第3個數據插入合適的位置碍彭。
⑶然后晤硕，將第4個數據插入已排好序的前3個數據中。
⑷不斷重復上述過程庇忌，直到把最后一個數據插入合適的位置舞箍。最后，便完成了對原始數組從小到大的排序皆疹。
為了更好地理解插入排序算法的執(zhí)行過程疏橄，下面舉一個實際數據的例子來一步一步地執(zhí)行插入排序算法。5個整型數據118略就、101捎迫、105、127表牢、112是一組無須的數據窄绒。對其執(zhí)行插入排序過程，如圖1所示崔兴。
插入排序算法的執(zhí)行步驟如下：
⑴第1次排序彰导，首先對數組的前兩個數據118和101排序蛔翅，由于118大于101，因此將其交換位谋。此時的排序后的數據為101山析、118、105倔幼、127盖腿、112。
⑵第2次排序损同，對于第3個數據105翩腐，其大于101，而小于118膏燃，將其插入它們之間茂卦。此時排序后的數據為101、105组哩、118等龙、127、112伶贰。
⑶第3次排序蛛砰，對于第4個數據127，其大于118黍衙，將其插入118之后泥畅。此時排序后的數據為101、105琅翻、118位仁、127、112方椎。
⑷第4次排序聂抢，對于第5個數據112，其大于105棠众，小于118琳疏，將其插入105和118之間。此時排序后的數據為101闸拿、105轿亮、112、118胸墙、127我注。
從上面的例子可以非常直觀地了解到插入排序算法的執(zhí)行過程。插入排序算法在對n個數據進行排序時迟隅，無論原數據有無順序但骨，都需要進行n-1步的中間排序励七。這種排序方法思路簡單直觀，在數據已有一定順序的情況下奔缠，排序效率較好掠抬。但如果數據無規(guī)則，則需要移動大量的數據校哎，其排序效率也不高两波。
插入排序算法的示例代碼如下：
void insertionSort(int[] a) {
int i, j, t, h;
for (i = 1; i < a.length; i++) {
t = a[i];
j = i - 1;
while (j >= 0 && t < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
System.out.print("第" + i + "步排序結果:");
for (h = 0; h < a.length; h++) {
System.out.print(" " + a[h]);
}
System.out.print("\n");
}
}
在上述代碼中，輸入參數a一般為一個數組的首地址闷哆，待排序的原數據便保存在數組a中腰奋。
在程序中，首先將需要插入的元素保存到變量t中抱怔。變量j表示需要插入的位置劣坊，一般就是插入數組元素的序號。設置變量j的值為i-1屈留，表示準備將當前位置（序號為i）的數插入序號為i-1（即前一個元素）的 位置局冰。
接著，算法程序通過while循環(huán)來進行判斷灌危，如果序號為j元素的數據大于變量t（需要插入的數據）康二，則將序號為j的元素向后移，同時變量j減1勇蝙，以判斷前一個數據是否還需要向后移沫勿。通過該while循環(huán)來找到一個元素的值比t小，該元素的序號為j浅蚪。然后，將序號為j的下一個元素進行數據插入操作烫罩。
插入排序算法實例
學習了前面的插入排序算法的基本思想和算法之后惜傲，下面通過一個完整的例子來說明插入排序法在整型數組排序中的應用，程序示例如下：
【程序】
public class Insertion_Sort {
static final int SIZE = 10;
static void insertionSort(int[] a) {
int i, j, t, h;
for (i = 1; i < a.length; i++) {
t = a[i];
j = i - 1;
while (j >= 0 && t < a[j]) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = t;
System.out.print("第" + i + "步排序結果:");
for (h = 0; h < a.length; h++) {
System.out.print(" " + a[h]);
}
System.out.print("\n");
}
}
public static void main(String[] args) {
int[] shuzu = new int[SIZE];
int i;
for (i = 0; i < SIZE; i++) {
shuzu[i] = (int) (100 + Math.random() * (100 + 1));
}
System.out.print("排序前的數組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
insertionSort(shuzu);
System.out.print("排序后的數組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
}
}
在上述代碼中贝攒，程序定義了符號常量SIZE盗誊，用于表征需要排序整型數組的大小。在主函數中隘弊，首先初始化隨機種子哈踱，然后對數組進行隨機初始化，并輸出排序前的數組內容梨熙。接著开镣，調用插入排序算法函數來對數組進行排序。最后咽扇，輸出排序后的數組邪财。
該程序的執(zhí)行結果陕壹，如圖2所示。圖中顯示了每一步排序的中間結果树埠。
