快速排序：一种高效的排序算法

前言

排序是最基本和最常用的操作之一。无论是数据处理、搜索优化，还是各种应用程序的内部逻辑，排序算法的选择都直接影响到程序的性能。快速排序（Quick Sort）作为一种典型的分治算法，以其平均时间复杂度 O(n log n) 和优越的实际表现，成为了现代编程中最常用的排序算法之一。本篇博客将详细讲解快速排序。

一、快速排序的基本思想

快速排序采用了分治的策略。基本思想如下：
1.从数组中选择一个“基准元素”（通常选择数组的第一个元素、最后一个元素，或者随机选择一个元素）。
2.将数组分成两部分：小于基准元素的部分和大于基准元素的部分。
3.分别对这两部分继续递归进行排序。
4.最终得到一个有序数组。

二、快速排序的算法步骤

假设我们有一个数组，快速排序的过程如下：

1.选择基准元素：选择一个元素作为基准，通常是数组的第一个元素（或最后一个，或随机选取）。
2.分割过程：对数组进行重新排列，使得所有比基准元素小的元素排在基准元素的左侧，所有比基准元素大的元素排在右侧。
3.递归排序：递归地对基准元素左边和右边的子数组进行排序，直到子数组大小为1。

三、C++实现快速排序

代码展示

#include <iostream>
#include <vector>

using namespace std;

// 分割函数，将数组分成两部分，左边小于基准，右边大于基准
int partition(vector<int>& arr, int low, int high) {
   
    int pivot = arr[high]; // 选择基准元素为最后一个元素
    int i = low - 1; // i指向小于基准的区域的最后一个元素
    
    for (int j = low; j <= high - 1; j++) {
   
        if (arr[j] < pivot) {
   
            i++;
            swap(arr[i], arr[j]); // 将小于基准的元素交换到左边
        }
    }
    swap(arr[i + 1], arr[high]); // 将基准元素放到正确的位置
    return (i +