【基数排序应用】问题：设计一个算法在O(n)时间内，对0到n^3-1区间内的数进行排序。
此问题是基数排序的应用，也用到了桶排序。思路如下：
可以将数字用n进制表示，那么0到n^3-1中的数最多是n进制的三位数。这样可以建立n个桶按照次位优先的规则排序3次即可。所以总时间是O(n+n+n)=O(n);
例如当n=4时，n^3-1=63，有4个数的数列为54,2,63,15;
在排序时首先用4进制表示该数。如54表示为4进制的关键字为key[0]=2,key[1]=1,key[2]=3,因为54=2+1*4+3*4^2;
将这些数字依次按照key[0],key[1],key[2]排序即可得到结果，以下代码用n=5来测试，
#include
using namespace std;
class Node{
public:
int key[3];
Node*next;
};
typedef Node*PNode;
PNode conver(int a[], int n);
PNode Radix_sort(PNode head, int n);
void Show_Node(PNode head,int n);
int main(){
const int n =5;
int a[n] = { 89,120,45,1,56 };
PNode head = conver(a,n);
head = Radix_sort(head, n);
Show_Node(head,n);
return 0;
}
PNode conver(int a[], int n){//关键字分解，使其串为链表
PNode head=new Node;
//作用为空头结点
PNode p = head,p1=head;
int i;
for (i = 0;
i < n;
i++){
p = new Node;
p->key[0] = a[i] % n;
p->key[1] = a[i] / n%n;
p->key[2] = a[i] / n / n%n;
p1->next = p;
p1 = p1->next;
}
p1->next = nullptr;
p = head;
head = head->next;
delete p;
return head;
}
PNode Radix_sort(PNode head,int n){
int i, j;
PNode *Bucket= new PNode[n];
//建立n个桶，记录n个桶首元素位置
PNode *Rear = new PNode[n];
//记录每个桶末尾元素位置
for (i = 0;
i < 3;
i++){;
for (j = 0;
j < n;
j++)
Bucket[j]= Rear[j] =nullptr;
while (head){
if (Bucket[head->key[i]]){//桶若不空
Rear[head->key[i]]->next = head;
Rear[head->key[i]] = Rear[head->key[i]]->next;
}
else
Bucket[head->key[i]] = Rear[head->key[i]]=head;
head = head->next;
}
j = 0;
while (!Bucket[j]) j++;
//找到头结点
head = Bucket[j];
PNode rear = Rear[j];
for (j = j + 1;
j < n;
j++){//将桶中节点串接起来
if (Bucket[j]){
rear->next = Bucket[j];
rear = Rear[j];
}
}
rear->next = nullptr;
//未结点指向空非常重要
}
return head;
}
void Show_Node(PNode head,int n){//显示链表结果
while (head){
cout << head->key[0] + head->key[1] * n + head->key[2] * n*n << " ";
head = head->next;
}
} 推荐阅读
- 集合的全排列（Java实现）
- 算法导论学习笔记——2.3.1分治法——习题2-4逆序对数
- 拓展欧几里得算法详解
- 算法导论程序15-计数排序（Python）
- 算法导论 — 8.3 基数排序
- 算法导论程序16--基数排序（Python）
- 算法导论 基数排序
- RSA模重复平方算法小示例
- 【算法导论之四】计数排序
- 算法导论计数排序实现