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

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



前言:

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

冒泡排序:

设定:

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

分类:

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

起源:

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

图解冒泡:

图中绿色:

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

图中橙色:

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

整体思路:

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

最后求点赞啦:

相关文章
|
1月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
104 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
13 0
|
1月前
|
搜索推荐 算法
排序算法---冒泡&选择&插入总结
排序算法---冒泡&选择&插入总结
14 0
|
1月前
|
算法
计科一二班算法数据结构实验9答案
计科一二班算法数据结构实验9答案
14 0
|
3月前
|
算法 Java 测试技术
算法分析(蛮力法与减治算法应用实验报告)
这篇文章是关于算法分析的实验报告,介绍了如何使用蛮力法解决背包问题,并通过伪代码和Java代码实现,同时分析了其时间效率;还介绍了基于减治法思想实现的二叉查找树的插入与查找,同样提供了伪代码、Java源代码实现和时间效率分析,最后展示了测试结果截图。
算法分析(蛮力法与减治算法应用实验报告)
|
3月前
|
搜索推荐 算法
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
|
3月前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
3月前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
41 0
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。