演算法定義
直接插入排序是插入排序的一種，是一種簡單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表，
演算法原理
直接插入排序演算法流程如下：
1、將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列，
2、從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位置，
代碼實作
按照上面的思路，可以通過交換法實作，
從第2個數開始，確定要操作的數，對要操作的數找到要插入的位置，
然后一路往前對比，若當前數字比前一個數字小，那么交換兩個數字，通過不斷的交換找到這個數合適的位置插入，
交換法的代碼如下：
public class Main {
// 直接插入排序(插入排序)，交換法，平均時間復雜度O(n^2)，最好時間復雜度O(n)，最壞時間復雜度O(n^2)，空間復雜度O(1)
public static void directlyInsertSort(int[] arr) {
// 從第2個數開始，確定要操作的數，對要操作的數找到要插入的位置
for (int i = 1; i < arr.length; ++i) {
// 獲取當前數字的下標
int j = i;
// 一路往前對比，若當前數字比前一個數字小，那么交換兩個數字，通過不斷的交換找到這個數合適的位置插入
while (j >= 1 && arr[j] < arr[j - 1]) {
// 交換兩個數字
arr[j - 1] ^= arr[j];
arr[j] ^= arr[j - 1];
arr[j - 1] ^= arr[j];
// 下標往前移動
--j;
}
}
}
}
但是我們發現，在交換法中，每次交換數字時，下一次比較可能又要被交換下去了，
所以，我們想到一個優化，使用移動法：先讓新插入的數字和前面的數字進行比較，比新插入的數字大的數字不斷向后移動，直到找到適合這個新插入的數字的位置后，新插入的數字再做一次交換，來完成插入，
移動法的代碼如下：
public class Main {
// 直接插入排序(插入排序)，移動法，平均時間復雜度O(n^2)，最好時間復雜度O(n)，最壞時間復雜度O(n^2)，空間復雜度O(1)
public static void directlyInsertSort(int[] arr) {
// 從第2個數開始，確定要操作的數，對要操作的數找到要插入的位置
for (int i = 1; i < arr.length; ++i) {
// 先把當前要插入的數字保存起來
int temp = arr[i];
// 獲取當前要插入的數字的前一個下標
int j = i - 1;
// 一路往前，和當前要插入的數字比較，若大于當前要插入的數字，那么后移，直到不大于當前要插入的數字或者到了第一個下標，結束回圈
while (j >= 0 && arr[j] > temp) {
// 后移數字
arr[j + 1] = arr[j];
// 下標往前移動
--j;
}
// 找到插入的位置，把當前要插入的數字賦值到這里
arr[j + 1] = temp;
}
}
}
交換法和移動法其實差不多，移動法沒有實質的效率改善，只是減少了一些沒有必要的交換操作，并沒有降低時間復雜度和空間復雜度，
演算法效率
直接插入排序是穩定的排序演算法，
最好時間復雜度是O(n)，剛好陣列是順序的，兩層回圈只走了第一層，第一層for回圈是n數量級的時間，第二層while回圈，陣列已經有序，不會進入，
最壞時間復雜度是O(n^2)，剛好陣列是倒敘的，兩層回圈都走了，第一層for回圈是n數量級的時間，第二層while回圈也是n數量級的時間，每次都要交換n-k次，k是常數，去到常數項k，還是n的數量級，所以是n * n=n ^ 2，
平均時間復雜度是O(n^2)，第一層for回圈無論如何都要走的，第二層的while回圈，平均下來也是n的數量級，因為假設陣列有n個數，不同順序的陣列，第二層的while回圈還是和前面的表示一樣，交換n-k次，k是常數，去到常數項k，還是n的數量級，所以還是n * n=n ^ 2，
空間復雜度為O(1)，因為只使用有限個數的變數，
演算法是穩定的，因為直接插入排序實質是通過交換來實作插入的，而這里的交換判斷沒有等于的判斷，如果陣列里的兩個數是相等的，那么不會交換，那么就不存在陣列里相等的兩個數的交換，
平均時間復雜度：O(n^2)
最好時間復雜度：O(n)
最壞時間復雜度：O(n^2)
空間復雜度：O(1)
參考資料
直接插入排序動圖來自：直接插入排序
原文鏈接
原文鏈接：演算法總結-直接插入排序
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296770.html
標籤：其他
上一篇：資料結構與演算法總結