前言
本文介绍一种排序算法——快速排序，是常用的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。
一、快速排序简介
快速排序法又称分割交换排序法，是目前公认的较优排序法之一，采用了分而治之的思想。先从数据中找到一个参照值，将其放置在数据中间，把数据集分为两部分，比参照值小的在左边，大的在右边；再以同样的方式分别处理左右侧的数据，直到排序完毕。
快速排序法的实现思路有很多，本文介绍其中一种（我觉得最好理解且最方便实现的）——占坑法。
- 假设第一个数据是参照值，该值备份下来。
- 从后开始找比它小的数值a，并将其放置在第一个数据处，然后再从前开始找比它大的数值b，将其放置在a原先的位置，以此类推，以占坑的方法让数据集动态排序。
- 在此过程中，数据集一直有两个值是一样的。
- 直到前下标和后下标重合时，将备份的参考值替换当前下标的数值，这样就完成了第一轮的分区。
- 同操作分别处理左侧数据集合右侧数据集，可用递归进行。递归完成，排序完毕。
二、算法特点
1）最好情况和平均情况下，时间复杂度为O(nlog2n)；最坏情况下，每次挑中的参照值都是最值，这样时间复杂度为O(n2)。
2）不稳定，假设两个一样的值a=b，a在前b在后，a被选为基准，排完一遍后，a很大可能就跑到b的后面去了。
3）占坑法的空间复杂度是O(1)，别的实现方法可能会增加空间复杂度。
4）快速排序法是目前使用较多的排序算法，也是平均运行速度较快的算法。
三、代码实现
代码实现逻辑：
- 以最左侧数据为基准，并备份为b。
- 占坑法对比数据并替换。
- 当i==j时，将备份的基准值b赋值到data[i]，完成一次分区。
- 对左侧数据和右侧数据分别排序。
- 递归完成，排序结束。
// 快速排序 void QuickSort(vector<int> &data, int left, int right) { // 若左标与右标重合，中断 if (left >= right) return; // i为左标，j为右标，b为基准 int i = left; int j = right; int b = data[i]; // 占坑式替换 while (i < j) { while (data[j] >= b && i < j) j--; data[i] = data[j]; while (data[i] <= b && i < j) i++; data[j] = data[i]; } data[i] = b; QuickSort(data, left, i - 1); QuickSort(data, i + 1, right); }
四、C++示例
#include <iostream> #include <iomanip> #include <vector> #include <string> using namespace std; // 展示当前顺序 void Show(vector<int> data) { size_t size = data.size(); for (size_t i = 0; i < size; ++i) cout << setw(4) << data[i]; cout << endl; } // 快速排序 int Count = 1; void QuickSort(vector<int> &data, int left, int right) { // 若左标与右标重合，中断 if (left >= right) return; // i为左标，j为右标，b为基准 int i = left; int j = right; int b = data[i]; // 占坑式替换 while (i < j) { while (data[j] >= b && i < j) j--; data[i] = data[j]; while (data[i] <= b && i < j) i++; data[j] = data[i]; } data[i] = b; cout << "第" << Count << "次排序结果：\n"; Show(data); Count++; QuickSort(data, left, i - 1); QuickSort(data, i + 1, right); } // 主函数 int main() { vector<int> data = { 9,11,567,0,-2,4,2 }; // 快速排序 cout << "快速排序：\n原始数据：\n"; Show(data); QuickSort(data, 0, data.size() - 1); cout << "排序后结果：\n"; Show(data); system("pause"); return 0; }
效果图：
综上所述，快速排序法是个比较好用的排序法，优点是速度快，缺点就是极端情况下的排序较慢，且不稳定~
如果文章帮助到你了，可以点个赞让我知道，我会很快乐~加油！
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)