C++链表排序算法解析 |21xrx.com

C++链表排序算法解析

2023-07-09 20:53:23 深夜i -- --

C++ 链表排序算法解析

链表是一种常见的数据结构，其特点是每个节点都含有数据以及下一个节点的指针。在实际开发中，我们经常需要对链表进行排序。C++语言提供了多种排序算法，本文将解析一些常见的链表排序算法。

1. 冒泡排序

冒泡排序是一种简单的排序算法，其基本思路是反复交换相邻两个节点的位置，直到整个链表排序完成。具体实现代码如下：


void bubbleSort(Node* head) {
  if (!head || !head->next) return;
  for (Node *cur = head; cur->next != nullptr; cur = cur->next) {
    for (Node *pre = head; pre->next != nullptr; pre = pre->next) {
      if (pre->val > pre->next->val)
        int temp = pre->val;
        pre->val = pre->next->val;
        pre->next->val = temp;
      
    }
  }
}

2. 选择排序

选择排序是一种比冒泡排序稍微高效的算法，在选择排序中，我们先记录下链表的最小值，然后将该最小值从链表中移除并插入到已排序的链表的尾部。重复这个操作直到整个链表都排好序。具体实现如下：


void selectSort(ListNode* head) {
  for (ListNode* i = head; i != nullptr; i = i->next) {
    ListNode *minNode = i;
    for (ListNode *j = i->next; j != nullptr; j = j->next) {
      if (j->val < minNode->val)
        minNode = j;
      
    }
    swap(i->val, minNode->val);
  }
}

3. 插入排序

插入排序的基本思想是维护一个已排序的链表，将未排序的元素逐个插入到已排序的链表的正确位置。具体实现如下：


ListNode* insertSort(ListNode* head) {
  if (!head || !head->next) return head;
  ListNode *newHead = new ListNode(-1);
  ListNode *temp = head;
  while (temp) {
    ListNode *next = temp->next;
    ListNode *pre = newHead;
    while (pre->next != nullptr && pre->next->val <= temp->val)
      pre = pre->next;
    
    temp->next = pre->next;
    pre->next = temp;
    temp = next;
  }
  return newHead->next;
}

最后，需要注意的是，在实际开发过程中，我们应该根据具体需求选择最合适的排序算法。只有了解每种算法的特点和适用范围，才能达到高效的排序效果。

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

下一篇: C++中while和for的区别是什么？

评论区

()

相似文章