基本思想
當插入第i（i≥1）個元素，前面的i-1個元素已經排好序。這時用第i個元素與前i-1個元素進行比較，找到插入位置即將第i個元素插入，原來位置上的元素向後順移。
代碼：
//待排數據存儲在數組a中，以及待排序列的左右邊界
public void InsertSort(int[] a, int left, int right) {
int temp;//臨時變量
int i, j;//循環標記
for (i = left + 1; i <= right; i++) {//遍歷待排序列
if (a[i] < a[i - 1]) {
temp = a[i];
j = i - 1;
//向後順移元素，直到找到適當位置插入元素
do {
a[j + 1] = a[j];
j--;
} while (j >= left && temp < a[j]);
a[j + 1] = temp;
}
}
}
性能分析
時間復雜度
考慮最壞的情況，即整個序列是逆序的。那麼對於每次外循環，最內循環的執行次數，也是基本操作的執行次數都達到最大值。也就是說，每次插入一個元素都需要順移所有已經排好序的元素。所以該算法的時間復雜度為O(n2)。
考慮最好的情況，即整個序列是有序的，那麼對於每次外循環，最內循環都不執行。也就是說，每次插入一個元素都不需要移動元素。顯然時間復雜度為O(n)。
綜上所述，直接插入排序算法的時間復雜度為O(n2)。
空間復雜度
直接插入排序算法所需的額外空間只有一個臨時變量temp，因此空間復雜度為O(1)。
穩定性
直接插入排序是一種穩定的排序算法。
