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

C++链式基数排序代码

2023-07-11 11:55:03 深夜i -- --

C++ 链式基数排序代码数据结构

C++链式基数排序是一种高效的排序算法，它的实现原理是利用数字的位数进行排序。在这种排序算法中，每个数字都被看作是一个链表节点，数字的位数决定了它在链表中的位置。以下是C++链式基数排序的代码实现。


#include<iostream>
using namespace std;
// 链表节点
struct Node {
  int data;
  Node *next;
};
// 获取数字d在第pos位上的值
int getValue(int d, int pos) {
  int tmp = 1;
  for (int i = 1; i < pos; ++i) {
    tmp *= 10;
  }
  return (d / tmp) % 10;
}
// 链式基数排序
void radixSort(Node *head, int n) {
  int maxNum = 0, digit = 1;
  Node *cur = head;
  // 找到最大的数字，确定循环次数
  while (cur != NULL) {
    maxNum = max(maxNum, cur->data);
    cur = cur->next;
  }
  // 循环n次，按照数字位数进行排序
  while (maxNum / digit > 0) {
    Node *bucket[10] = { NULL };
    // 桶排序
    cur = head;
    while (cur != NULL) {
      int val = getValue(cur->data, digit);
      if (bucket[val] == NULL) {
        bucket[val] = new Node();
        bucket[val]->data = cur->data;
      }
      else {
        Node *node = bucket[val];
        while (node->next != NULL)
          node = node->next;
        
        node->next = new Node();
        node->next->data = cur->data;
      }
      cur = cur->next;
    }
    // 将各个桶合并
    Node *tail = head;
    for (int i = 0; i < 10; ++i) {
      if (bucket[i] != NULL) {
        while (tail->next != NULL)
          tail = tail->next;
        
        tail->next = bucket[i];
      }
    }
    // 将下一位的数字进行排序
    digit *= 10;
  }
}
// 主函数
int main() {
  int n;
  cin >> n;
  // 创建链表
  Node *head = new Node();
  cin >> head->data;
  Node *cur = head;
  for (int i = 1; i < n; ++i) {
    int data;
    cin >> data;
    cur->next = new Node();
    cur = cur->next;
    cur->data = data;
  }
  // 链式基数排序
  radixSort(head, n);
  // 输出结果
  cur = head;
  while (cur != NULL)
    cout << cur->data << " ";
    cur = cur->next;
  
  cout << endl;
  return 0;
}

在这个代码实现中，首先定义了一个链表节点，每个节点包含一个整型数据和一个指向下一个节点的指针。然后通过getValue函数获取数字d在第pos位上的值。接下来，使用radixSort函数进行链式基数排序，其中的桶排序主要是根据数字d在第pos位上的值，将数字放入对应的桶中。然后将各个桶合并，就可以将数字按照当前位数排序。最后，main函数中通过创建链表并使用radixSort函数排序，并输出结果。

C++链式基数排序采用链表的存储方式，具有数据结构的特性，通过桶排序和循环来实现排序，其时间复杂度为O(nk)，是一种简单高效的排序算法。需要注意的是，在使用C++链式基数排序时，需要预估数据规模，避免出现内存溢出等问题。

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

下一篇: Visual C++ 2010无法顺利安装的原因

评论区

()

相似文章