### Insertion Sort --- 實作簡單易理解。 將序列分為未排序與部分排序兩個區域。 未排序部分的值被拾取並放置在已排序部分的正確位置。 --- insertion sort 基本特性如下： 實作簡單易理解。 資料量少時較高效，且比其他 O(n^2) 的排序法高效（selection sort/bubble sort）。 自適應排序：可根據當前資料排序情形加速排序，資料越接近排序完成，效率越高。 穩定排序：相同鍵值的元素，排序後相對位置不改變。 原地排序：不需額外花費儲存空間來排序。 即時演算法：可處理逐步輸入的資料，不需等資料完全備妥。 --- Illustrations:  --- 將序列分為"未排序"與"部分排序"兩個區域。 1.取第一個元素，將該元素視為已排序。 2.取出下一元素，該元素將插入序列的部分排序區域。 3.尋找正確位置：若部分排序元素比新元素大，則互換位置。並重複步驟 2 - 3，直到部分排序元素小於等於新元素。 4.插入元素：將新元素插入最後的位置。 5.重複步驟 2 - 4，直到排序完成。 --- 簡而言之，即是每次取一個元素，尋找並插入該元素在部分排序區域的排序位置，再逐步把序列單邊排序完成。 --- 未排序部分的值被拾取並放置在已排序部分的正確位置。   --- 簡單來說定義的三行碼:  或五行碼:  --- pseudo code ```java= i ← 1 while i < length(A) j ← i while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j ← j - 1 end while i ← i + 1 end while ``` --- code ```java= // Java program for implementation of Insertion Sort class InsertionSort { /*Function to sort array using insertion sort*/ void sort(int arr[]) { int n = arr.length; for (int i = 1; i < n; ++i) { int key = arr[i]; int j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } /* A utility function to print array of size n*/ static void printArray(int arr[]) { int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr[i] + " "); System.out.println(); } // Driver method public static void main(String args[]) { int arr[] = { 12, 11, 13, 5, 6 }; InsertionSort ob = new InsertionSort(); ob.sort(arr); printArray(arr); } } /* This code is contributed by Rajat Mishra. */ ``` --- Binary Insertion Sort? --- 使用二分查找來減少正常插入排序中的比較次數。 Binary Insertion Sort使用 binary search來找到在每次迭代中插入所選項目的正確位置 在正常插入中，排序在最壞的情況下需要 O(n)（在第 n 次迭代中）。我們可以通過使用二進制搜索將其減少到 O(logn)。 該算法作為一個整體，仍然具有 O(n^2) 的運行最壞情況運行時間，因為每次插入都需要一系列交換。 --- 如何實現Linked List的Insertion Sort？ --- 以下步驟是LinkedList的簡單插入排序算法: 創建一個空的排序（或結果）列表 遍歷給定的列表，對每個節點執行以下操作。 在排序或結果列表中以排序方式插入當前節點。 將給定LinkedList的頭更改為排序（或結果）列表的頭。 --- best case： 若要處理序列是1、2、...、N， 那麼只要比較N次即可完成排序， 此即為時間複雜度 O(N)。 依此推論，當問題已經「接近完成排序」的狀態時，使用Insertion Sort會非常有效率。 --- worst case： 若要處理的序列恰好是顛倒順序，N、N−1、...、2、1，那麼位於index(i)的元素，需要比較「i−1次」，完成演算法總共要比較N*(N−1)/2次，時間複雜度為O(N^2)。 --- average case： 時間複雜度 O(N^2)。 --- 當問題的資料量較小時(欲排序的元素之數目較小)，使用Insertion Sort會很有效率，這是因為和Quick Sort、Merge Sort、Heap Sort相比，Insertion Sort不具有「遞迴」形式，因此不需要系統的stack， --- 題目: https://leetcode.com/problems/insertion-sort-list/ ```java= class Solution { public ListNode insertionSortList(ListNode head) { if( head == null ){ return head; } //創建一個空的排序（或結果）列表 ListNode helper = new ListNode(0); ListNode cur = head; ListNode pre = helper; ListNode next = null; //遍歷給定的列表，對每個節點執行以下操作。 while( cur != null ){ next = cur.next; //在排序或結果列表中以排序方式插入當前節點。 while( pre.next != null && pre.next.val < cur.val ){ pre = pre.next; } //將給定LinkedList的頭更改為排序（或結果）列表的頭 cur.next = pre.next; pre.next = cur; pre = helper; cur = next; } return helper.next; } } ``` --- ref: https://en.wikipedia.org/wiki/Insertion_sort https://www.geeksforgeeks.org/insertion-sort/