許久沒有寫點東西了，答辯之后人也變得松懈，今天看到簡書又有人點贊之前記錄的冒泡排序，點進去一看，居然有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 發布！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/5107.html
標籤：其他
上一篇：如何優雅地向公司提加薪