链式基数排序是一种按照数字的每一位进行排序的算法，它适用于对大量的数字进行排序。在C++中，可以通过以下代码实现链式基数排序。

#include <iostream>
using namespace std;
struct Node { //定义链表结构体
  int data;
  Node* next;
};
void radixSort(int arr[], int n) {
  Node* bucket[10]; //定义10个桶
  for (int i = 0; i < 10; i++) {
    bucket[i] = new Node(); //每个桶都初始化一个头节点
  }
  int exp = 1; //指数，初始值设为1
  int maxVal = arr[0]; //最大值，初始值设为第一个元素
  for (int i = 1; i < n; i++) { //找到最大值
    if (arr[i] > maxVal) {
      maxVal = arr[i];
    }
  }
  while (maxVal / exp > 0) //按照每一位进行排序，直到最后一位
  {
    for (int i = 0; i < 10; i++) { //清空桶
      bucket[i]->next = NULL;
    }
    for (int i = 0; i < n; i++) { //将元素分配到对应的桶中
      int digit = (arr[i] / exp) % 10;
      Node* newNode = new Node();
      newNode->data = arr[i];
      if (bucket[digit]->next == NULL) {
        bucket[digit]->next = newNode;
      } else { //如果桶中已经有其他元素
        Node* p = bucket[digit]->next;
        Node* q = bucket[digit];
        while (p != NULL && p->data < arr[i]) //寻找插入位置
          q = p;
          p = p->next;
        
        if (p == NULL) //插入到链表末尾
          q->next = newNode;
         else //插入到链表中间
          newNode->next = p;
          q->next = newNode;
        
      }
    }
    int j = 0; //将排好序的元素拷贝回原数组
    for (int i = 0; i < 10; i++) {
      Node* p = bucket[i]->next;
      while (p != NULL) {
        arr[j++] = p->data;
        p = p->next;
      }
    }
    exp *= 10; //指数增加一位
  }
}
int main() {
  int arr[] = 3;
  int n = sizeof(arr) / sizeof(arr[0]);
  radixSort(arr, n);
  for (int i = 0; i < n; i++) { //输出排好序的数组
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}

在该代码中，通过定义一个链表结构体实现了链式基数排序。桶的数量为10，每个桶都初始化一个头节点，用于存放对应的元素。在按照每一位进行排序时，首先将所有桶清空，然后将元素分配到对应的桶中。如果桶中已经有元素，那么就按照从小到大的顺序插入到链表中，并拷贝排好序的元素回原数组。根据指数的增加，重复以上操作直到最后一位排好序。最后，输出排好序的数组。

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

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政