🌟个人博客:www.hellocode.top
🏰Java知识导航:Java-Navigate
🔥CSDN:HelloCode.
🌞知乎:HelloCode
🌴掘金:HelloCode
⚡如有问题,欢迎指正,一起学习~~
插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录插入完成为止。
基本思想
如上图所示,插入排序的基本思想就是将一个数组划分为两部分:有序部分和无序部分。通过将无序部分的元素依次插入有序部分(需要找到对应的正确位置),让每次插入的每个元素都能在正确的位置,保证有序部分始终有序,在将无序部分的元素全部插入到有序部分后,整个集合也就为有序的了。
- 从第二个元素开始,依次将当前元素插入到已排好序的有序序列中,直到最后一个元素。
- 插入当前元素时,从后往前遍历已排好序的有序序列,找到当前元素在有序序列中的位置,并将其插入到该位置。
- 重复执行步骤2,直到所有元素都插入完毕。
举个例子,比如我们有一组数字 [5, 3, 8, 4, 2],我们可以首先把第一个数字5视为已排序序列,然后从第二个数字3开始,与已排序序列中的元素逐一比较,找到合适的位置插入。然后针对第三个数字8,我们再重复这个过程,直至所有的数字都插入到已排序序列中。
代码实现
具体的代码就是两层for循环,外层控制未排序部分的指针,内层不断循环寻找新插入元素的正确位置,代码如下:
/**
* @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) {
// 外层循环,i指向数组中未排序的元素,也可以表示已经有序元素的个数
for (int i = 1; i < arr.length; i++) {
// 内层for指向已经排好序的最后一个元素
for (int j = i - 1; j >= 0; j--) {
// 开始排序,寻找新加入的元素的正确位置,(j + 1)代表新加入的元素
if (arr[j + 1] >= arr[j]) {
// 代表不用交换,加入即有序,直接跳出循环
break;
}
// 否则需要进行交换,直到找到合适位置
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
测试:
优化
对于插入排序,能够优化的点我认为是在为新插入元素寻找正确位置的时候,上面的代码采用的是依次比较,类似于冒泡排序的思想。如果数据量大且情况最差的时候,效率就有些不理想了,因此可以用其他方法在此处进行优化,提升插入排序的性能
二分查找:在每次需要插入元素时,使用二分查找来找到插入的位置,而不是从头到尾扫描已排序序列。这样可以将比较次数降低为O(log n)。文章来源:https://www.toymoban.com/news/detail-636391.html
具体代码这里就不列了,后面可能会有专门的二分查找文章。文章来源地址https://www.toymoban.com/news/detail-636391.html
总结
优点
- 实现简单,对于部分有序的数组效率高。
- 对于小规模数据或者部分有序的数据,插入排序的运行时间相对较短。
缺点
- 对于大规模数据或者随机数据,插入排序的时间复杂度较高,为O(n^2)。
- 是非稳定的排序算法,即相等的元素可能会因为排序而变得顺序颠倒。
复杂度
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
使用场景
- 小型数据集:对于小型的数据集,插入排序是一种高效且简单的排序算法
- 部分排序的数据集:如果一个数据集大部分是排序的,那么插入排序将是一个很好的选择。例如,考虑一个场景,一个团队在一场比赛中获得了一组分数,这些分数按照高低已经被排序,但是有一个新的分数需要插入到合适的位置。在这种情况下,插入排序可以快速找到新分数的位置并把它插入到正确的位置。
- 外部排序:当处理非常大的数据集时,可能需要使用外部排序。外部排序是指那些不能一次性加载到内存中的数据的排序。在这种情况下,可以使用插入排序作为子程序,从外部存储器中读取元素并将它们插入到已经排序的部分中。
- 与其他算法结合:插入排序也可以与其他算法结合使用。例如,当需要先对数据进行排序,然后再进行一些复杂的操作时,可以使用插入排序作为预处理步骤。
到了这里,关于【数据结构与算法】十大经典排序算法-插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!