排序算法—–基数排序_代码007(未授权)

本文介绍: 基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机 (Ta bula t ion Mac hine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的方式可以采用LSD（Le ast sig nifi c ant digital）或MSD（Mos t sig nifi cant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值

前言

#pragma once
#include<stdlib.h>

//数据类型
typedef int Datatype;

//节点
typedef struct node {
	Datatype data;
	struct node* next;
}Lnode;
//队列
typedef struct queue {
	int curnum;
	Lnode* front, * rear;
}Queue;

//队列初始化
void queue_init(Queue* que);
//判空
int isEmpty(Queue q);
//入队列
void enqueue(Queue *que, Datatype data);
//出队列
Lnode* dequeue(Queue* que);
//获取队头元素
Datatype get_headdata(Queue que);

#include"queue.h"
#include<assert.h>

//队列初始化
void queue_init(Queue* que) {
	que->curnum = 0;
	que->front = que->rear = NULL;
}

//创建一个节点
Lnode* create_node(Datatype data) {
	Lnode* node = (Lnode*)malloc(sizeof(Lnode));
	assert(node);
	node->data = data;
	node->next = NULL;
	return node;
}

//判空
int isEmpty(Queue q) {
	return q.curnum == 0;
}

//入队列
void enqueue(Queue *que,Datatype data) {
	Lnode* add = create_node(data);
	if (isEmpty(*que)) {
		que->front = que->rear = add;
		que->curnum++;
	}
	else {
		que->rear->next = add;
		que->rear = add;
		que->curnum++;
	}
}

//出队列
Lnode* dequeue(Queue *que) {
	if (isEmpty(*que))
		return NULL;
	if (que->curnum == 1)
		que->rear = NULL;
	Lnode* de = que->front;
	que->front = de->next;
	que->curnum--;
	return de;
}

//获取队头元素
Datatype get_headdata(Queue que) {
	return que.front->data;
}

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"

void radix_sort(int* arr, int n) {
	Queue que[10];//创建下标为0~9的队列
	for (int i = 0; i < 10; i++) {
		queue_init(&amp;que[i]);//初始化队列
	}
	for (int i = 0; i < n; i++) {
		enqueue(&amp;que[arr[i] % 10], arr[i]);//把数组个位数的数字依次入队
	}
	int k = 0;
	int count = 10;
	while (que[0].curnum != n) {//如果数字里面全部的数据到第0个队列的时候就结束
		for (int i = 0; i < 10; i++) {
			while (!isEmpty(que[i])) {
				Lnode* pop = dequeue(&que[i]);//出队
				arr[k++] = pop->data;//重新放置数组
				//释放空间
				free(pop);
				pop = NULL;
			}
		}

		k = 0;
		
		for (int i = 0; i < n; i++) {
			//除以count取整，此时指向进一位数字，进行入队操作
			int x = arr[i] / count;
			enqueue(&que[x % 10], arr[i]);
		}
		count *= 10;//
	}
}

int main() {
	int array[] = { 123,0, 25,24,6,65,11,43,22,51 ,999 };
	printf("排序前:");
	for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
		printf("%d ", array[i]);
	}
	//基数排序
	radix_sort(array, sizeof(array) / sizeof(int));
	printf("n排序后：");
	for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
		printf("%d ", array[i]);
	}
}