【数据结构】直接插入排序

news/发布时间2024/6/15 17:59:00

大家好,我是苏貝,本篇博客带大家了解插入排序,如果你觉得我写的还不错的话,可以给我一个赞👍吗,感谢❤️
在这里插入图片描述


目录

  • 一. 基本思想
  • 二. 插入排序详解(以升序为例)
  • 三. 对比冒泡排序

一. 基本思想

直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列
实际中我们玩扑克牌时,就用了插入排序的思想

在这里插入图片描述

在这里插入图片描述

二. 插入排序详解(以升序为例)

思路:

我们让数组下标为[0,end]的有序,现插入a[end+1],使数组下标为[0,end+1]的有序。
最开始时,我们让end==0,这样就是插入a[1],让数组下标为[0,1]的有序

在这里插入图片描述

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移

下面代码中,因为最后一个元素一定是tmp,所以end+1<n,所以end<n-1,因为end=i,所以i<n-1。

void InsertSort(int* a, int n)
{//假设[0,end]有序,将a[end+1]插入再次形成有序for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}

插入排序的时间复杂度是多少?
时间复杂度是在最坏情况下计算的,插入排序的最坏情况就是降序
第一次:1
第二次:2
……
第N-1次:N-1
全部加起来=1+2+……+(N-1) = (N+1)(1+N-1)/2 = N*(N-1)/2,所以时间复杂度为O(N^2)

直接插入排序的特性总结:
1.元素集合越接近有序,直接插入排序算法的时间效率越高
2.时间复杂度:O(N^2)
3.空间复杂度:O(1),它是一种稳定的排序算法
4.稳定性:稳定

三. 对比冒泡排序

点击了解冒泡排序

在这里插入图片描述

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);}}}
}

冒泡排序的时间复杂度是多少?
总共需要冒泡N-1次
第一次冒泡:循环N-1次
第二次冒泡:N-2
第三次冒泡:N-3

第N-1次冒泡:1
全部加起来=1+2+……+(N-1) = (N+1)(1+N-1)/2 = N*(N-1)/2,所以时间复杂度为O(N^2)

所以插入排序和冒泡排序的时间复杂度是一样的,那能说明它们的效率是一样的吗?在这里我们用一个函数来测试两个排序的性能。让两种排序都排列同样的100000个随机数字,比较2个排序的时间。rand函数用来生成随机值,clock函数用来返回程序运行的时间。因为2种排序用的时间都比较长,所以在这里我们将Debug换成Release

void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();BubbleSort(a7, N);int end2 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("BubbleSort:%d\n", end2 - begin2);free(a1);free(a2);
}

在这里插入图片描述

结果如下:我们发现,虽然它们的时间复杂度在同一层级,但是插入排序还是优于冒泡排序的。

在这里插入图片描述
在这里插入图片描述


好了,那么本篇博客就到此结束了,如果你觉得本篇博客对你有些帮助,可以给个大大的赞👍吗,感谢看到这里,我们下篇博客见❤️

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.shwantai.cn/a/78705602.html

如若内容造成侵权/违法违规/事实不符,请联系万泰站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

使用CUDA 为Tegra构建OpenCV

返回&#xff1a;OpenCV系列文章目录&#xff08;持续更新中......&#xff09; 上一篇&#xff1a;MultiArch与Ubuntu/Debian 的交叉编译 下一篇&#xff1a;在iOS中安装 警告&#xff1a; 本教程可能包含过时的信息。 使用CUDA for Tegra 的OpenCV 本文档是构建支持 CUD…

Redis - 高并发场景下的Redis最佳实践_翻过6座大山

文章目录 概述6座大山之_缓存雪崩 &#xff08;缓存全部失效&#xff09;缓存雪崩的两种常见场景如何应对缓存雪崩&#xff1f; 6座大山之_缓存穿透&#xff08;查询不存在的 key&#xff09;缓存穿透的原因解决方案1. 数据校验2. 缓存空值3. 频控4. 使用布隆过滤器 6座大山之_…

关于汽车中网改装需要报备吗?(第二天)

车联网改造需要申报吗&#xff1f; 今天2022年10月20日&#xff0c;小编就给大家介绍一下车联网改装是否需要申报的相关知识。 让我们来看看。 汽车格栅改装无需申报。 这种年检可以直接通过。 您不必担心&#xff0c;因为汽车格栅对于实车的外观来说并不陌生&#xff0c;因此…

深度学习pytorch——激活函数损失函数(持续更新)

论生物神经元与神经网络中的神经元联系——为什么使用激活函数&#xff1f; 我们将生物体中的神经元与神经网络中的神经元共同分析。从下图可以看出神经网络中的神经元与生物体中的神经元有很多相似之处&#xff0c;由于只有刺激达到一定的程度人体才可以感受到刺激&#xff0c…

举4例说明Python如何使用正则表达式分割字符串

在Python中&#xff0c;你可以使用re模块的split()函数来根据正则表达式分割字符串。这个函数的工作原理类似于Python内置的str.split()方法&#xff0c;但它允许你使用正则表达式作为分隔符。 示例 1: 使用单个字符作为分隔符 假设你有一个由逗号分隔的字符串&#xff0c;你可…

【机器学习300问】44、P-R曲线是如何权衡精确率和召回率的?

关于精确率和召回率的基础概念我已经写了两篇文章&#xff0c;如果友友还不知道这两个评估指标是什么&#xff0c;可以先移步去看看这两篇文章&#xff1a; 【机器学习300问】25、常见的模型评估指标有哪些&#xff1f;http://t.csdnimg.cn/JtuUO 总结一下这两个概念&a…