带你深入浅出新面经：十六、十大排序之快速排序

本文主要是介绍带你深入浅出新面经：十六、十大排序之快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此为面经第十六谈！关注我，每日带你深入浅出一个新面经。

我们要了解面经要如何“说”！

很重要！很重要！很重要！

我们通常采取总-分-总方式来阐述！（有些知识点，你可以去了解，但是面经并不是需要全部了解的）

码农不易，各位学者学到东西请点赞支持支持！

排序算法部分可以记忆简单过程概述。

开始部分：

总:快速排序算法通过选取一个基准值，将数组分为两个子数组，一个包含小于基准值的元素，另一个包含大于基准值的元素，然后递归地对这两个子数组进行同样的操作，直到整个数组变得有序。

分：

最好时间复杂度就是（nlogn）

最差时间复杂度就是（n²）

平均时间复杂度也是（nlogn）

空间复杂度：nlogn

稳定性：不稳定。

#include <iostream>
#include <vector>
#include <algorithm> // 引入algorithm库，用于swap函数using namespace std;// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {int pivot = arr[low]; // 选择基准值，这里选择数组第一个元素int i = low; // i作为小于pivot的区域的指示器int j = high + 1; // j作为大于pivot的区域的指示器// 使用循环进行分区操作while (true) {// 从左向右找到第一个大于等于pivot的元素，大于才能跳出循环while (arr[++i] < pivot);// 从右向左找到第一个小于等于pivot的元素，小于才能跳出循环while (arr[--j] > pivot && j > low);// 如果i和j没有相遇，交换它们所指向的元素if (i < j) {swap(arr[i], arr[j]);} else {break; // 如果i和j相遇，跳出循环}}// 将基准值放到正确的位置，即i和j相遇的位置swap(arr[low], arr[j]);return j; // 返回基准值的索引
}// 快速排序的递归函数
void quickSort(vector<int>& 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() {vector<int> arr = {10, 7, 8, 9, 1, 5};cout << "Original array: ";for (int num : arr) cout << num << " ";cout << endl;quickSort(arr, 0, arr.size() - 1); // 调用快速排序函数cout << "Sorted array: ";for (int num : arr) cout << num << " ";cout << endl;return 0;
}

快速排序的过程可以简单概述为以下几个步骤：