三亚网络网站建设,北京婚纱摄影网站,微信公众平台开发者是什么,wordpress中医主题文章目录C017-C冒泡排序与插入排序冒泡排序与插入排序目标冒泡排序排序规则冒泡排序优化插入排序题目描述在线练习#xff1a;总结C017-C冒泡排序与插入排序 在线练习#xff1a; http://noi.openjudge.cn/ https://www.luogu.com.cn/
冒泡排序与插入排序
参考#xff1a;…
文章目录C017-C冒泡排序与插入排序冒泡排序与插入排序目标冒泡排序排序规则冒泡排序优化插入排序题目描述在线练习总结C017-C冒泡排序与插入排序 在线练习 http://noi.openjudge.cn/ https://www.luogu.com.cn/
冒泡排序与插入排序
参考
目标 1.理解并掌握冒泡排序基本原理 2.理解并掌握插入排序基本原理 3.掌握冒泡排序与插入排序的基本使用 冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有元素再需要交换也就是说该数列已经排序完成。 这个算法的名字由来是因为越小的元素会经由交换像气泡一样慢慢“浮”到数列的顶端。
排序规则 每次比较相邻的元素如果第一个比第二个大就交换他们两个。对每—对相邻元素做同样的工作从开始第一对到结尾的最后一对。经过一轮排序后最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤除了最后一个。 持续每轮对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较也就是已经是按照从小到大的顺序排列了。 每轮比较都会确定一个数字的位置因此N个数字需要比较N-1轮。如如果是5个数比较则 第一轮比较了4次 第二轮比较3次 第三轮比较2次 第四轮比较1次 那么第i轮比较的次数为N-i次。 每次比较均是对相邻两个数字作比较直至最后。 #include iostreamusing namespace std;int main()
{int n;int a[6]{0,3,4,1,5,2};nsizeof(a)/sizeof(int);coutnendl;int outres0;for(int i1;in;i){outres;int innerres0;for(int j1;jn-i;j){innerres;if(a[j]a[j1]){swap(a[j],a[j1]);}cout执行的外循环次数--outres执行的内循环次数--innerresendl;}}for(int i1;i5;i){couta[i] ;}return 0;
}冒泡排序优化
参考冒泡排序的三种优化 刚才对于序列{1235,991876}的排序过程中我们不难发现第二轮排序进行完之后整个序列已经是有序的了也就是说第二轮排序结束就可以不用接着进行接下来的比较了。
因此我们可以对刚才的程序进行优化那么什么时候就可以结束排序过程呢?根据观察我们发现当某轮排序过程中没有交换的发生那么就说明序列已经有序无需再次比较了。
#include iostreamusing namespace std;int main()
{int n;int a[6]{0,3,4,1,5,2};nsizeof(a)/sizeof(int);coutnendl;int outres0;for(int i1;in;i){bool flag0;// 优化 标记是否有交换outres;int innerres0;for(int j1;jn-i;j){innerres;if(a[j]a[j1]){flag1;//优化 有交换标记1swap(a[j],a[j1]);}cout执行的外循环次数--outres执行的内循环次数--innerresendl;}if(flag0)break;//优化 有交换标记1}for(int i1;i5;i){couta[i] ;}return 0;
}如
插入排序
插入排序(Insertion sort)是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列要求在这个已经排好的数据序列中插入一个数但要求插入后此数据序列仍然有序这个时候就要用到一种新的排序方法—插入排序法。 插入排序的基本操作就是将一个数据插入到已经排好序的有序数列中从而得到一个新的、个数加一的有序数列算法适用于少量数据的排序。 1、从第一个元素开始该元素被认为已被排序。 2、取出下一个元素在已排序的序列中从后往前扫描。 3、如果该元素大于新元素将该元素移到下一个位置。 4、重复步骤3直到找到已排序的元素小于或者等于新元素的位置。5、将新元素插入后重复步骤2~5。 接下来我们以对序列{563781}从小到大排序为例来讲解插入排序的具体过程。 第一步:有序序列为{5}。 第二个数6开始进行插入排序。因为5是小于6的所以位置不 用改动。在第二个位置插入数字6得到有序序列{56}。 第二步:有序序列为{56}。 第三个数3开始进行插入排序。由于56均大于3因此数字5、6需要往后挪一个位置。然后再将3放到第一个位置。得到有序序列{356}。 第三步:有序序列为{356}。 第四个数1开始进行插入排序。由于356均大于1因此数字3、5、6需要往后挪一个位置。然后再将1放到第一个位置。得到有序序列{13,56}。 第四步:有序序列为{1356}。 第五个数8开始进行插入排序。由于1、3、5、6都是小于8的所以位置不用改动。在最后一个位置插入数字8得到有序序列{13568}。 第五步:有序序列为{13568}。 第七个数7开始进行插入排序。因为1、3、5、6都是小于7的所以位置不用改动由于8大于7因此往后挪一个位置然后在6和8之间插入数字7。得到有序序列{135678}。 至此整个插入排序过程完成。 #include iostreamusing namespace std;int a[10005];int main()
{int n;int key,j;cinn;for(int i1;in;i) cina[i];for(int i2;in;i){//从第二个开始排序keya[i]; //待记录插入的数字ji-1;//令j已有序列的尾位置while(j1keya[j]) //从后往前遍历序列已有序列直到第一个比key小的位置{a[j1]a[j];//当前元素比关键字大则往前插空j--;}a[j1]key;//直到无法前移的时候将key插入空出的位置}for(int i1;in;i) couta[i] ;return 0;
}题目描述 在线练习
http://noi.openjudge.cn/
总结
本系列为C学习系列会介绍C基础语法基础算法与数据结构的相关内容。本文为C冒泡排序与插入排序案例包括相关案例练习。
