读书笔记-《数据结构与算法》-摘要4[插入排序]
2023-12-14 05:34:20
插入排序
核心:通过构建有序序列,对于未排序序列,在已排序序列中从后向前扫描(对于单向链表则只能从前往后遍历),找到相应位置并插入。实现上通常使用in-place排序(需用到O(1)的额外空间)
- 从第一个元素开始,该元素可认为已排序
- 取下一个元素,对已排序数组从后往前扫描
- 若从排序数组中取出的元素大于新元素,则移至下一位置
- 重复步骤3,直至找到已排序元素小于或等于新元素的位置
- 插入新元素至该位置
- 重复2~5
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
希尔排序
核心:基于插入排序,使数组中任意间隔为h的元素都是有序的,即将全部元素分为h个区域使用插入排序。其实现可类似于插入排序但使用不同增量。更高效的原因是它权衡了子数组的规模和有序性。
推荐大佬文章:排序算法 —— 希尔排序(图文超详细)
从网上搞了一个动图
(图网,侵删)
文章来源:https://blog.csdn.net/JustDI0209/article/details/134860917
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!