插入排序
核心：通過(guò)構(gòu)建有序序列，對(duì)于未排序序列，在已排序序列中從后向前掃描(對(duì)于單向鏈表則只能從前往后遍歷)，找到相應(yīng)位置并插入。實(shí)現(xiàn)上通常使用in-place排序(需用到O(1)的額外空間)
- 從第一個(gè)元素開(kāi)始，該元素可認(rèn)為已排序
- 取下一個(gè)元素，對(duì)已排序數(shù)組從后往前掃描
- 若從排序數(shù)組中取出的元素大于新元素，則移至下一位置
- 重復(fù)步驟3，直至找到已排序元素小于或等于新元素的位置
- 插入新元素至該位置
- 重復(fù)2~5
![讀書(shū)筆記-《數(shù)據(jù)結(jié)構(gòu)與算法》-摘要4[插入排序],讀書(shū)筆記,排序算法,算法](https://imgs.yssmx.com/Uploads/2023/12/759772-1.gif)
public class InsertionSort {
public static void main(String[] args) {
int unsortedArray[] = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
insertionSort(unsortedArray);
System.out.println("After sort: ");
for (int item : unsortedArray) {
System.out.print(item + " ");
}
}
public static void insertionSort(int[] array) {
int len = array.length;
for (int i = 0; i < len; i++) {
int index = i, array_i = array[i];
while (index > 0 && array[index - 1] > array_i) {
array[index] = array[index - 1];
index -= 1;
}
array[index] = array_i;
/* print sort process */
for (int item : array) {
System.out.print(item + " ");
}
System.out.println();
}
}
}
輸出：
6 5 3 1 8 7 2 4
5 6 3 1 8 7 2 4
3 5 6 1 8 7 2 4
1 3 5 6 8 7 2 4
1 3 5 6 8 7 2 4
1 3 5 6 7 8 2 4
1 2 3 5 6 7 8 4
1 2 3 4 5 6 7 8
After sort:
1 2 3 4 5 6 7 8
希爾排序
核心：基于插入排序，使數(shù)組中任意間隔為h的元素都是有序的，即將全部元素分為h個(gè)區(qū)域使用插入排序。其實(shí)現(xiàn)可類似于插入排序但使用不同增量。更高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性。
推薦大佬文章：排序算法 —— 希爾排序（圖文超詳細(xì)）
從網(wǎng)上搞了一個(gè)動(dòng)圖
![讀書(shū)筆記-《數(shù)據(jù)結(jié)構(gòu)與算法》-摘要4[插入排序],讀書(shū)筆記,排序算法,算法](https://imgs.yssmx.com/Uploads/2023/12/759772-2.gif)
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-759772.html
(圖網(wǎng)，侵刪)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-759772.html
到了這里，關(guān)于讀書(shū)筆記-《數(shù)據(jù)結(jié)構(gòu)與算法》-摘要4[插入排序]的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
