基数排序
2013-01-01 22:05:21 最后更新: 2015-08-06 19:04:38 访问数量：1381
概述
基数排序是在计数排序基础上进行的一种线性时间排序，时间复杂度是O(n)，空间复杂度是O(n*k)
算法思路如下图所示：
是模拟老式穿卡机的排序算法
代码
/*
* file: main.c
* author: 龙泉居士
* date: 2013-01-01 22:05
*/
#include <stdio.h>
#include <malloc.h>
int counting_sort (int *array, int n, int count)
{
if (array == NULL || n<=0 || count <= 0)
{
printf ("counting_sort param error\n");
return -1;
}
int *tmp = (int *)malloc((count+1)*sizeof(int));
if (tmp == NULL)
{
printf ("malloc error\n");
return -1;
}
int i;
for (i=0; i<=count; ++i)
tmp[i] = 0;
for (i=0; i<n; ++i)
tmp[array[i]]++;
for (i=1; i<=count; ++i)
tmp[i] += tmp[i-1];
int *tmparray = (int *)malloc(n*sizeof(int));
for (i=0; i<n; ++i)
{
tmparray[tmp[array[i]]-1] = array[i];
-- tmp[array[i]];
}
for (i=0; i<n; ++i)
array[i] = tmparray[i];
free (tmparray);
free (tmp);
return 0;
}
int main ()
{
int i, n=0, m=0;
int array[256];
printf ("Please input numbers, end by 9999:\n");
while (1)
{
scanf ("%d", &array[n]);
if (array[n] == 9999)
break;
if (array[n] > m)
m = array[n];
++n;
}
if (counting_sort(array, n, m))
return -1;
for (i=0; i!=n; ++i)
printf ("%d ", array[i]);
printf ("\n");
return 0;
}
/*
* file: function.h
* author: 龙泉居士
* date: 2013-01-01 22:18
*/
#ifndef FUNCTION_H_20130101
#define FUNCTION_H_20130101
int counting_sort (int *array, int n, int c);
int radix_sort (int *array, int n, int count);
#endif
/*
* file: function.c
* author: 龙泉居士
* date: 2013-01-01 22:18
*/
#include <stdio.h>
#include <malloc.h>
#include "function.h"
int counting_sort (int *array, int n, int c)
{
if (array == NULL || n<=0 || c <= 0)
{
printf ("counting_sort param error\n");
return -1;
}
int *tmp = (int *)malloc(10*sizeof(int));
if (tmp == NULL)
{
printf ("malloc error\n");
return -1;
}
int i;
for (i=0; i<10; ++i)
tmp[i]=0;
for (i=0; i<n; ++i)
tmp[(array[i]-array[i]/c*c)/(c/10)]++;
for (i=1; i<10; ++i)
tmp[i] += tmp[i-1];
int *tmparray = (int *)malloc(n*sizeof(int));
if (tmparray == NULL)
{
printf ("malloc error\n");
free (tmp);
return -1;
}
for (i=n-1; i>=0; --i)
{
tmparray[tmp[(array[i]-array[i]/c*c)/(c/10)]-1] = array[i];
--tmp[(array[i]-array[i]/c*c)/(c/10)];
}
for (i=0; i<n; ++i)
array[i] = tmparray[i];
free (tmparray);
free (tmp);
return 0;
}
微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤
