基数排序及C语言实现
基数排序的基本思想是对数字的每一位进行排序,先对个位排序,然后十位,百位……,对每一位进行排序时,要求采用稳定排序算法,比如前面讨论过的计数排序。以一个三位整数为例,过程是这样的:
该算法同样能达到线性复杂度。下面是代码。(好吧,我知道写的很菜……)
#include <stdio.h> #define NUM 10 //数组元素个数 void counting_sort(int a[],int b[],int c[],int atemp[]); int main() { int i; int j; int a[10] = {326,54,512,13,9,71,92,61,53,19}; //input array int atemp[10]; int b[10]; //output array int c[10]; //temp all element are not biger than 10 // 个位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] % 10; counting_sort(atemp,b,c,a); for (i = 0;i < NUM;i++) a[i] = b[i]; // 十位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] / 10 % 10; counting_sort(atemp,b,c,a); for (i = 0;i < NUM;i++) a[i] = b[i]; //百位排序 for (i = 0;i < NUM;i++) atemp[i] = a[i] / 100 % 10; counting_sort(atemp,b,c,a); for (i = 0;i < NUM;i++) printf(" %d ",b[i]); printf("\n"); } //计数排序算法,a为待排序数组(一位数,要和atemp区分开),b为排序好的数组,c为中间数组,atemp为原始数组(包括三位数) void counting_sort(int a[],int b[],int c[],int atemp[]) { int i,j; for (i = 0;i < NUM;i++) c[i] = 0; for (j = 0;j < NUM;j++) c[a[j]] += 1; for (i = 1;i < NUM;i++) c[i] = c[i] + c[i-1]; for (j = 9;j >= 0;j--) { b[c[a[j]] - 1] = atemp[j]; c[a[j]] -= 1; } }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。