本文主要是介绍带你深入浅出新面经：十六、十大排序之快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
此为面经第十六谈！关注我，每日带你深入浅出一个新面经。
我们要了解面经要如何“说”！
很重要！很重要！很重要！
我们通常采取总-分-总方式来阐述！（有些知识点，你可以去了解，但是面经并不是需要全部了解的）
码农不易，各位学者学到东西请点赞支持支持！
排序算法部分可以记忆简单过程概述。
开始部分：
总:快速排序算法通过选取一个基准值，将数组分为两个子数组，一个包含小于基准值的元素，另一个包含大于基准值的元素，然后递归地对这两个子数组进行同样的操作，直到整个数组变得有序。
分：
最好时间复杂度就是（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;
}快速排序的过程可以简单概述为以下几个步骤：
-
选择基准值（Pivot）：通常选择数组的第一个元素或其他某种策略确定的元素作为基准值。
-
分区操作：将数组分为两个子区域，左边子区域的所有元素都小于或等于基准值，右边子区域的所有元素都大于或等于基准值。
-
递归排序：对基准值左边和右边的子区域递归地应用快速排序，直到每个子区域只有一个元素或为空。
-
组合结果：由于子区域是独立排序的，合并它们不会改变元素的顺序，因此不需要额外的合并步骤。
总：排序可视化网站（建议打开看着代码来了解）Comparison Sorting Visualization (usfca.edu)
看着排序过程来理解代码实现会更好。
学习链接：https://xxetb.xetslk.com/s/3Kif2D
这篇关于带你深入浅出新面经：十六、十大排序之快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
