【算法导论】桶排序-阿里云开发者社区

开发者社区> tengweitw> 正文

【算法导论】桶排序

简介: 桶排序 时间复杂度为:O(n) 基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。
+关注继续查看

桶排序

时间复杂度为:O(n)

基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。假设有十个学生的成绩如下:78,17,39,26,72,94,21,12,23,68。我们可以把成绩先进行分段(称为桶),每十分分为一段,共分为10段。然后在每段内进行排序,每一段的排序可以采用插入排序,最后再进行合并即可。各段的内容为:

 桶编号:桶中元素

           0: 

           1:12 、17

           2:21 、23 、26

           3:39

           4:

           5:

           6:68

           7:72 、 78

           8:

           9:94

具体的程序实现如下:

#include<stdio.h>  
#include<malloc.h>  
 
void inc_sort(int arrayA[],int size,int bucket_size);

typedef struct node
{  
    int key;  
    struct node * next;  
}KeyNode;  
  

void main()
{  
    int raw[]={78,17,39,26,72,94,21,12,23,68};   
    int size=sizeof(raw)/sizeof(int);     
    inc_sort(raw,size,10);  
}

/****************************************************\
函数功能:对输入数组进行桶排序
输入:数组及其大小、桶的大小
输出:无
\****************************************************/
void inc_sort(int arrayA[],int size,int bucket_size)
{  
    KeyNode **bucket=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *)); //指向指针的指针,bucket相当于二维数组 
    for(int i=0;i<bucket_size;i++)
	{  
        bucket[i]=(KeyNode *)malloc(sizeof(KeyNode));//动态开辟空间  
        bucket[i]->key=0; //初始化桶中的数据  
        bucket[i]->next=NULL;  
    }  

    for(int j=0;j<size;j++)
	{  
        KeyNode *node=(KeyNode *)malloc(sizeof(KeyNode));//创立节点
        node->key=arrayA[j];  
        node->next=NULL;  
       
        int index=arrayA[j]/10; //映射函数计算桶号和散列函数相似    
          
        KeyNode *p=bucket[index];//初始化p成为桶中数据链表的头指针  
        
        if(p->key==0)//当桶中还没有数据   
            bucket[index]->next=node;  
   		else
		{  
            //链表结构的插入排序  
            while((p->next!=NULL)&&(p->next->key<=node->key))//插入的数据大于当前数据时,从头结点开始
                p=p->next;                                   //直到找到大于它的节点为止
            node->next=p->next;  
            p->next=node;        
        } 
		(bucket[index]->key)++;
    }  
    
    for(int i=0;i<bucket_size;i++)  
	{
        for(KeyNode *k=bucket[i]->next; k!=NULL; k=k->next)  
			printf("%d ",k->key); 
	//	printf("\n");
	}
    printf("\n"); 

	free(bucket);//记得释放申请的内存空间
	
}  
  
  

注意:我是在vs2008上运行的,与vc 6.0有点区别,主要是循环体中的循环变量的作用域,出错体现在循环变量的重复定义上。例如:在vs2008或vs2010上,程序为:

#include<stdio.h>
void main()
{
int i=0;
for(int i=0;i<5;i++)
printf("%d ",i);
}

则在VC 6.0上需改为:

#include<stdio.h>
void main()
{
int i=0;
for(i=0;i<5;i++)
printf("%d ",i);
} 



原文:http://blog.csdn.net/tengweitw/article/details/9713333

作者:nineheadedbird


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法导论】选择排序法
选择排序法         选择排序其实是冒泡法的一种改进,其基本思路也是:先确定最小元素,再找次最小元素,最后确定最大元素。         它与冒泡排序的最大区别在于:冒泡排序是只要碰见比它大的元素就交换,而选择排序是直接将元素放在最终的确定位置,从而避免了多次交换过程。
932 0
【算法导论】桶排序
桶排序 时间复杂度为:O(n) 基本思想:将要排列的序列分成n组,每组分别进行排序,然后在合并到一起,这里面有分而治之的思想。实例说明:大家学c语言肯定学过switch-case结构,最常见的题型就是对成绩进行分类,但是这里我们是对其进行排名。
892 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10469 0
【算法导论】合并排序法
       分治法:将原问题划分为n个规模较小而结构与原问题相似的子问题;递归地解决这些子问题,然后再合并其结果,就得到了原问题的解。分治法在每一个递归上都有三个步骤:分解、解决、合并。
778 0
【算法导论】堆排序
        堆排序像合并排序一样,时间复杂度为O(nlogn);像插入排序一样,是一种原地排序(在任何时候只有常数个元素存储在数组外)。         二叉堆的概念:是一种数组对象,可以被视为一棵完全二叉树,树的每一层都是填满的,最后一层可能除外。
785 0
【算法导论】归并排序
1. 分治法:分治模型在每层递归的时都有三个步骤:   a.分解原问题为若干个子问题,这些子问题是原问题的规模较小的实例;   b. 解决这些子问题,递归地求解各子问题的规模足够小,则直接求解;   c. 合并这些子问题的解 成 原问题的解。
1408 0
【算法导论】计数排序
计数排序 比较排序:通过元素间的比较对序列进行排序的算法称为比较排序。 常见的比较排序算法有:冒泡排序法、插入排序法、合并排序法、快速排序法,堆排序法等等。
897 0
【算法导论】插入排序法
插入排序法的时间复杂度为n的平方,对于较小的输入规模来说,插入排序法比合并排序法更快些。在最佳情况下,即输入数组已经排序好,则时间复杂度可表示为n,是一个线性函数;在最差情况下,即输入数组是逆序排列时,时间复杂度为.
897 0
【算法导论】冒泡排序法
冒泡排序法 时间复杂度:O(n*n) 基本思想:从数组最后一个元素开始,依次与前一个元素比较,若比前一个元素小,则与之交换位置,然后再与当前前一个元素比较,直到遇到比它大的元素为止。
1188 0
+关注
tengweitw
所在学校:西电 兴趣爱好:编程、英语,象棋,乒乓球 email:771257840@qq.com
159
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载