기수 정렬 적용

문제: O (n) 시간 내 에 0 ~ n ^ 3 - 1 구간 의 수 를 정렬 하 는 알고리즘 을 설계 합 니 다.
  이 문 제 는 기수 정렬 의 응용 이 고 통 정렬 에 도 사용 된다 는 것 이다.사고방식 은 다음 과 같다.
   숫자 를 n 진법 으로 표시 할 수 있 습 니 다. 그러면 0 에서 n ^ 3 - 1 의 수 는 n 진법 의 세 자릿수 입 니 다.이렇게 하면 n 개의 통 을 만 들 수 있 고 차석 우선 규칙 에 따라 세 번 정렬 하면 된다.그래서 총 시간 은 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 이기 때 문 입 니 다.이 숫자 들 을 키 [0], 키 [1], 키 [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;
	}
}