21xrx.com
2024-09-20 00:57:02 Friday
登录
文章检索 我的文章 写文章
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++链式基数排序时，需要预估数据规模，避免出现内存溢出等问题。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复