排序—插入排序
- 2020 年 6 月 9 日
- 筆記
許久沒有寫點東西了，答辯之後人也變得鬆懈。今天看到簡書又有人點贊之前記錄的冒泡排序，點進去一看，居然有4w+的閱讀量，心生疑問，咋會有這麼高的閱讀量，打開百度搜索冒泡排序，結果第3條就是我的。點開認真看了看，其實寫得不好，還改了兩個錯別字(狗頭)，這個閱讀量或許只是記錄的點擊量。但我萌生一個想法，趁現在有時間，想把排序系列做完，便於以後自己回顧。
排序系列傳遞門
排序—冒泡排序
排序—選擇排序
排序—快速排序
排序-希爾排序（待完善）
排序—歸併排序（待完善）
排序—基數排序（待完善）
排序—堆排序（待完善）
排序—桶排序（待完善）
排序—計數排序（待完善）
排序—排序算法總結（待完善）
插入排序思想
基本思想是在一個有序的序列中找到待排序元素的位置，比如將3插入-1，2，4，6這個有序序列中，先與6和4比較，直到和2比較之後，找到適合插入的位置(2之後)。
下面以按升序排序為例：
- step1 第一個元素默認有序。
- step2 取待排序的元素B，在有序序列上從後往前尋找。
- step3 如果已排序元素A大於待排序的元素B，則將A往後移動一位。
- step4 重複step3，直到找到元素A<=B(待排序)時或者有序序列全部被掃描。將待排序元素A插入。
- 重複step2—step4
動圖展示(圖片來源見參考資料)
代碼實現(java)
/**
* 插入排序
* @param arr
*/
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return;
int curEle, preIndex; // 記錄當前待排序元素和前一個元素的下標
for(int i = 0; i < arr.length; i++) {
preIndex = i - 1;
curEle = arr[i];
while(preIndex >=0 && arr[preIndex] > curEle){
arr[preIndex + 1] = arr[preIndex]; // 移動元素
preIndex--;
}
// 將待排序元素插入新的位置
arr[preIndex + 1] = curEle;
}
}
算法分析
時間複雜度：$O(n^2)$
空間複雜度：$O(1)$
穩定性：穩定
參考資料
最後
本文若有不當，請指出。
此致，敬禮！
本文由博客一文多發平台 OpenWrite 發佈！
