第一章 排序

第一节 桶排序

问题：满分为十分，现要把五个同学的分数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)