??個人博客：www.hellocode.top
??Java知識導(dǎo)航：Java-Navigate
??CSDN：HelloCode.
??知乎：HelloCode
??掘金：HelloCode
?如有問題，歡迎指正，一起學(xué)習(xí)~~
插入排序（Insertion Sort）是一種簡單直觀的排序算法，其基本思想是將一個記錄插入到已排好序的有序序列中，直到所有記錄插入完成為止。
基本思想
如上圖所示，插入排序的基本思想就是將一個數(shù)組劃分為兩部分：有序部分和無序部分。通過將無序部分的元素依次插入有序部分（需要找到對應(yīng)的正確位置），讓每次插入的每個元素都能在正確的位置，保證有序部分始終有序，在將無序部分的元素全部插入到有序部分后，整個集合也就為有序的了。
- 從第二個元素開始，依次將當(dāng)前元素插入到已排好序的有序序列中，直到最后一個元素。
- 插入當(dāng)前元素時，從后往前遍歷已排好序的有序序列，找到當(dāng)前元素在有序序列中的位置，并將其插入到該位置。
- 重復(fù)執(zhí)行步驟2，直到所有元素都插入完畢。
舉個例子，比如我們有一組數(shù)字 [5, 3, 8, 4, 2]，我們可以首先把第一個數(shù)字5視為已排序序列，然后從第二個數(shù)字3開始，與已排序序列中的元素逐一比較，找到合適的位置插入。然后針對第三個數(shù)字8，我們再重復(fù)這個過程，直至所有的數(shù)字都插入到已排序序列中。
代碼實現(xiàn)
具體的代碼就是兩層for循環(huán)，外層控制未排序部分的指針，內(nèi)層不斷循環(huán)尋找新插入元素的正確位置，代碼如下：
/**
* @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) {
// 外層循環(huán)，i指向數(shù)組中未排序的元素，也可以表示已經(jīng)有序元素的個數(shù)
for (int i = 1; i < arr.length; i++) {
// 內(nèi)層for指向已經(jīng)排好序的最后一個元素
for (int j = i - 1; j >= 0; j--) {
// 開始排序，尋找新加入的元素的正確位置，（j + 1）代表新加入的元素
if (arr[j + 1] >= arr[j]) {
// 代表不用交換，加入即有序，直接跳出循環(huán)
break;
}
// 否則需要進(jìn)行交換，直到找到合適位置
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
測試：
優(yōu)化
對于插入排序，能夠優(yōu)化的點我認(rèn)為是在為新插入元素尋找正確位置的時候，上面的代碼采用的是依次比較，類似于冒泡排序的思想。如果數(shù)據(jù)量大且情況最差的時候，效率就有些不理想了，因此可以用其他方法在此處進(jìn)行優(yōu)化，提升插入排序的性能
二分查找：在每次需要插入元素時，使用二分查找來找到插入的位置，而不是從頭到尾掃描已排序序列。這樣可以將比較次數(shù)降低為O(log n)。文章來源：http://www.zghlxwxcb.cn/news/detail-636391.html
具體代碼這里就不列了，后面可能會有專門的二分查找文章。文章來源地址http://www.zghlxwxcb.cn/news/detail-636391.html
總結(jié)
優(yōu)點
- 實現(xiàn)簡單，對于部分有序的數(shù)組效率高。
- 對于小規(guī)模數(shù)據(jù)或者部分有序的數(shù)據(jù)，插入排序的運行時間相對較短。
缺點
- 對于大規(guī)模數(shù)據(jù)或者隨機數(shù)據(jù)，插入排序的時間復(fù)雜度較高，為O(n^2)。
- 是非穩(wěn)定的排序算法，即相等的元素可能會因為排序而變得順序顛倒。
復(fù)雜度
- 時間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：O(1)
使用場景
- 小型數(shù)據(jù)集：對于小型的數(shù)據(jù)集，插入排序是一種高效且簡單的排序算法
- 部分排序的數(shù)據(jù)集：如果一個數(shù)據(jù)集大部分是排序的，那么插入排序?qū)⑹且粋€很好的選擇。例如，考慮一個場景，一個團(tuán)隊在一場比賽中獲得了一組分?jǐn)?shù)，這些分?jǐn)?shù)按照高低已經(jīng)被排序，但是有一個新的分?jǐn)?shù)需要插入到合適的位置。在這種情況下，插入排序可以快速找到新分?jǐn)?shù)的位置并把它插入到正確的位置。
- 外部排序：當(dāng)處理非常大的數(shù)據(jù)集時，可能需要使用外部排序。外部排序是指那些不能一次性加載到內(nèi)存中的數(shù)據(jù)的排序。在這種情況下，可以使用插入排序作為子程序，從外部存儲器中讀取元素并將它們插入到已經(jīng)排序的部分中。
- 與其他算法結(jié)合：插入排序也可以與其他算法結(jié)合使用。例如，當(dāng)需要先對數(shù)據(jù)進(jìn)行排序，然后再進(jìn)行一些復(fù)雜的操作時，可以使用插入排序作為預(yù)處理步驟。
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】十大經(jīng)典排序算法-插入排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
