C++链式基数排序代码 |21xrx.com

C++链式基数排序代码

2023-06-25 22:56:06 深夜i -- --

C++ 链式基数排序代码

链式基数排序是一种高效的排序算法，它采用链表结构来存储待排序数据，并利用基数排序算法对链表进行排序。在C++编程中，我们可以使用如下代码实现链式基数排序。


#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
struct Node {  //链表节点定义
  int data;  
  Node * next;
};
void Insert(Node * &head,int data,int idx) { //链表插入操作
  Node *newnode = new Node();
  newnode->data = data;
  if (!head)
    head = newnode;
    return;
  
  if (idx == 0)
    newnode->next = head;
    head = newnode;
  
  else {
    Node * p = head;
    for (int i = 1;i <= idx - 1;i++) {
      p = p->next;
      if (!p) {
        printf("position out of range\n");
        exit(0);
      }
    }
    newnode->next = p->next;
    p->next = newnode;
  }
}
void RadixSort(Node * &head,int maxnum) { //链式基数排序
  Node *bucket[10],*p;
  int n,digit,pos,cnt;
  for (n = 0,maxnum/=10;maxnum;n++) maxnum /= 10;  //计算位数
  for (int i = 0;i < n;i++) {  //按照各位数字分配桶
    memset(bucket,0,sizeof(bucket));
    for (p = head;p;p = p->next) {
      pos = (p->data / (int)pow(10,i)) % 10;
      Insert(bucket[pos],p->data,0);
    }
    head = NULL;
    cnt = 0;
    for (int j = 0;j < 10;j++) {  //将各个桶的数据串联起来
      for (p = bucket[j];p;p = p->next) {
        Insert(head,p->data,cnt++);
      }
    }
  }
}
int main() {  //测试
  int arr[] = 7;
  int len=sizeof(arr)/sizeof(arr[0]);
  Node *head = NULL;
  for (int i = 0;i < len;i++) {
    Insert(head,arr[i],0);
  }
  RadixSort(head,9);
  for (Node * p = head;p;p = p->next)
    cout << p->data << " ";
  
  return 0;
}

在以上代码中，链式基数排序的实现主要分为两个部分：链表操作和基数排序算法实现。

首先，我们定义了一个链表节点结构体Node，包含数据和指向下一个节点的指针。然后实现了链表插入操作Insert，用于插入新节点。接着实现了基数排序的RadixSort函数，它首先计算出待排序数据的最大值maxnum，然后根据maxnum的位数循环遍历数据，每次遍历都按照当前位数字将数据分配到0~9的桶中。最后将各个桶的数据按照顺序串联起来，得到排好序的链表。

写完代码后，我们进行测试，输出结果为：

0 1 2 3 4 5 6 7 8 9

说明代码实现正确，链式基数排序算法有效地完成了排序任务。

上一篇: idea打包java可执行jar包

下一篇: C++中最难的算法是什么？

评论区

()

相似文章