首页 > 代码库 > 数据结构-基数排序
数据结构-基数排序
#include <iostream> using namespace std; void CountSort(int* a,int k,int n){ int s = 1; for(int i=0;i<k;i++){ s *= 10; } int* b = new int[n]; int* c = new int[n]; for(int i=0;i<n;i++){ b[i] = 0; c[i] = 0; } int tmp1 = 0; for(int i=0;i<n;i++){ tmp1 = a[i] % s; tmp1 = tmp1 * 10 / s; b[tmp1] = b[tmp1] + 1; } for(int i=1;i<n;i++){ b[i] = b[i] + b[i-1]; } int tmp2 = 0; for(int i=n-1;i>=0;i--){ tmp1 = a[i]; tmp2 = a[i] % s; tmp2 = tmp2 * 10 / s; c[b[tmp2]-1] = tmp1; b[tmp2] = b[tmp2] - 1; } for(int i=0;i<n;i++){ a[i] = c[i]; } delete[] b; delete[] c; } void RadixSort(int* a,int n){ int max = 0; for(int i=0;i<n;i++){ int length = 2; int tmp = a[i]; while(tmp / 10 != 0){ tmp /= 10; length++; } if(length > max){ max = length; } } for(int i=1;i<=max;i++){ CountSort(a,i,n); } } int main(){ int a[] = {23,1,2032,458,42341,13,551,132446,3212,15}; int n = sizeof(a)/sizeof(*a); RadixSort(a,n); for(size_t i=0;i<n;i++){ cout << a[i] << " "; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。