基数排序

2013-01-01 22:05:21   最后更新: 2015-08-06 19:04:38   访问数量:764




基数排序是在计数排序基础上进行的一种线性时间排序,时间复杂度是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; }

 

 






读书笔记      技术帖      算法      算法导论      数据结构      龙潭书斋      排序      sort      计数排序      基数排序      radixsort      radix     


京ICP备15018585号