专栏首页章鱼的慢慢技术路排序算法的实现与比较

排序算法的实现与比较

一、最快最简单的排序——桶排序

问题:让计算机随机读入5个数然后将这5个数从大到小输出。

分析:这里只需借助一个一维数组就可以解决这个问题

  1. 首先我们需要申请一个大小为11的数组 int a[11]并初始化为0。
  2. 下面开始处理每一个人的分数:假如第一个人的分数是5分,我们就将相对应的a[5]的值在原来的基础增加1,即将a[5]的值从0改为1,表示5出现过一次,以此类推下去。
  3. 其实a[0]~a[10]中的数值其实就是0分到10分每个分数出现的次数。接下来我们只需要将出现过的分数打印出来就可以了,出现几次就打印几次。
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
        a[i]=0;  //初始化为0
    
    for(i=1;i<=5;i++)  //循环读入5个数
    {
        scanf("%d",&t);
        a[t]++;
    } 
    
    for(i=0;i<=10;i++)  //依次判断a[0]~a[10]
        for(j=1;j<=a[i];j++)
            printf("%d",i);
    
    return 0; 

注:如果要实现从大到小排序,只需将for(i=0;i<=10;i++)改为for(i=10;i>=10;i--).

现在尝试输入n个0~1000之间的整数,将他们从大到小排序。

    int book[1001],i,j,t,n;  //我们需要1001个桶,来表示0~1000之间每一个数出现的次数
    for(i=0;i<=1000;i++)
        book[i]=0;
    scanf("%d",&n); 
    
    for(i=1;i<=n;i++)  //循环读入n个数,并进行桶排序 
    {
        scanf("%d",&t);
        book[t]++;
    } 
    
    for(i=1000;i>=0;i--)  //依次判断a[0]~a[10]
        for(j=1;j<=book[i];j++)
            printf("%d ",i);
    
    return 0; 

感受:桶排序固然快,但很浪费空间,而且不利于进行小数排序。

二、冒泡排序

基本思想:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。

原理:每一趟只能确定将一个数归位。

    int a[100],i,j,t,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)  //循环读入n个数到数组中 
        scanf("%d",&a[i]);
    /*冒泡程序的核心部分*/
    for(i=1;i<=n;i++)  //n个数排序,只用进行n-1趟
    {
        for(j=1;j<n-i;j++)  //从第一位开始比较直到最后一个尚未归位的数 
        {
            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]);
        
    return 0; 
#include<stdio.h>
struct student
{
    char name[21];
    int score;
};  //创建一个结构体用来存储学生的姓名和分数 
int main()
{
    struct student a[100],t;
    int i,j,n;
    scanf("%d",&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);
        
    return 0; 
}

总结: 如果有n个数进行排序,只需将n-1个数归位,也就是说要进行n-1趟操作。而每一趟都需要从第1位开始进行相邻两个数的比较,将较小的一个数放在后面,比较完毕后向后挪一位继续比较下面两个相邻数的大小,重复此步骤,直到最后一个尚未归位的数,已经归位的数则无需再进行比较。

冒泡排序的核心部分是双重嵌套循环,所以它的时间复杂度是O(N2)。

冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外,似乎没有什么值得推荐的。         ——Donald E.Knuth

三、最常用的排序——快速排序

思想:每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换,交换的距离大得多了。因此总的比较和交换次数就少了。

#include<stdio.h>
int a[10],n;  //定义全局变量
void quicksort(int left,int right)
{
    int i,j,t,temp;
    if(left>right)
        return;
    
    temp=a[left];  //temp中存的基准数
    i=left;
    j=right;
    while(i!=j)
    {
        while(a[j]>=temp && i<j)  //顺序很重要,要先从右往左找
            j--;
        while(a[i]<=temp && i<j)  //再从左往右找
            i++;
        /*交换两个数在数组中的位置*/
        if(i<j)  //当哨兵i和哨兵j没有相遇时
        {
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        } 
    } 
    /*最终将基准数归位*/
    a[left]=a[i];
    a[i]=temp;
    
    quicksort(left,i-1);  //继续处理左边的,这里是一个递归的过程
    quicksort(i+1,right);  //继续处理右边的,这里是一个递归的过程
    return; 
} 

