插入排序（Insertion Sort）算法通過對未排序的數(shù)據(jù)執(zhí)行逐個插入至合適的位置而完成排序工作。插入排序算法的思路比較簡單，應用比較多。
插入排序算法
插入排序算法通過比較和插入來實現(xiàn)排序，其排序流程如下：
⑴首先對數(shù)組的前兩個數(shù)據(jù)進行從小到大的排序。
⑵接著將第3個數(shù)據(jù)與排好序的兩個數(shù)據(jù)比較，將第3個數(shù)據(jù)插入合適的位置。
⑶然后，將第4個數(shù)據(jù)插入已排好序的前3個數(shù)據(jù)中。
⑷不斷重復上述過程，直到把最后一個數(shù)據(jù)插入合適的位置。最后，便完成了對原始數(shù)組從小到大的排序。
為了更好地理解插入排序算法的執(zhí)行過程，下面舉一個實際數(shù)據(jù)的例子來一步一步地執(zhí)行插入排序算法。5個整型數(shù)據(jù)118、101、105、127、112是一組無須的數(shù)據(jù)。對其執(zhí)行插入排序過程，如圖1所示。
插入排序算法的執(zhí)行步驟如下：
⑴第1次排序，首先對數(shù)組的前兩個數(shù)據(jù)118和101排序，由于118大于101，因此將其交換。此時的排序后的數(shù)據(jù)為101、118、105、127、112。
⑵第2次排序，對于第3個數(shù)據(jù)105，其大于101，而小于118，將其插入它們之間。此時排序后的數(shù)據(jù)為101、105、118、127、112。
⑶第3次排序，對于第4個數(shù)據(jù)127，其大于118，將其插入118之后。此時排序后的數(shù)據(jù)為101、105、118、127、112。
⑷第4次排序，對于第5個數(shù)據(jù)112，其大于105，小于118，將其插入105和118之間。此時排序后的數(shù)據(jù)為101、105、112、118、127。
從上面的例子可以非常直觀地了解到插入排序算法的執(zhí)行過程。插入排序算法在對n個數(shù)據(jù)進行排序時，無論原數(shù)據(jù)有無順序，都需要進行n-1步的中間排序。這種排序方法思路簡單直觀，在數(shù)據(jù)已有一定順序的情況下，排序效率較好。但如果數(shù)據(jù)無規(guī)則，則需要移動大量的數(shù)據(jù)，其排序效率也不高。
插入排序算法的示例代碼如下：
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");
}
}
在上述代碼中，輸入?yún)?shù)a一般為一個數(shù)組的首地址，待排序的原數(shù)據(jù)便保存在數(shù)組a中。
在程序中，首先將需要插入的元素保存到變量t中。變量j表示需要插入的位置，一般就是插入數(shù)組元素的序號。設置變量j的值為i-1，表示準備將當前位置（序號為i）的數(shù)插入序號為i-1（即前一個元素）的 位置。
接著，算法程序通過while循環(huán)來進行判斷，如果序號為j元素的數(shù)據(jù)大于變量t（需要插入的數(shù)據(jù)），則將序號為j的元素向后移，同時變量j減1，以判斷前一個數(shù)據(jù)是否還需要向后移。通過該while循環(huán)來找到一個元素的值比t小，該元素的序號為j。然后，將序號為j的下一個元素進行數(shù)據(jù)插入操作。
插入排序算法實例
學習了前面的插入排序算法的基本思想和算法之后，下面通過一個完整的例子來說明插入排序法在整型數(shù)組排序中的應用，程序示例如下：
【程序】
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("排序前的數(shù)組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
insertionSort(shuzu);
System.out.print("排序后的數(shù)組為: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
}
}
在上述代碼中，程序定義了符號常量SIZE，用于表征需要排序整型數(shù)組的大小。在主函數(shù)中，首先初始化隨機種子，然后對數(shù)組進行隨機初始化，并輸出排序前的數(shù)組內(nèi)容。接著，調(diào)用插入排序算法函數(shù)來對數(shù)組進行排序。最后，輸出排序后的數(shù)組。
該程序的執(zhí)行結果，如圖2所示。圖中顯示了每一步排序的中間結果。
