注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mr.Right

不顾一切的去想,于是我们有了梦想。脚踏实地的去做,于是梦想成了现实。

 
 
 

日志

 
 
关于我

人生一年又一年,只要每年都有所积累,有所成长,都有那么一次自己认为满意的花开时刻就好。即使一时不顺,也要敞开胸怀。生命的荣枯并不是简单的重复,一时的得失不是成败的尺度。花开不是荣耀,而是一个美丽的结束,花谢也不是耻辱,而是一个低调的开始。

网易考拉推荐
GACHA精选

阿英讲桶排序 Bucket Sort -- C语言实现  

2012-08-11 01:21:57|  分类: 编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

桶排序以下列程序进行:

  1. 设置一个定量的阵列当作空桶子。
  2. 寻访序列,并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

 

#include <stdio.h>
#include <stdlib.h>

#define m 15       // 数组array中的数组元素的数值必须比m小,不能等于m


void bucketsort( int *a, int n )   //n是 数组长度

{

    int buckets [m];   // An array of m counters, or buckets  共 m 个buckets, 下标从0...m-1


    for ( int j = 0; j < m; ++j )    // 将各个bucket初始化为0

        buckets[j] = 0;

    for ( int i = 0; i < n; ++i ) //the buckets are used to keep a count of the number of occurrences of each value between 0 and m-1

        ++buckets[a[i]];   // ++buckets[i] 就是给buckets[i]的数值加1

    for ( int i = 0, j = 0; j < m; ++j )  // 依次遍历各个buckets

        for ( int k = buckets[j]; k > 0; --k )  // k > 0保证buckets[j]非空,k是buckets[j]中的计数器,将buckets[j]中的所有数依次输出到a[]中

            a[i++] = j; // 注意buckets[j]中的下标j就是数组元素a[i]

 

}

 

 

int main()
{
    int i;
    int len;
    int array[] = {8, 9, 1, 2, 3, 5, 4, 6, 7, 11, 10, 14};
    len = sizeof( array ) / sizeof( *array );
    printf( "排序前数组序列:\n" );

    for ( i = 0;i < len;i++ )
    {
        printf( "%5d", array[i] );
    }

    bucketsort( array, len );

    printf( "\n排序后数组序列:\n" );

    for ( i = 0;i < len;i++ )
    {
        printf( "%5d", array[i] );
    }

    getchar();
}

 

 

At first, we define the value of m, which means that all the elements we will introduce for the array will have to be lower than m. Next, we make buckets for the size of m, and we make them null and in the end, we add the elements to the proper buckets.

 

If you know the range of the elements, the bucket sort is quite good.

The time complexity of bucket sort is: O(n + m) where: m is the range input values, n is the total number of values in the array. Bucket sort beats all other sorting routines in time complexity. It should only be used when the range of input values is small compared with the number of values. In other words, occasions when there are a lot of repeated values in the input. Bucket sort works by counting the number of instances of each input value throughout the array. It then reconstructs the array from this auxiliary data. This implementation has a configurable input range, and will use the least amount of memory possible.

  评论这张
 
阅读(1694)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016