C++链式基数排序——从键盘输入源代码 |21xrx.com

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

2023-07-13 20:10:51 深夜i -- --

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

C++语言是面向对象的程序设计语言，自20世纪初以来一直发展壮大，成为当前最流行的计算机语言之一。在C++语言中，排序算法发挥着重要的作用，而链式基数排序算法作为其中的一种，是一种高效的排序方法。

链式基数排序算法的实现过程可以分为三个步骤：首先将待排序的数组按照最高位的数字进行排序，然后依次按照次高位、次次高位……进行排序，最后依据最低位的数字进行排序。在排序过程中，我们需要使用链表来存储相同数字的数值，然后将它们合并回原来的数组。

下面是链式基数排序算法的C++实现代码。在这个程序中，我们首先输入待排序数组的长度和要排序的数字个位数，然后从键盘输入待排序的数组元素，最后调用链式基数排序算法进行排序，输出排序后的数组元素。


#include <iostream>
using namespace std;
//链表结构体
struct node {
  int data;
  node *next;
};
//返回数字的第k位
int get_digit(int x, int k) {
  while (--k > 0)
    x /= 10;
  return x % 10;
}
//链式基数排序函数
void radix_sort(node *&head, node *&tail, int k) {
  node *bucket[10], *tail_bucket[10];
  int i, j, digit;
  for (i = 0; i < 10; i++) {
    bucket[i] = tail_bucket[i] = NULL;
  }
  while (head != NULL) {
    digit = get_digit(head->data, k);
    if (bucket[digit] == NULL) {
      bucket[digit] = tail_bucket[digit] = head;
    } else {
      tail_bucket[digit]->next = head;
      tail_bucket[digit] = head;
    }
    head = head->next;
  }
  head = tail = NULL;
  for (i = 0; i < 10; i++) {
    if (bucket[i] != NULL) {
      if (head == NULL) {
        head = bucket[i];
        tail = tail_bucket[i];
      } else {
        tail->next = bucket[i];
        tail = tail_bucket[i];
      }
    }
  }
  if (head != NULL && k > 1) {
    radix_sort(head, tail, k - 1);
  }
}
int main() {
  node *head, *tail, *p;
  int num, digit, i, data;
  head = tail = NULL;
  cout << "请输入待排序数组的长度：";
  cin >> num;
  cout << "请输入要排序的数字位数：";
  cin >> digit;
  cout << "请输入待排序数组元素：";
  for (i = 0; i < num; i++) {
    cin >> data;
    p = new node;
    p->data = data;
    p->next = NULL;
    if (head == NULL)
      head = tail = p;
     else
      tail->next = p;
      tail = p;
    
  }
  radix_sort(head, tail, digit);
  cout << "排序后的数组元素为：";
  p = head;
  while (p != NULL)
    cout << p->data << " ";
    p = p->next;
  
  cout << endl;
  return 0;
}

在实现代码中，我们首先定义了一个链表结构体，表示一个链表节点，其中data表示节点的数值，next表示下一个节点的指针。然后定义了两个函数，get_digit函数是用来获得数字的第k位数字。radix_sort函数则是链式基数排序函数，它使用了桶的思想，将待排序的数组分成10个桶，并且按照每一位数字依次排序。最后，我们在主函数中输入数组数据，调用radix_sort函数，输出排序后的结果。

总的来说，C++链式基数排序算法是一种高效的排序方法，它不仅可以帮助我们提高程序的运行效率，还可以启发我们对于算法复杂度的深入理解。如果你想进一步提升你的C++排序算法技能，那么一定要学习和掌握链式基数排序算法。

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

下一篇: C++语言关键字及其含义详解

评论区

()

相似文章