图解基础排序算法(冒泡、插入、选择)(山东大学实验二)

2024-01-17 07:20

本文主要是介绍图解基础排序算法(冒泡、插入、选择)(山东大学实验二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

目录

⚽前言:

🏐 冒泡排序:

设定:

分类:

起源:

图解冒泡:

图中绿色:

图中橙色:

整体思路:

交换思路:

核心代码: 

🏀 图解插入:

设定:

插入思路:

整体思路:

核心代码:

🥎图解选择: 

设定:

整体思路:

核心代码: 

🎱山东大学实验二完整代码: 


前言:

冒泡、插入、选择排序的都是最基础的排序算法。其时间复杂度、空间复杂度都较高,但是学起来相对容易,非常适合新手入门学习。并且里面所蕴含的思想也是非常深刻,值得我们细细体味!下面就让我们逐个进入吧。

 冒泡排序:

设定:

首先不妨设定我们需要实现的是从小到大的排序

分类:

冒泡分为两种:一、前向后  二、后向前。

起源:

让我们先来想想水中的气泡是如何从水底浮上来的。是不是从最底下然后逐渐慢慢的向上浮动,直到最终露出水面。那如果有很多气泡呢?那是不是肯定是最轻的气泡先浮上来,然后最重的气泡排在后面再浮上来。这个生活常识就是我们冒泡排序的起源。

图解冒泡:

图中绿色:

在一次次变动的就是每一趟下的冒泡子排序,其目的是为了选出目前待排序的数中最大的一个。

图中橙色:

是每一轮冒泡子排序下得到的最大结果。

整体思路:

不难发现每一轮子排序我们都将得到一个待排序中的最大数。也就是说第一轮得到所有数中的最大值。然后第二轮得到所有数中的次大值(因为此时最大值不参与排序),第三轮得到第三大值。如此循环n-1次,最后完成排序。

交换思路:

每次选择两个数,前面的与后面的比较,若前面大后面小则两者交换。第一次选择1、2数,第二次选择2、3数,第三次选择3、4数,如此重复。如图中的绿色不停比较交换所体现的

核心代码: 

        cout<<"Bubble Sort"<<endl;for(int i=0;i<num;i++){for(int j=num-1;j>i;j--){if(a[j]<a[j-1])swap(a[j],a[j-1]);}}for(int i=0;i<num-1;i++){cout<<a[i]<<',';}cout<<a[num-1]<<endl;

时间复杂度:最坏情况:O(N^2)
      最好情况:O(N)
空间复杂度:O(1)

 插入排序:

设定:

首先不妨设定我们需要实现的是从小到大的排序

插入思路:

假如我们有一个有序的序列,现在要将一个数插入这个序列中要求序列仍然有序。那么我们就要从第一个数开始和待插入数进行比较,如果第一个数小于待插入数,说明这个数可能还要插入到后面。于是我们再看第二个数和插入数的大小关系,重复上面的操作。直到我们遇到一个数大于待插入数,那么此时待插入数必然是插入在这个数的前一个,于是我们实现插入。

整体思路:

整体思路就是进行多次前面提到的插入过程。

橙色:已经有序的序列

绿色:待插入有序序列的数 

蓝色:本轮未轮到插入的序列,后续需要插入 

再来个动图:

核心代码:

        cout<<"Insert Sort"<<endl;int res[19]={0};for(int i=0;i<num;i++){int j=0;for(j=i-1;j>=0;j--){if(a[i]<res[j])res[j+1]=res[j];elsebreak;}res[j+1]=a[i];}for(int i=0;i<num-1;i++){cout<<res[i]<<',';}cout<<res[num-1]<<endl;

选择排序: 

设定:

首先不妨设定我们需要实现的是从小到大的排序

整体思路:


每次从待排序列中选出一个最小值,然后放在序列的起始位置,直到全部待排数据排完即可。
实际上,我们可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

橙色:已经完成的有序的序列

红色:不停在找待排序序列中最小的,找到后就和最前面的蓝色的数进行交换

核心代码: 

        cout<<"Select Sort"<<endl;int res[19]={0};int x=0;for(int i=0;i<num;i++){int min=INT_MAX;int pos=0;for(int j=0;j<num;j++){if(min>a[j]){min=a[j];pos=j;}}a[pos]=INT_MAX;res[x++]=min;}for(int i=0;i<num-1;i++){cout<<res[i]<<',';}cout<<res[num-1]<<endl;

山东大学实验二完整代码: 

#include<iostream>
using namespace std;void multiSelect(int a[],int sel,int num){switch (sel){case 1:{cout<<"Bubble Sort"<<endl;for(int i=0;i<num;i++){for(int j=num-1;j>i;j--){if(a[j]<a[j-1])swap(a[j],a[j-1]);}}for(int i=0;i<num-1;i++){cout<<a[i]<<',';}cout<<a[num-1]<<endl;break;}case 2:{cout<<"Insert Sort"<<endl;int res[19]={0};for(int i=0;i<num;i++){int j=0;for(j=i-1;j>=0;j--){if(a[i]<res[j])res[j+1]=res[j];elsebreak;}res[j+1]=a[i];}for(int i=0;i<num-1;i++){cout<<res[i]<<',';}cout<<res[num-1]<<endl;break;}case 3:{cout<<"Select Sort"<<endl;int res[19]={0};int x=0;for(int i=0;i<num;i++){int min=INT_MAX;int pos=0;for(int j=0;j<num;j++){if(min>a[j]){min=a[j];pos=j;}}a[pos]=INT_MAX;res[x++]=min;}for(int i=0;i<num-1;i++){cout<<res[i]<<',';}cout<<res[num-1]<<endl;break;}default:break;}
}int main(){cout<<"Input"<<endl;int a[19]={0};int num=0;for(int i=0;i<18;i++){int t=0;cin>>t;if(t==0)break;else{a[i]=t;num++;}}cout<<"1-Bubble Sort,2-Insert Sort,3-Select Sort"<<endl;int sel=0;cin>>sel;cout<<"Output"<<endl;multiSelect(a,sel,num);cout<<"End"<<endl;
}

最后求点赞啦: 

这篇关于图解基础排序算法(冒泡、插入、选择)(山东大学实验二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/615262

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO