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

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

 

目录

⚽前言：

🏐 冒泡排序：

设定：

分类：

起源：

图解冒泡：

图中绿色：

图中橙色：

整体思路：

交换思路：

核心代码： 

🏀 图解插入：

设定：

插入思路：

整体思路：

核心代码：

🥎图解选择： 

设定：

整体思路：

核心代码： 

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

---

前言：

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

 冒泡排序：

设定：

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

分类：

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

起源：

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

图解冒泡：

图中绿色：

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

图中橙色：

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

整体思路：

不难发现每一轮子排序我们都将得到一个待排序中的最大数。也就是说第一轮得到所有数中的最大值。然后第二轮得到所有数中的次大值（因为此时最大值不参与排序），第三轮得到第三大值。如此循环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;
}

最后求点赞啦： 

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

---