基数排序c语言实现 基于链式

基数排序是一种非比较型整数排序算法，它根据待排序数的位数，从低位到高位逐次排序。在C语言中，我们可以使用链表来实现基数排序，因为链表支持动态分配内存和处理任意大小的数据。

基数排序C语言链式实现的基本步骤如下：

1. **设置计数数组**：为每一位创建一个计数数组，初始化为0，用于统计每个数字在当前位的出现次数。

2. **确定位数**：找到输入数据中的最大数，确定需要排序的位数。

3. **填充计数数组**：遍历每一位，将每个数字对应的计数数组元素加一。

4. **累计计数**：从低位开始，对计数数组进行累加，生成新的链表节点，每个节点包含当前位和该位值的数量。

5. **复制链表**：基于累计计数，将链表元素分配到相应的桶中，形成初步的排序链表。

6. **重复过程**：对于剩余的高位，重复步骤2-5，直到所有位都被处理。

7. **输出排序结果**：最后，将所有链表连接起来，就得到了按位排序后的链表，再按照链表的顺序连接成一个完整的有序序列。

相关问题

链式基数排序 c语言

链式基数排序是一种基于链表的排序算法，用于对数据进行多关键字排序。它的基本思想是将单个关键字拆分成若干项，并将每一项作为一个新的关键字进行排序。对于整数或字符串类型的关键字，可以将其拆分为单个数字或单个字母。

链式基数排序的具体步骤如下：
1. 定义链结构和链队列结构。
2. 初始化带头结点的链队列。
3. 判断带头结点的链队列是否为空，如果为空则说明排序完成。
4. 从最低位的关键字开始，将序列中的数据根据关键字的不同值分配到不同的队列中。
5. 按关键字从小到大（升序）收集起来。
6. 重复上述步骤，直到最高位分配—收集完成，此时序列有序。

下面是一个示例代码的实现：

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

#define MAX_DIGIT 10  // 假设关键字的最大位数为10

// 定义链结构
typedef struct node {
    int data;
    struct node* next;
} Node;

// 定义链队列结构
typedef struct queue {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} Queue;

// 初始化带头结点的链队列
void initQueue(Queue* q) {
    q->front = q->rear = (Node*)malloc(sizeof(Node));
    q->front->next = NULL;
}

// 判断带头结点的链队列是否为空
int isQueueEmpty(Queue* q) {
    return (q->front == q->rear);
}

// 带头结点的链队列入队操作
void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    q->rear->next = newNode;
    q->rear = newNode;
}

// 带头结点的链队列出队操作
int dequeue(Queue* q) {
    if (isQueueEmpty(q)) {
        printf("Error: Queue is empty\n");
        exit(EXIT_FAILURE);
    }
    Node* temp = q->front->next;
    int data = temp->data;
    q->front->next = temp->next;
    if (q->rear == temp) {  // 若删除的是最后一个结点，则修改队尾指针
        q->rear = q->front;
    }
    free(temp);
    return data;
}

// 取关键字的某一位的值
int getDigit(int num, int digit) {
    int i;
    for (i = 0; i < digit; i++) {
        num /= 10;
    }
    return num % 10;
}

// 检索表中最大的值是几位数
int getMaxDigit(int* arr, int length) {
    int maxDigit = 1;
    int i;
    for (i = 1; i < length; i++) {
        if (arr[i > arr[i - 1]) {
            maxDigit = arr[i];
        }
    }
    int digit = 0;
    while (maxDigit) {
        maxDigit /= 10;
        digit++;
    }
    return digit;
}

// 基数排序算法的实现
void radixSort(int* arr, int length) {
    int maxDigit = getMaxDigit(arr, length);
    int i, j, k;
    Queue queues

数据结构基数排序C语言

基数排序是一种非比较排序算法，它根据数据元素的每个位上的值进行排序。下面是基于顺序队列的基数排序的C语言实现：

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

// 定义数据元素的数据结构
typedef struct {
    int key;
} DataType;

// 定义队列的数据结构
typedef struct {
    DataType *data;
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *queue, int size) {
    queue->data = (DataType *)malloc(size * sizeof(DataType));
    queue->front = queue->rear = 0;
}

// 入队操作
void enqueue(Queue *queue, DataType element) {
    queue->data[queue->rear++] = element;
}

// 出队操作
DataType dequeue(Queue *queue) {
    return queue->data[queue->front++];
}

// 判断队列是否为空
int isEmpty(Queue *queue) {
    return queue->front == queue->rear;
}

// 获取关键字的某一位上的值
int getDigit(int number, int digit) {
    int i;
    for (i = 0; i < digit - 1; i++) {
        number /= 10;
    }
    return number % 10;
}

// 基数排序
void radixSort(DataType *data, int size, int digit) {
    int i, j, k;
    Queue *queues = (Queue *)malloc(10 * sizeof(Queue)); // 创建10个队列，用于存放每个位上的数据元素

    // 初始化队列
    for (i = 0; i < 10; i++) {
        initQueue(&queues[i], size);
    }

    // 根据每个位上的值将数据元素入队
    for (i = 1; i <= digit; i++) {
        for (j = 0; j < size; j++) {
            int digitValue = getDigit(data[j].key, i);
            enqueue(&queues[digitValue], data[j]);
        }

        // 将队列中的数据元素按顺序出队，更新原数组
        k = 0;
        for (j = 0; j < 10; j++) {
            while (!isEmpty(&queues[j])) {
                data[k++] = dequeue(&queues[j]);
            }
        }
    }

    // 释放队列的内存空间
    for (i = 0; i < 10; i++) {
        free(queues[i].data);
    }
    free(queues);
}

int main() {
    int size = 10;
    int digit = 3;
    DataType data[] = {{710}, {342}, {45}, {686}, {6}, {841}, {429}, {134}, {68}, {264}};

    radixSort(data, size, digit);

    // 输出排序结果
    for (int i = 0; i < size; i++) {
        printf("%d ", data[i].key);
    }
    printf("\n");

    return 0;
}

运行以上代码，输出结果为：6 45 68 134 264 342 429 686 710 841