插入排序(InsertionSort)，一般也被稱為直接插入排序。
對于少量元素的排序，它是一個有效的算法。插入排序是一種最簡單的排序方法，它的基本思想是将一個記錄插入到已經排好序的有序表中，進而一個新的、記錄數增 1 的有序表
。在其實作過程使用雙層循環，外層循環對除了第一個元素之外的所有元素，内層循環對目前元素前面有序表進行待插入位置查找，并進行移動。
插入排序的平均時間複雜度也是 O(n^2)，空間複雜度為常數階 O(1)，具體時間複雜度和數組的有序性也是有關聯的。
插入排序中，當待排序數組是有序時，是最優的情況，隻需目前數跟前一個數比較一下就可以了，這時一共需要比較 N-1 次，時間複雜度為 O(N)。最壞的情況是待排序數組是逆序的，此時需要比較次數最多，最壞的情況是 O(n^2)。
假設前面 n-1(其中 n>=2)個數已經是排好順序的，現将第 n 個數插到前面已經排好的序列中，然後找到合适自己的位置，使得插入第n個數的這個序列也是排好順序的。
按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序。
從小到大的插入排序整個過程如圖示：
第一輪：從第二位置的 6 開始比較，比前面 7 小，交換位置。
第二輪：第三位置的 9 比前一位置的 7 大，無需交換位置。
第三輪：第四位置的 3 比前一位置的 9 小交換位置，依次往前比較。
第四輪：第五位置的 1 比前一位置的 9 小，交換位置，再依次往前比較。
......
就這樣依次比較到最後一個元素。
源碼包下載下傳：Download
部分代碼：
package runoob;
/**
* 插入排序
*/
public class InsertionSort {
//核心代碼---開始
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// 尋找元素 arr[i] 合适的插入位置
for( int j = i ; j > 0 ; j -- )
if( arr[j].compareTo( arr[j-1] ) < 0 )
swap( arr, j , j-1 );
else
break;
}
}
//核心代碼---結束
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
InsertionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}