第一章 排序

第一节 桶排序

问题:满分为十分,现要把五个同学的分数5分、3分、5分、2分、8分从高到低排序,要如何排?

  • 思路:利用数组 int a [ ] 即可,从0~10开始算起,将分数出现的次数赋值于数组当中。这样以上五个同学a[0]— a[10]的值分别为:
a[0] = 0    不打印            a[6] = 0不打印
a[1] = 0    不打印            a[7] = 0不打印
a[2] = 2    打印2             a[8] = 1 打印1
a[3] = 1    打印1             a[9] = 0不打印
a[4] = 0    不打印            a[10] = 0不打印
a[5] = 2    打印55            a[11] = 0不打印

最终输出“2,3,5,8”的结果

完整的代码:

#include <stdio.h>
int main()
{
    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(j=1;j<a[i];j++)//出现几次就打印几次
    
    get char();get char();
    //这里一个是用来暂停程序,查看输出内容;
    //也可用system pause()来代替;
    return 0;
}

对0~1000的几个数据按照从小到大的顺序排序,注意从大到小则需改成:for(i=1000;i>0;i--)

#include <stdio.h> 
{
    int a [1001],i,j,t;
    for(i=0;i<1001;i++)
       a[i]=0;//初始化为0
       
    for(i=1;i<=1001;i++)//循环计数
    {
        scanf("%d",&t);//把每个数读到变量中去
        a[t]++;//进行计数
    }
    for(j=1;j<=a[i];j++)//出现几次就输出几次
    
    get char();get char();
    return 0;
    
}
  • 关于时间复杂度的问题

以上述例子为准,整个排序算法一共执行了m+n+m+n次,O(m+n+m+n)=O(2*(m+n)),常数可以忽略不计,则最终的时间复杂度为O(m+n),通常写为大写O(M+N)