int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    quicksort(1,n);  //快速排序调用
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);  //输出排序后的结果
        
    return 0; 
}

四、问题演练:买书

问题描述:小明想看看同学们都喜欢读哪些书,于是小明让每个同学写出一个自己最想读的书的ISBN号。小明需要去掉其中重复的ISBN号,然后再把这些ISBN号从小到大排序,请你协助小明完成“去重”与“排序”的工作。

输入有2行,第1行为一个正整数,表示有n个同学参与调查(n<=100)。第2行有n个用空格隔开的正整数,为每本书的ISBN号(1~1000)。

输出有2行,第1行为一个正整数k,表示需要买多少本书。第2行为k个用空格隔开的正整数,为从小到大已排好序的需要购买的图书的ISBN号。

程序运行时间限制为1秒。

分析:先将这n个图书的ISBN号去重,再进行从小到大的排序并输出;或者先从小到大进行排序,输出时再去重。

    int a[1001],n,i,t;
    for(i=1;i<=1000;i++)
        a[i]=0;  //初始化
        
    scanf("%d",&n);
    for(i=1;i<=n;i++)  //循环读入n个图书的ISBN号
    {
        scanf("%d",&t);  //把每一个ISBN号读到变量t中
        a[t]=1;  //标记出现过的ISBN号 
    } 
    
    for(i=1;i<=1000;i++)  //依次判断1~1000这个1000个桶
    {
        if(a[i]==1)  //如果这个ISBN出现过就打印出来
            printf("%d ",i); 
    } 
    return 0;
    int a[1001],n,i,j,t;    
    scanf("%d",&n);
    for(i=1;i<=n;i++)  //循环读入n个图书的ISBN号
    {
        scanf("%d",&a[i]);
    } 
    /*开始冒泡程序*/ 
    for(i=1;i<=n-1;i++)
    {
        for(j=1;j<=n-i;j++)
        {
            if(a[j]>a[j+1])
            {
                t=a[j];
                a[j]=a[j+1];
                a[j]=t;
            }
        }
    }
    printf("%d ",a[1]);  //输出第1个数
    for(i=2;i<=n;i++)  //从2循环到n
    {
        if(a[i]!=a[i-1])  //如果当前这个数是第一次出现则输出
            printf("%d ",a[i]); 
    } 
    return 0;

回顾

桶排序是最快的,它的时间复杂度为O(N+M);冒泡排序是O(N2);快速排序是O(NlogN)。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客网2018年全国多校算法寒假训练营练习比赛(第二场)

    Zoctopus
  • C语言中的循环语句练习

    Zoctopus
  • Aizu_Insertion Sort

    Zoctopus
  • JAVA 练习 找出素数

    拾点阳光
  • 程序员进阶之算法练习(七)

    前言 最近来公司面试的开发者很多,经验从1、2年,到5、6年都有,大都不堪重用。 或许在一些程序员眼里,能实现功能,保证上线即可。代码质量,可扩展性,复杂度...

    落影
  • 简单排序

    选择排序降低了交换次数,但是比较次数仍然很多,当数据量比较少,或者基本上有序的时候,使用选择排序。 对于其他情况,应该选择插入排序。

    悠扬前奏
  • 素数(质数)筛选法模板

    echobingo
  • sort algorithm

    选择排序: 5(前) 8 5(后) 2 9 –> 2 8 5(后) 5(前) 9 快速排序: 5 3(前) 3(中) 4 3(后) 8 9 10 ...

    pydata
  • hdu------1281 棋盘游戏(最小覆盖点)

    棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

    Gxjun
  • SID1190471 / 烦人的幻灯片 暴力出奇迹 !!!!!!!!!!!!!!!!!!

    PID221 / 烦人的幻灯片 ☆ 你还木有做过哦 我的状态 查看最后一次评测记录 质量还不能统计出来哦~ 题目评价 质量 无 ★★★★★ ★★★★☆ ★...

    attack

扫码关注云+社区

领取腾讯云代金券