C++ 单链表上的快速排序

2024 年 8 月 28 日 | 3 分钟阅读

排序是计算机科学中的一个基本操作，而快速排序是其典范。快速排序是一种分而治之的算法，以其效率而闻名。尽管它通常应用于数组，但将快速排序扩展到链表是一项有价值的技能。在本文中，我们将深入探讨 C++ 中单链表上的快速排序实现，提供包含代码、示例和输出的全面指南。

什么是快速排序？

快速排序的本质在于划分数据集并递归地排序子集。该算法指定一个“枢轴”元素，根据其他元素与枢轴的关系将它们分成子数组。快速排序的效率源于其就地排序和在分区过程中同时排序元素的能力。

在单链表上实现快速排序

为了使快速排序适应单链表，需要定义关键函数：一个用于划分列表，另一个用于选择枢轴，以及用于递归排序的主快速排序函数。让我们探索 C++ 代码

代码

#include <iostream>
 
// Node structure for the singly linked list
struct Node {
    int data;
    Node* next;
    
    Node(int value) : data(value), next(nullptr) {}
};
 
// Function to find the last node of the linked list
Node* getTail(Node* head) {
    while (head != nullptr && head->next != nullptr) {
        head = head->next;
    }
    return head;
}
 
// Function to partition the linked list and return the pivot node
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* temp = cur->next;
            cur->next = nullptr;
            tail->next = cur;
            tail = cur;
            cur = temp;
        }
    }
 
    if (*newHead == nullptr)
        *newHead = pivot;
 
    *newEnd = tail;
 
    return pivot;
}
 
// Recursive function to perform QuickSort on the linked list
Node* quickSortRecur(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* temp = newHead;
        while (temp->next != pivot)
            temp = temp->next;
        temp->next = nullptr;
 
        newHead = quickSortRecur(newHead, temp);
 
        temp = getTail(newHead);
        temp->next = pivot;
    }
 
    pivot->next = quickSortRecur(pivot->next, newEnd);
 
    return newHead;
}
 
// Wrapper function for QuickSort on a linked list
void quickSort(Node** headRef) {
    *headRef = quickSortRecur(*headRef, getTail(*headRef));
}
 
// Function to print the linked list
void printList(Node* node) {
    while (node != nullptr) {
        std::cout << node->data << " ";
        node = node->next;
    }
    std::cout << std::endl;
}
 
// Function to add a new node to the linked list
void push(Node** headRef, int newData) {
    Node* newNode = new Node(newData);
    newNode->next = *headRef;
    *headRef = newNode;
}
 
// Driver code
int main() {
    Node* head = nullptr;
 
    // Adding elements to the linked list
    push(&head, 12);
    push(&head, 9);
    push(&head, 15);
    push(&head, 5);
    push(&head, 6);
 
    std::cout << "Linked List before sorting: ";
    printList(head);
 
    quickSort(&head);
 
    std::cout << "Linked List after sorting: ";
    printList(head);
 
    return 0;
}

输出

Linked List before sorting: 12 9 15 5 6
Linked List after sorting: 5 6 9 12 15

结论

总之，将快速排序与 C++ 中的单链表结合使用，丰富了人们对排序算法的理解。在提供的代码中，涉及对指针和递归调用的细致处理的复杂证据突出了快速排序对各种数据结构的适应性。快速排序成为有效排序大型数据集的强大解决方案，其平均时间复杂度为 O(n log n)。

示例场景和结果输出生动地展示了该算法将无序链表无缝转换为有序链表的能力。熟练掌握此类适应性意味着对算法原理有扎实的理解，为开发人员提供了用于有效数据操作的多功能工具。

在计算机科学领域，快速排序保持其突出地位，其对链表的扩展展示了解决各种计算挑战所必需的灵活性。通过深入理解和实现此类算法，开发人员不仅提高了他们的算法熟练程度，而且强调了精简排序策略固有的复杂性和功效。对链表上的快速排序的探索不仅完善了算法技能，而且强调了熟练排序方法中蕴含的优雅和潜力。

下一个主题C++ 中的煎饼排序

C++ 单链表上的快速排序

什么是快速排序？

在单链表上实现快速排序

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 单链表上的快速排序

什么是快速排序？

在单链表上实现快速排序

结论

相关帖子

C++ 吃豆人游戏

C++ New 和 Delete 运算符的区别

C++ 前向列表操作函数

C++ 多线程

C++ thread_local

C++ 中最大化具有唯一元素大小的容器

C++ 直方图绘制程序

C++ 程序检查矩阵是否正交

C++ 集合数组

C++ 程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器