首页 > 编程语言 > 详细

锵锵锵,又来了——冒泡排序

时间:2020-01-24 16:13:14      阅读:92      评论:0      收藏:0      [点我收藏+]

虽然桶排序很方便,但是它非常浪费空间!!!在多大范围就要开多大的空间,seriously?!

所以,推出了一种新的算法:冒泡排序!

其思想就是比较相邻的两个元素,如果与题目不符就交换

技术分享图片

 

 

如上图就是利用冒泡每次都与相邻的比较,最后在最后一位的就是最大的数,依次排列完成想法!

  • 比较相邻的元素,如果前一个比后一个大,交换之。
  • 第一趟排序第1个和第2个一对,比较与交换,随后第2个和第3个一对比较交换,这样直到倒数第2个和最后1个,将最大的数移动到最后一位。
  • 第二趟将第二大的数移动至倒数第二位

最后需要n-1次

#include <stdio.h>
int main()
{
  int a[100],i,j,t,n;
    scanf("%d",&n);  //输入一个数n,表示接下来有n个数
    for(i=1;i<=n;i++)  //循环读入n个数到数组a中
        scanf("%d",&a[i]);
    //冒泡排序的核心部分
    for(i=1;i<=n-1;i++) //n个数排序,只用进行n-1趟
    {
        for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数。
        {
            if(a[j]<a[j+1]) //比较大小并交换
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t;  }
        }
    }
    for(i=1;i<=n;i++)  //输出结果
        printf("%d ",a[i]);
    getchar();getchar();
    return 0;

}
#include <stdio.h>
struct student
{
    char name[21];
    char score;
};//这里创建了一个结构体用来存储姓名和分数
int main()
{
    struct student a[100],t;
    int i,j,n;
    scanf("%d",&n); //输入一个数n
    for(i=1;i<=n;i++) //循环读入n个人名和分数
    scanf("%s %d",a[i].name,&a[i].score);
    //按分数从高到低进行排序
    for(i=1;i<=n-1;i++) 
    {
        for(j=1;j<=n-i;j++)
        {
            if(a[j].score<a[j+1].score)//对分数进行比较
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t; //可以将结构体整个进行交换 }
        }
    }
    for(i=1;i<=n;i++)//输出人名
        printf("%s\n",a[i].name);
    getchar();getchar();
    return 0;
}
输入:
5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8
输出:
gaoshou
huhu
xixi
haha
hengheng

利用了冒泡对成绩进行了排序

冒泡的时间复杂度是O[N^2]
空间复杂度是O[1]

锵锵锵,又来了——冒泡排序

原文:https://www.cnblogs.com/-113/p/12232295.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!