## **插入排序** 插入排序是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。 ## **算法描述** 1. 把待排序的數組分成已排序和未排序兩部分，初始的時候把第一個元素認為是已排好序的。 2. 從第二個元素開始，在已排好序的子數組中尋找到該元素合適的位置并插入該位置。 3. 重復上述過程直到最后一個元素被插入有序子數組中。 ## **穩定性** 由于只需要找到不大于當前數的位置而并不需要交換，因此，直接插入排序是穩定的排序方法。 ## **適用場景** 插入排序由于O( n2 )的復雜度，在數組較大的時候不適用。但是，在數據比較少的時候，是一個不錯的選擇，一般做為快速排序的擴充。例如，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的實現中，當待排數組長度小于47時，會使用插入排序。 ## **JAVA代碼實現** ``` public static void insertionSort(int[] arr){ for (int i=1; i<arr.length; ++i){ int value = arr[i]; int position=i; while (position>0 && arr[position-1]>value){ arr[position] = arr[position-1]; position--; } arr[position] = value; }//loop i } ```