C++链表排序实现 |21xrx.com

C++链表排序实现

2023-07-01 14:36:19 深夜i -- --

C++ 链表排序实现

C++ 链表是一种动态数据结构，它可以有效地实现插入、删除等操作。但是，当链表中的数据量很大的时候，我们就需要对链表进行排序，以便能够更快地查找、比较数据。下面，我们将介绍如何在 C++ 中实现链表排序。

链表排序方法

1. 冒泡排序法：

冒泡排序法是一种比较容易理解的排序方法，它通过不断比较相邻两个元素的大小，把较大的元素交换到后面，最终实现排序的目的。

2. 快速排序法：

快速排序法是一种比较高效的排序方法，它通过选取一个基准元素，把链表分成两个部分，一部分是小于基准元素的，一部分是大于基准元素的，然后对这两部分分别进行排序，最终把它们合并起来即可。

C++链表排序实现步骤

1. 定义链表结构体，包括数据和指针，定义指向链表头的指针。

2. 使用冒泡排序法或快速排序法对链表进行排序。

3. 定义一个输出链表的函数，遍历整个链表并输出所有值。

C++链表排序实现示例

定义链表结构体：


typedef struct Node {
  int data;
  Node* next;
}Node;
Node* head = nullptr;

插入节点：


void insertNode(int data) {
  Node* newNode = new Node;
  newNode->data = data;
  newNode->next = head;
  head = newNode;
}

冒泡排序：


void bubbleSort() {
  Node* current = head;
  Node* index = nullptr;
  int temp;
  if (head == nullptr)
    return;
  
  else {
    while (current != nullptr) {
      index = current->next;
      while (index != nullptr) {
        if (current->data > index->data)
          temp = current->data;
          current->data = index->data;
          index->data = temp;
        
        index = index->next;
      }
      current = current->next;
    }
  }
}

快速排序：


Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
  Node* pivot = end;
  Node* prev = nullptr, * cur = head, * tail = pivot;
  while (cur != pivot) {
    if (cur->data < pivot->data) {
      if (*newHead == nullptr) {
        *newHead = cur;
      }
      prev = cur;
      cur = cur->next;
    }
    else {
      if (prev)
        prev->next = cur->next;
      
      Node* tmp = cur->next;
      cur->next = nullptr;
      tail->next = cur;
      tail = cur;
      cur = tmp;
    }
  }
  if (*newHead == nullptr) {
    *newHead = pivot;
  }
  *newEnd = tail;
  return pivot;
}
Node* quickSort(Node* head, Node* end) {
  if (!head || head == end)
    return head;
  
  Node* newHead = nullptr, * newEnd = nullptr;
  Node* pivot = partition(head, end, &newHead, &newEnd);
  if (newHead != pivot) {
    Node* tmp = newHead;
    while (tmp->next != pivot)
      tmp = tmp->next;
    
    tmp->next = nullptr;
    newHead = quickSort(newHead, tmp);
    tmp = getTail(newHead);
    tmp->next = pivot;
  }
  pivot->next = quickSort(pivot->next, newEnd);
  return newHead;
}

输出链表：


void printList() {
  Node* node = head;
  while (node != nullptr)
    std::cout << node->data << " ";
    node = node->next;
  
}

最后，我们可以将整个链表实例化并插入一些随机数据，然后调用排序函数和输出函数，即可实现 C++ 链表排序。

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

下一篇: C++排列组合算法实现

评论区

()

相似文章