🌟個人博客：www.hellocode.top
🏰Java知識導航：Java-Navigate
🔥CSDN：HelloCode.
🌞知乎：HelloCode
🌴掘金：HelloCode
?如有問題，歡迎指正，一起學習~~

---

插入排序（Insertion Sort）是一種簡單直觀的排序算法，其基本思想是將一個記錄插入到已排好序的有序序列中，直到所有記錄插入完成為止。

基本思想

如上圖所示，插入排序的基本思想就是將一個數組劃分為兩部分：有序部分和無序部分。通過將無序部分的元素依次插入有序部分（需要找到對應的正確位置），讓每次插入的每個元素都能在正確的位置，保證有序部分始終有序，在將無序部分的元素全部插入到有序部分后，整個集合也就為有序的了。

1. 從第二個元素開始，依次將當前元素插入到已排好序的有序序列中，直到最后一個元素。
2. 插入當前元素時，從后往前遍歷已排好序的有序序列，找到當前元素在有序序列中的位置，并將其插入到該位置。
3. 重復執行步驟2，直到所有元素都插入完畢。

舉個例子，比如我們有一組數字 [5, 3, 8, 4, 2]，我們可以首先把第一個數字5視為已排序序列，然后從第二個數字3開始，與已排序序列中的元素逐一比較，找到合適的位置插入。然后針對第三個數字8，我們再重復這個過程，直至所有的數字都插入到已排序序列中。

代碼實現

具體的代碼就是兩層for循環，外層控制未排序部分的指針，內層不斷循環尋找新插入元素的正確位置，代碼如下：

/*** @author HelloCode* @blog https://www.hellocode.top* @date 2023年08月09日 21:45*/
public class InsertSort {public static void main(String[] args) {int[] arr = {21, 64, 32, 11, 9, 5, 3, 41, 75, 32, 12, 98, 66};System.out.println("排序前：" + Arrays.toString(arr));insertSort(arr);System.out.println("排序后：" + Arrays.toString(arr));}public static void insertSort(int[] arr) {// 外層循環，i指向數組中未排序的元素，也可以表示已經有序元素的個數for (int i = 1; i < arr.length; i++) {// 內層for指向已經排好序的最后一個元素for (int j = i - 1; j >= 0; j--) {// 開始排序，尋找新加入的元素的正確位置，（j + 1）代表新加入的元素if (arr[j + 1] >= arr[j]) {// 代表不用交換，加入即有序，直接跳出循環break;}// 否則需要進行交換，直到找到合適位置int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}
}

測試：

優化

對于插入排序，能夠優化的點我認為是在為新插入元素尋找正確位置的時候，上面的代碼采用的是依次比較，類似于冒泡排序的思想。如果數據量大且情況最差的時候，效率就有些不理想了，因此可以用其他方法在此處進行優化，提升插入排序的性能

二分查找：在每次需要插入元素時，使用二分查找來找到插入的位置，而不是從頭到尾掃描已排序序列。這樣可以將比較次數降低為O(log n)。

具體代碼這里就不列了，后面可能會有專門的二分查找文章。

總結

優點

1. 實現簡單，對于部分有序的數組效率高。
2. 對于小規模數據或者部分有序的數據，插入排序的運行時間相對較短。

缺點

1. 對于大規模數據或者隨機數據，插入排序的時間復雜度較高，為O(n^2)。
2. 是非穩定的排序算法，即相等的元素可能會因為排序而變得順序顛倒。

復雜度

• 時間復雜度：O(n^2)
• 空間復雜度：O(1)

使用場景

1. 小型數據集：對于小型的數據集，插入排序是一種高效且簡單的排序算法
2. 部分排序的數據集：如果一個數據集大部分是排序的，那么插入排序將是一個很好的選擇。例如，考慮一個場景，一個團隊在一場比賽中獲得了一組分數，這些分數按照高低已經被排序，但是有一個新的分數需要插入到合適的位置。在這種情況下，插入排序可以快速找到新分數的位置并把它插入到正確的位置。
3. 外部排序：當處理非常大的數據集時，可能需要使用外部排序。外部排序是指那些不能一次性加載到內存中的數據的排序。在這種情況下，可以使用插入排序作為子程序，從外部存儲器中讀取元素并將它們插入到已經排序的部分中。
4. 與其他算法結合：插入排序也可以與其他算法結合使用。例如，當需要先對數據進行排序，然后再進行一些復雜的操作時，可以使用插入排序作為預處理步驟。