「使用C++实现链式基数排序：从键盘输入源代码」 |21xrx.com

「使用C++实现链式基数排序：从键盘输入源代码」

2023-07-04 22:01:43 深夜i 17 0

C++ 链式基数排序键盘输入源代码

链式基数排序是一种基于比较排序的高效排序算法，在大规模数据排序时具有较高的时间和空间效率。与基数排序不同的是，链式基数排序使用链表来代替数组实现桶。

下面是使用C++实现链式基数排序的源代码，从键盘输入：

#include <iostream>
#include <cstring>
using namespace std;
// 定义一个链表结构体
struct Node {
  int value;
  Node* next;
};
// 插入操作
void insert(Node* & head, int value) {
  Node* node = new Node();
  node->value = value;
  node->next = head;
  head = node;
}
// 输出操作
void print(Node* head) {
  while (head != NULL)
    cout << head->value << " ";
    head = head->next;
  
  cout << endl;
}
// 桶排序
void sort(Node* & head, int radix) {
  Node* buckets[10] = {NULL};
  while (head != NULL) {
    int index = (head->value / radix) % 10;
    insert(buckets[index], head->value);
    head = head->next;
  }
  head = NULL;
  for (int i = 0; i < 10; i++) {
    while (buckets[i] != NULL) {
      Node* node = buckets[i];
      buckets[i] = node->next;
      node->next = head;
      head = node;
    }
  }
}
// 链式基数排序
void radix_sort(Node* & head) {
  int max_value = 0;
  Node* p = head;
  while (p != NULL) {
    max_value = max(max_value, p->value);
    p = p->next;
  }
  for (int radix = 1; radix <= max_value; radix *= 10) {
    sort(head, radix);
  }
}
int main() {
  Node* head = NULL;
  int n, value;
  cout << "请输入排序数据的个数：";
  cin >> n;
  cout << "请输入排序数据：";
  for (int i = 0; i < n; i++) {
    cin >> value;
    insert(head, value);
  }
  radix_sort(head);
  cout << "排序结果为：";
  print(head);
  return 0;
}

在这段代码中，我们首先定义了一个链表结构体，包含一个value值和一个指向下一个结点的指针。然后实现了插入操作和输出操作。

在桶排序中，我们使用桶的数组来存储链表中的数据，然后按照相应的基数将数据插入到对应的桶中。最后再将桶中的数据按照顺序重新连接起来，并更新头结点。

在链式基数排序中，我们根据数据中最大值的位数进行多趟排序。每一趟排序按照相应的基数进行桶排序，最后按照桶连接的顺序将链表重新连接起来。

因为链式基数排序使用了链表来代替数组，所以它的空间利用率更高。同时，链式基数排序的时间复杂度为O(dn)，其中d是数据中最大值的位数，n是数据的个数，比一般的基数排序要快。

使用上面的源代码，我们可以很轻松地实现链式基数排序，并根据自己的需求进行修改和优化。

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

下一篇: 函数的用法和实现原理

评论区

相似文章