1. 插入排序思想
（1.1）插入排序是一種簡單直觀的排序方法，其基本思想在于每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中，直到全部記錄插入完成，由插入排序的思想可以引申出三個重要的排序演算法：直接插入排序、折半插入排序和希爾排序，
2. 直接插入排序思想及演示程序
https://www.bilibili.com/video/BV14r4y1F71a?p=65
3. 直接插入排序代碼實作
1 package cn.sun.it.review; 2 3 import java.util.Arrays; 4 import java.util.Scanner; 5 6 public class InsertSort { 7 8 public static void main(String[] args) { 9 // 測驗資料：49,38,65,97,76,13,27,49 10 System.out.println("請輸入若干個整數，以逗號分隔："); 11 Scanner sc = new Scanner(System.in); 12 String strNums = sc.nextLine(); 13 String[] tempArrNums = strNums.split(","); 14 int[] arr = new int[tempArrNums.length]; 15 for (int i = 0; i < arr.length; i++) { 16 arr[i] = Integer.valueOf(tempArrNums[i]); 17 } 18 System.out.println("排序前：" + Arrays.toString(arr)); 19 insertSort(arr); 20 System.out.println("排序后：" + Arrays.toString(arr)); 21 } 22 23 private static void insertSort(int[] arr) { 24 int temp; 25 int j; 26 for(int i=1;i<arr.length;i++){ 27 temp = arr[i]; // 把當前待排序元素用一個臨時變數temp記錄 28 j = i-1; 29 while(j>=0 && temp < arr[j]){ 30 arr[j+1] = arr[j]; // 向后移動一個位置 31 j--; 32 } 33 arr[j+1] = temp; // 把當前待排序元素插入到最終位置 34 } 35 } 36 37 }
4. 測驗及輸出結果
5. 直接插入排序性能分析
（5.1）空間復雜度：僅使用常數個輔助單元，空間復雜度為O(1);
（5.2）時間復雜度：
- 在最好的情況下，表中元素已經有序，此時每插入一個元素，都只需比較一次而不用移動元素，因而時間復雜度為O(n)；
- 在最壞的情況下，表中元素順序剛好與排序結果中元素順序相反(逆序)時，總的比較次數達到最大n(n-1)/2次，總的移動次數也達到最大，為n(n-1)/2次，
- 平均情況下，考慮待排序表中元素是隨機的，此時可以取上述最好與最壞情況的平均值作為平均情況下的時間復雜度，總的比較次數與總的移動次數均為n2/4，因此，直接插入排序演算法的時間復雜度為O(n2)，雖然折半插入排序演算法的時間復雜度也有O(n2)，但對于資料量比較小的排序表，折半插入排序往往能表現出很好的性能，
（5.3）穩定性：由于每次插入元素時總是從后向前先比較再移動，所以不會出現相同元素相對位置發生變化的情況，即直接插入排序是一個穩定的排序方法，
（5.4）適用性：直接插入排序演算法適用于順序存盤和鏈式存盤的線性表，當為鏈式存盤時，可以從前往后查找指定元素的位置，注意：大部分排序演算法都僅適用于順序存盤的線性表，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/270652.html
標籤：其他