建e网站,河南网站建设设计价格,整站seo排名,厦门seo公司到1火星目录
⚽前言#xff1a;
#x1f3d0; 冒泡排序#xff1a;
设定#xff1a;
分类#xff1a;
起源#xff1a;
图解冒泡#xff1a;
图中绿色#xff1a;
图中橙色#xff1a;
整体思路#xff1a;
交换思路#xff1a;
核心代码#xff1a;
#x…
目录
⚽前言 冒泡排序
设定
分类
起源
图解冒泡
图中绿色
图中橙色
整体思路
交换思路
核心代码 图解插入
设定
插入思路
整体思路
核心代码
图解选择
设定
整体思路
核心代码
山东大学实验二完整代码 前言
冒泡、插入、选择排序的都是最基础的排序算法。其时间复杂度、空间复杂度都较高但是学起来相对容易非常适合新手入门学习。并且里面所蕴含的思想也是非常深刻值得我们细细体味下面就让我们逐个进入吧。 冒泡排序
设定
首先不妨设定我们需要实现的是从小到大的排序
分类
冒泡分为两种一、前向后 二、后向前。
起源
让我们先来想想水中的气泡是如何从水底浮上来的。是不是从最底下然后逐渐慢慢的向上浮动直到最终露出水面。那如果有很多气泡呢那是不是肯定是最轻的气泡先浮上来然后最重的气泡排在后面再浮上来。这个生活常识就是我们冒泡排序的起源。
图解冒泡 图中绿色
在一次次变动的就是每一趟下的冒泡子排序其目的是为了选出目前待排序的数中最大的一个。
图中橙色
是每一轮冒泡子排序下得到的最大结果。
整体思路
不难发现每一轮子排序我们都将得到一个待排序中的最大数。也就是说第一轮得到所有数中的最大值。然后第二轮得到所有数中的次大值因为此时最大值不参与排序第三轮得到第三大值。如此循环n-1次最后完成排序。
交换思路
每次选择两个数前面的与后面的比较若前面大后面小则两者交换。第一次选择1、2数第二次选择2、3数第三次选择3、4数如此重复。如图中的绿色不停比较交换所体现的
核心代码 coutBubble Sortendl;for(int i0;inum;i){for(int jnum-1;ji;j--){if(a[j]a[j-1])swap(a[j],a[j-1]);}}for(int i0;inum-1;i){couta[i],;}couta[num-1]endl;时间复杂度最坏情况O(N^2) 最好情况O(N) 空间复杂度O(1) 插入排序
设定
首先不妨设定我们需要实现的是从小到大的排序
插入思路
假如我们有一个有序的序列现在要将一个数插入这个序列中要求序列仍然有序。那么我们就要从第一个数开始和待插入数进行比较如果第一个数小于待插入数说明这个数可能还要插入到后面。于是我们再看第二个数和插入数的大小关系重复上面的操作。直到我们遇到一个数大于待插入数那么此时待插入数必然是插入在这个数的前一个于是我们实现插入。
整体思路 整体思路就是进行多次前面提到的插入过程。
橙色已经有序的序列
绿色待插入有序序列的数
蓝色本轮未轮到插入的序列后续需要插入
再来个动图 核心代码 coutInsert Sortendl;int res[19]{0};for(int i0;inum;i){int j0;for(ji-1;j0;j--){if(a[i]res[j])res[j1]res[j];elsebreak;}res[j1]a[i];}for(int i0;inum-1;i){coutres[i],;}coutres[num-1]endl;
选择排序
设定
首先不妨设定我们需要实现的是从小到大的排序
整体思路 每次从待排序列中选出一个最小值然后放在序列的起始位置直到全部待排数据排完即可。 实际上我们可以一趟选出两个值一个最大值一个最小值然后将其放在序列开头和末尾这样可以使选择排序的效率快一倍。 橙色已经完成的有序的序列
红色不停在找待排序序列中最小的找到后就和最前面的蓝色的数进行交换
核心代码 coutSelect Sortendl;int res[19]{0};int x0;for(int i0;inum;i){int minINT_MAX;int pos0;for(int j0;jnum;j){if(mina[j]){mina[j];posj;}}a[pos]INT_MAX;res[x]min;}for(int i0;inum-1;i){coutres[i],;}coutres[num-1]endl;
山东大学实验二完整代码
#includeiostream
using namespace std;void multiSelect(int a[],int sel,int num){switch (sel){case 1:{coutBubble Sortendl;for(int i0;inum;i){for(int jnum-1;ji;j--){if(a[j]a[j-1])swap(a[j],a[j-1]);}}for(int i0;inum-1;i){couta[i],;}couta[num-1]endl;break;}case 2:{coutInsert Sortendl;int res[19]{0};for(int i0;inum;i){int j0;for(ji-1;j0;j--){if(a[i]res[j])res[j1]res[j];elsebreak;}res[j1]a[i];}for(int i0;inum-1;i){coutres[i],;}coutres[num-1]endl;break;}case 3:{coutSelect Sortendl;int res[19]{0};int x0;for(int i0;inum;i){int minINT_MAX;int pos0;for(int j0;jnum;j){if(mina[j]){mina[j];posj;}}a[pos]INT_MAX;res[x]min;}for(int i0;inum-1;i){coutres[i],;}coutres[num-1]endl;break;}default:break;}
}int main(){coutInputendl;int a[19]{0};int num0;for(int i0;i18;i){int t0;cint;if(t0)break;else{a[i]t;num;}}cout1-Bubble Sort,2-Insert Sort,3-Select Sortendl;int sel0;cinsel;coutOutputendl;multiSelect(a,sel,num);coutEndendl;
}
最后求点赞啦
