C++ 快速排序实现

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

快速排序是一种流行的排序技术，以其时间复杂度和效率而闻名。

历史

快速排序算法由 Tony Hoare 于 1959 年在他的计算机科学论文中开发。它是最高效且广泛使用的排序算法之一。

快速排序的历史可以追溯到计算机科学早期对排序算法的研究。英国计算机科学家 Tony Hoare 开发了快速排序，作为对现有排序算法的更有效替代方案。

Hoare 最初用 Algol 60 编程语言开发了该算法，并于 1961 年在他的题为“Quicksort”的论文中发表。他将该算法描述为一种分治法，利用元素的划分来实现高效排序。

快速排序因其实用性上的简洁性和效率而广受欢迎。它的平均时间复杂度为 O(n log n)，使其在大多数情况下成为最快的排序算法之一。该算法也非常适合大型数据集，并具有良好的缓存性能。

多年来，快速排序经历了各种优化和改进。已经提出了该算法的不同变体，例如随机快速排序和三路划分快速排序，以进一步提高其性能并处理特定场景。

如今，快速排序在实践中被广泛使用，并且通常是许多编程语言和库中排序的默认选择。其高效的特性、易于实现的优点和多功能性使其成为各种应用的流行选择。

C++ 快速排序实现

#include <iostream>
using namespace std;

// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// Partitioning the array and returning the pivot index
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choosing the last element as the pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++;  // Increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// The main function that implements QuickSort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[p] is now at the right place
        int pi = partition(arr, low, high);

        // Separately sort elements before partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: " << endl;
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: " << endl;
    printArray(arr, n);

    return 0;
}

输出

Original array:
64 25 12 22 11
Sorted array:
11 12 22 25 64

说明

swap 函数以两个整数指针 a 和 b 作为参数。它交换 a 和 b 指向的值。
partition 函数以数组 arr、低索引 low 和高索引 high 作为参数。它选择主元元素，通常选择为数组的最后一个元素 (arr[high])。
partition 函数将较小元素的索引 (i) 初始化为 (low - 1)。
然后，它使用变量 j 遍历从低索引到 high - 1 的数组。如果元素 arr[j] 小于或等于主元，则将 i 加 1 并交换 arr[i] 和 arr[j]。
循环结束后，通过将主元与 arr[i + 1] 处的元素交换，将主元放置在其正确的位置。这确保所有小于主元的元素都在其左侧，所有大于主元的元素都在其右侧。
partition 函数返回主元元素的索引。
quickSort 函数是实现快速排序算法的主要递归函数。它以数组 arr、低索引 low 和高索引 high 作为参数。
在 quickSort 函数中，如果 low 索引小于 high 索引，则表示子数组中有一个以上的元素，需要进行划分。
它调用 partition 函数来划分数组并获取主元元素的索引。
然后，它递归地调用 quickSort 对主元之前的子数组（即从 low 到 pi - 1）和主元之后的子数组（即从 pi + 1 到 high）。
递归继续进行，直到每个子数组只包含一个元素。此时，数组已排序。
printArray 函数以数组 arr 和数组大小作为参数。它打印数组的元素。
在 main 函数中，初始化一个带有某些值的数组。使用 printArray 函数打印原始数组，然后调用 quickSort 函数对数组进行排序。最后，再次使用 printArray 打印排序后的数组。

示例

示例 1：使用字符串数组在 C++ 中进行快速排序

#include <iostream>
#include <vector>

using namespace std;

// Function to partition the array into two sub-arrays
// and return the index of the pivot element
int partition(vector<string> &arr, int low, int high) {
    string pivot = arr[high]; // Choose the rightmost element as the pivot
    int i = (low - 1);        // Initialize the index of the smaller element

    for (int j = low; j < high; j++) {
        // If the current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++; // Increment the index of the smaller element
            swap(arr[i], arr[j]);
        }
    }

    // Swap the pivot element with the element at index i+1
    swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// Function to perform Quick Sort
