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

Mr.Right

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

 
 
 

日志

 
 
关于我

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

网易考拉推荐

阿英讲基数排序Radix Sort --C语言实现  

2012-08-11 12:04:55|  分类: 编程 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
基数排序是对桶排序的一种改进,这种改进是让“桶排序”适合于更大的元素值集合的情况,而不是提高性能。它的思想是这样的,比如数值的集合是8位整数,我们很难创建一亿个桶,于是我们先对这些数的个位进行类似桶排序的排序(下文且称作“类桶排序”吧),然后再对这些数的十位进行类桶排序,再就是百位……一共做8次。

将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

Radix sort is a sorting algorithm that sorts the data, integers for example, by splitting the numbers into individual digits and comparing the individual digits sharing the same significant position.

Also, a positional notation is required, because instead of integers there could be strings of characters or floating point numbers.

The radix sort can be classified into 2 types: LSD (least significant digit) or MSD (most significant digit). The LSD sorting type begins from the least significant digit to the most significant digit and the MSD works the other way around.

Note: having the number 150, the number 0 is the least significant digit and 1 is the most significant digit.

Step by step example :

Having the following list, let's try to use radix sort to arrange the numbers from lowest to greatest:

Unsorted list: 12, 8, 92, 7, 100, 500. Because there are numbers with 3 digits, we can write the initial list like this: 012, 008, 092, 007, 100, 500.

Now by using the LSD, the sorting may begin with step 1:

Write all the numbers that have one of the following digit as the LSD of the numbers from the list:

0:100, 500

1:-

2:012, 092

3:-

4:-

5:-

6:-

7:007

8:008

9:-

Also, if you have two numbers with the same digit like 012 and 092, you write them in the order from the list.

Now, the order of the numbers according to step 1 is: 100, 500, 012, 092, 007, 008, which differs a bit from the initial list.

We repeat step 1, but now we use the second digit :

0:100, 500, 007, 008

1:012

2:-

3:-

4:-

5:-

6:-

7:-

8:-

9:092

After step 2, the order is: 100, 500, 007, 008, 012, 092.

Step 3, using the MSB:

0:007, 008, 012, 092

1: 100

2:-

3:-

4:-

5: 500

6:-

7:-

8:-

9:-

The final list is the sorted one: 007, 008, 012, 092, 100, 500.



#include <stdio.h>

#include <stdlib.h>


#define MAX 15     // MAX是buckets的大小,应该至少比array中的最大值大1

#define SHOWPASS

void print(int *a, int n)

{

  int i;

  for (i = 0; i < n; i++)

    printf("%d\t", a[i]);

}

 

void radixsort(int *a, int n)

{

  int i, b[MAX], m = a[0], exp = 1;

  for (i = 0; i < n; i++) //at this for loop, the variable m will store the highest number from the array

  {

    if (a[i] > m)

      m = a[i];

  }

 

  while (m / exp > 0) //at the while loop, the condition is to check if the number still has digits, to see if the number of digits is greater than 0.


  {

/* 

while this is true, a bucket (an array) with maxim 10 storage places (the values from 0 to 9)

will store the proper numbers, just like in the example from above. 

*/

    int bucket[10] ={0}; // 此处bucket是装个位上,或十位上的数用的

    for (i = 0; i < n; i++)  // 先将个位的装入buckets,再十位

      bucket[a[i] / exp % 10]++;

    for (i = 1; i < 10; i++)

      bucket[i] += bucket[i - 1]; //计算偏移量

    for (i = n - 1; i >= 0; i--)  //b是小bucket, 装的是a[]的具体值

      b[--bucket[a[i] / exp % 10]] = a[i];

    for (i = 0; i < n; i++)  // 本次exp对应的小bucket排序结果

      a[i] = b[i];

    exp *= 10;

 

    #ifdef SHOWPASS

      printf("\nPASS:\n ");

      print(a, n);

    #endif

  }

}



 


 


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] );

    }


    radixsort( array, len );


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


    for ( i = 0;i < len;i++ )

    {

        printf( "%5d", array[i] );

    }


    getchar();

}


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

历史上的今天

评论

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

页脚

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