用C语言实现简单的基数排序
八大排序算法有：冒泡排序、插入排序、选择排序、快速排序、希尔排序、堆排序、归并排序、基数排序。前面七种网上都有很多例子，但是最后一种基数排序却很少看到，所以我总结了一下，并且自己写了一个简单的实现。
基数排序是一种分配排序，其基本思想是：排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性O(n)。基数排序所做的事情，是对N位分别进行排序。从直觉上来看，人们可能会觉得应该首先按最高有效位进行排序，不过这点与我们的直觉相反，基数排序首先对最低有效位数字进行排序。如果我们每次比较r bits，则需要进行b/r趟，每趟进行计数排序需要O(n+2^r)，则总的时间复杂度为O(b/r(n+2^r))。
理论上来说，基数排序的速度是以上几种排序方法中最快的，可以达到O(N)，而其它的排序算法最快也只有O(N*logN)。但是，基数排序需要占用额外的空间，而且只支持整数进行排序。
基数排序的演示可以看这里：基数排序
实现代码如下：
#include
#include /* 获取输入数字的索引值，dec指定数字的位数，3代表百位数，order指定需要获取哪一位的索引，1代表个位，2代表十位，3代表百位 */
int get_index(int num, int dec, int order)
{
int i, j, n;
int index;
int div;
/* 根据位数，循环减去不需要的高位数字 */
for (i=dec;
i>order;
i--) {
n = 1;
for (j=0;
j=0;
i--) {
index = get_index(array[i], dec, order);
/* 从数组尾开始依次获得各个数字的索引 */
j = --num[index];
/* 根据索引计算该数字在按位排序之后在数组中的位置 */
tmp[j] = array[i];
/* 数字放入临时数组 */
}for (i=0;
i 运行结果如下：
baishen@sjtu:~/sort$ ./radix
before
258976515337359701916494303175677825131560147254759814917382452114873585881127819658461435
the 1 time
560701131881461382452303873494254814114515175825585435976916337677147917127258658359759819
the 2 time
701303814114515916917819825127131435337147452254258658359759560461873175976677881382585494
the 3 time
114127131147175254258303337359382435452461494515560585658677701759814819825873881916917976
final
114127131147175254258303337359382435452461494515560585658677701759814819825873881916917976
【用C语言实现简单的基数排序】转载于:https://www.cnblogs.com/compulsive/archive/2011/09/22/2185079.html
推荐阅读
- Docker应用:容器间通信与Mariadb数据库主从复制
- JS中的各种宽高度定义及其应用
- 由浅入深理解AOP
- 【译】20个更有效地使用谷歌搜索的技巧
- 涉毒患者(新诗)
- 参保人员因患病来不及到指定的医疗机构就医，能否报销医疗费用（）
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- mybatisplus如何在xml的连表查询中使用queryWrapper
- MybatisPlus|MybatisPlus LambdaQueryWrapper使用int默认值的坑及解决
- MybatisPlus使用queryWrapper如何实现复杂查询