void quickSort(vector<string> &arr, int low, int high) {
    if (low < high) {
        // Find pivot such that elements smaller than pivot are on the left
        // and elements greater than pivot are on the right
        int pi = partition(arr, low, high);

        // Recursively sort the elements before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<string> arr = {"apple", "banana", "cherry", "date", "grape", "fig"};
    int n = arr.size();

    cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "Sorted Array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

输出

Original Array: apple banana cherry date grape fig 
Sorted Array: apple banana cherry date fig grape

说明

包含库：代码包含用于输入/输出和向量的库。
分区函数

partition 接受一个字符串向量 arr 和两个索引 low 和 high。

它选择最右边的元素 (arr[high]) 作为主元。

它将范围 [low, high-1] 中的每个元素与主元进行比较。

如果元素小于或等于主元，则将其移到主元的左侧。

循环结束后，它将主元放置在其正确的位置，较小的元素在左侧，较大的元素在右侧，并返回主元索引。

快速排序函数

quickSort 通过递归选择主元和划分数组来对字符串向量进行排序。

它从由 low 和 high 定义的范围开始。

如果 low 小于 high，则

调用 partition 来查找主元索引 (pi) 并划分数组。

对主元之前和之后的左右子数组递归应用 quickSort。

主函数

初始化一个字符串向量 arr，其中包含未排序的元素。

打印原始数组。

调用 quickSort 对数组进行排序。

打印排序后的数组。

在此示例中，快速排序用于对字符串向量进行排序。partition 和 swap 操作基于字符串比较执行。编译并运行此代码，以查看快速排序如何应用于不同的数据类型。

示例 2：对浮点数数组进行排序

#include <iostream>

void swap(double &a, double &b) {
    double temp = a;
    a = b;
    b = temp;
}

int partition(double arr[], int low, int high) {
    double pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(double arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    double arr[] = {9.1, 7.2, 5.3, 11.4, 2.5, 1.6};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    quickSort(arr, 0, n - 1);

    std::cout << "Sorted Array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出

Original Array: 9.1 7.2 5.3 11.4 2.5 1.6
Sorted Array: 1.6 2.5 5.3 7.2 9.1 11.4

说明

从数组中选择一个主元元素。
重新排列元素，使小于或等于主元的元素在一侧，大于主元的元素在另一侧。
对主元两侧的子数组递归应用快速排序。
当子数组为零个或一个元素时，递归停止。
原始数组在元素相对于主元正确放置时得到排序。
对于划分过程中创建的每个子数组，都会重复此过程。
快速排序是一种高效的、基于比较的排序算法。
平均时间复杂度为 O(n log n)，使其成为最快的通用排序算法之一。
主元选择会影响性能。
快速排序进行原地排序，无需额外内存。
如果主元选择一直很差，则最坏情况时间复杂度为 O(n^2)。
经常用于对大型数据集进行排序。

示例 3：对自定义对象进行排序

#include <iostream>
#include <vector>
#include <algorithm>

class Student {
public:
    std::string name;
    int score;

    Student(std::string n, int s) : name(n), score(s) {}
};

bool compareStudents(const Student &a, const Student &b) {
    return a.score < b.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 72},
        {"Charlie", 94},
        {"David", 68},
        {"Eve", 91}
    };

    std::cout << "Original Students:" << std::endl;
    for (const Student &student : students) {
        std::cout << student.name << " - " << student.score << std::endl;
    }

    std::sort(students.begin(), students.end(), compareStudents);

    std::cout << "Sorted Students (by score):" << std::endl;
    for (const Student &student : students) {
        std::cout << student.name << " - " << student.score << std::endl;
    }

    return 0;
}

输出

Original Students:
Alice - 85
Bob - 72
Charlie - 94
David - 68
Eve - 91

Sorted Students (by score):
David - 68
Bob - 72
Alice - 85
Eve - 91
Charlie - 94

说明

Student 类

定义了一个名为 Student 的自定义类来表示学生。

每个 Student 对象有两个属性：name（字符串）和 score（整数）。

提供了一个构造函数，用于在创建 Student 对象时初始化这些属性。

比较函数

定义了一个名为 compareStudents 的自定义比较函数。

该函数接受两个 Student 对象作为输入，并根据它们的分数属性进行比较。

如果第一个学生的分数小于第二个学生的分数，则返回 true，表示第一个学生在排序顺序中应排在第二个之前。

主函数

在 main 函数中，创建了一个名为 students 的向量。

该向量包含多个 Student 对象，每个对象代表一个具有姓名和分数的学生。

打印原始学生

程序将原始学生列表打印到控制台。

对于 students 向量中的每个学生，它都会显示该学生的姓名和分数。

排序学生

std::sort 函数用于对 students 向量进行排序。

它根据分数以升序重新排列学生。

compareStudents 函数用作比较标准，以确定排序过程中学生的顺序。

打印排序后的学生

排序后，程序再次将学生列表打印到控制台。

这次，它按分数升序显示学生，显示他们的姓名和分数。

总之，此程序演示了如何定义自定义类 (Student)，创建该类的对象，根据特定属性 (score) 对其进行排序，并显示原始和排序后的学生列表。排序使用带有自定义比较函数的 std::sort 函数执行。

在此示例中，我们有一个自定义 Student 类，我们使用快速排序根据分数对 Student 对象向量进行排序。

这些示例演示了快速排序在对不同数据类型和自定义对象进行排序方面的灵活性。您可以根据需要定义适当的比较函数或运算符重载来使快速排序适用于各种数据结构。

快速排序的应用

快速排序是一种流行的排序算法，它通过将数组划分为两个子数组并递归地对它们进行排序来工作。它以其效率而闻名，并广泛用于需要排序的各种应用中。以下是一些快速排序的常见应用

通用排序：快速排序主要用于对元素数组或列表进行排序。它很高效，平均时间复杂度为 O(n log n)。因此，它通常在编程语言和库中用于对数据集合进行排序。
数值分析：快速排序可应用于数值分析，以解决诸如查找中位数、四分位数或其他统计计算等问题。在这种情况下，它可以对大型数据集进行高效排序。
数据库系统：快速排序可用于数据库系统中，以高效地对大量数据进行排序。排序是数据库管理系统中检索或显示排序结果的基本操作。
实现其他算法：快速排序通常用作其他算法中的子例程。例如，它可以作为 MergeSort 等分治算法的一部分，或在 Kruskal 算法等图算法中用于最小生成树。
顺序统计：快速排序可用于查找数组中的第 k 个最小（或最大）元素。通过选择主元并划分数组，可以在不对整个数组进行排序的情况下快速确定第 k 个元素。
文件系统：快速排序适用于文件系统，用于根据名称、大小或其他属性对文件和目录进行排序和组织。它有助于改进文件系统中的搜索和检索操作。
计算生物学：快速排序用于各种生物信息学应用，如 DNA 序列比对、基因组组装或识别相似序列。排序在这些过程中起着至关重要的作用，而快速排序提供了高效的解决方案。
主元选择：快速排序中选择主元的概念应用于数据挖掘、聚类和机器学习算法等各种领域。选择合适的主元可以显著影响这些算法的性能。
语言处理和自然语言处理 (NLP)：快速排序可用于涉及单词、短语或句子排序的语言处理和 NLP 任务。它通常用于文本分析、信息检索和机器翻译等应用程序。

快速排序的优点

效率：快速排序以其高效的平均性能而闻名。它的平均时间复杂度为 O(n log n)，使其成为最快的排序算法之一。在实践中，快速排序通常优于其他排序算法，特别是对于大型数据集。
原地排序：快速排序进行原地排序，这意味着它不需要与输入大小成比例的额外内存。它在原始数组内重新排列元素，减少了对额外空间的需求，使其内存效率更高。
简洁性：算法的概念相对简单易懂，包括划分数组和递归地对子数组进行排序。与更复杂的排序算法相比，快速排序的简洁性使其更易于实现和调试。
良好的平均性能：快速排序的平均性能通常优于许多其他排序算法，如归并排序或堆排序。它非常适合输入数据随机分布或输入规模较大的情况。
尾递归优化：可以通过尾递归优化快速排序，这减少了递归调用期间所需的堆栈空间。这种优化有助于防止堆栈溢出错误，并使快速排序对大型数据集更有效。
缓存效率：由于其顺序内存访问模式，快速排序具有良好的缓存效率。它在利用缓存的现代计算机体系结构上通常表现良好，因为访问附近的内存位置可能更快。
固有的并行性：快速排序可以高效地并行化，允许在多个处理器或线程上并发执行。划分步骤非常适合并行化，使快速排序成为并行计算环境的合适选择。
随机化版本：在划分期间选择随机主元元素可以使快速排序随机化。这有助于避免最坏情况，并确保更平衡的划分，从而提高平均性能并降低退化输入的可能性。

这些优点使快速排序成为许多需要排序的应用的首选。但是，重要的是要注意，在某些情况下，快速排序的最坏情况时间复杂度为 O(n^2)，尽管在实践中这种情况相对罕见。

下一个主题C++ 中的排序算法

← 上一个下一个 →

C++ 快速排序实现

历史

C++ 快速排序实现

示例

示例 1：使用字符串数组在 C++ 中进行快速排序

示例 2：对浮点数数组进行排序

示例 3：对自定义对象进行排序

快速排序的应用

快速排序的优点

联系信息

关注我们

教程

面试题

在线编译器

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++ 快速排序实现

示例

示例 1：使用字符串数组在 C++ 中进行快速排序

示例 2：对浮点数数组进行排序

示例 3：对自定义对象进行排序

快速排序的应用

快速排序的优点

相关帖子

C++ HASHSET

不使用算术、关系或条件运算符设置变量

C++ 自定义排序字符串

C++ ios::rdstate() 函数

C++ 最大圆形子数组和

C++ seekg() 函数

C++ tellp() 函数

C++ 生成斐波那契三角形程序

C++ 命名约定

C++ DES

订阅 Tpoint Tech

联系信息