前言:
冒泡、插入、选择排序的都是最基础的排序算法。其时间复杂度、空间复杂度都较高,但是学起来相对容易,非常适合新手入门学习。并且里面所蕴含的思想也是非常深刻,值得我们细细体味!下面就让我们逐个进入吧。
冒泡排序:
设定:
首先不妨设定我们需要实现的是从小到大的排序
分类:
冒泡分为两种:一、前向后 二、后向前。
起源:
让我们先来想想水中的气泡是如何从水底浮上来的。是不是从最底下然后逐渐慢慢的向上浮动,直到最终露出水面。那如果有很多气泡呢?那是不是肯定是最轻的气泡先浮上来,然后最重的气泡排在后面再浮上来。这个生活常识就是我们冒泡排序的起源。
图解冒泡:
图中绿色:
在一次次变动的就是每一趟下的冒泡子排序,其目的是为了选出目前待排序的数中最大的一个。
图中橙色:
是每一轮冒泡子排序下得到的最大结果。
整体思路:
不难发现每一轮子排序我们都将得到一个待排序中的最大数。也就是说第一轮得到所有数中的最大值。然后第二轮得到所有数中的次大值(因为此时最大值不参与排序),第三轮得到第三大值。如此循环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]; else break; } 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]; else break; } 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; }
最后求点赞啦: