首页 > 代码库 > 基数排序LSD_Radix_Sort
基数排序LSD_Radix_Sort
裸基数排序
#include <iostream> using namespace std; struct list_ { int v; int next; }a[1005]; void print(list_ a[],int head) { for (int i = head; i != -1; i = a[i].next) { cout << a[i].v <<" "; } cout << endl; } int LSD_radix_sort(list_ a[],int head,int digit) { int first[10]; int rear[10]; int M = 1; for (int i = 1; i<=digit; i++) { for (int j = 0;j<=9;j++) first [j] = rear [j] = -1; int now = head; /***将数据分配到各个箱子中去***/ while (head!=-1) { int radix = (a[head].v/M) % 10; if (first[radix] == -1) first [radix] = rear [radix] = head; else { a[rear[radix]].next = head; rear[radix] = head; } head = a[head].next; } /***连接各个箱子***/ int ptr = -1; for (int j = 9;j >=0 ; j--) if (first[j] != -1) { a[rear[j]].next = ptr; ptr = first[j]; } head = ptr; print(a,head); M*=10; } return head; } int main () { int n; int digit; cin >>n >> digit; for (int i = 1; i<=n; i++) { cin >> a[i].v; a[i].next = i+1; } a[n].next = -1; int head = LSD_radix_sort(a,1,digit); print(a,head); }
基数排序LSD_Radix_Sort
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。