关于快速排序有很多中写法，对于初学者可能会很疑惑究竟哪种是“标准写法”，事实上只要符合快速排序算法的要求都可以叫做快速排序。而快速排序实际上就是选取一个基准值，将待排序数组按照基准值分为两部分，左边的都小于基准值，右边的都大于基准值，左右两部分分别继续上面的操作，分而治之，从而让整个数组有序。这是快速排序的根本原理，至于在具体实现细节上有各种各样的版本，其实都是做了一些优化。具体来看一下各种版本：
待排序数组：
vector<int> vec = { 2, 3, 2, 3, 4, 1, 5 }; int length = vec.size();//7
（假定我们每次选取最左边的数为基准值）
交换（一）
两个标兵left和right，初始 left 指向 0 的位置，right 指向 length - 1 位置。
先让right往左走（为什么？），走到比基准值小的值的位置，right = 5
再让left往右走，走到比基准值大的值的位置 left = 1
让vec[left] 和 vec[right]交换
交换完成，重复上诉步骤（让right往左走，走到比基准值小的值的位置，left往右走，走到比基准值大的值的位置，交换），直到left == right。
这时将vec[left] 与 基准值交换（vec[left] 一定小于基准值，因为每次都是right先走到小于基准值的位置，right在等left）
完成后基准值左边的都小于基准值，右边的都大于基准值。
之后再对左右部分分别进行上述操作。
实现代码：
void quicksort(int left, int right) { int i, j, t, temp; if (left > right) return; temp = vec[left]; i = left; j = right; while (i != j) { //顺序很重要 while (vec[j] >= temp && i < j) j--; while (vec[i] <= temp && i < j) i++; if (i < j) { t = vec[i]; vec[i] = vec[j]; vec[j] = t; } } vec[left] = vec[i]; vec[i] = temp; quicksort(left, i - 1); quicksort(i + 1, right); return; }
交换（二）
在交换（一）中，我们先让左右标兵走，碰头时再把基准值和碰头位置的值交换。
事实上，我们要做的就是将基准值放在一个正确的位置，使得基准值左边的都小于基准值，基准值右边的都大于基准值。
因此，在交换过程中，我们可以带着基准值走。即当right走到比基准值小的值的位置时，将基准值与right位置所在的值交换，当left走到比基准值大的值的位置时，将基准值与left位置所在的值交换。
void swp(int &a, int &b) { int t = a; a = b; b = t; } void quicksort(int left, int right) { int i, j, temp; if (left > right) return; i = left; j = right; temp = vec[left]; while (i != j) { while (i < j && vec[j] >= temp) j--; swp(vec[i], vec[j]); while (i < j && vec[i] <= temp) i++; swp(vec[i], vec[j]); } quicksort(left, i - 1); quicksort(i + 1, right); return; }
挖坑
试想，如果我们每次把基准值保存在一个临时变量中，是不是也就意味着数组中空出来一个位置（因为这个位置的值已经保存到临时变量中，我们想恢复整个数组随时可以恢复）
因此当以最左边的值为基准值时，将该值保存到临时变量中，最左边的值也就空出来了，这样当right找到比基准值小的值时，直接将该值放入空位置，这样right所指的位置又空了出来，等待left找到比基准值大的值放入。这样当left和right碰头时，也正是空位置的值，也正是基准值该待的位置。（这里说的空位置，并不是实际的没有数据，而是这个位置的数据已经有了拷贝，所以位置的值可以覆盖，和空位置的效果一样）
void quicksort(int l, int r) { int left = l; int right = r; if (left > right) return; int tmp = vec[l]; while (left < right) { while (left < right && vec[right] >= tmp) right--; if (left < right) vec[left++] = vec[right]; while (left < right && vec[left] <= tmp) left++; if (left < right) vec[right--] = vec[left]; } vec[left] = tmp; quicksort(l, left - 1); quicksort(left + 1, r); }
以上便是几种快速排序朴素的实现方式。
之所以说朴素是因为算法只是按照快排的概念而写，优化的力度不大。
比如：
在上面的实现中，我们每次都以最左边的值作为基准值，但是对于下面这组数据，试想会怎么样？
vector<int> vec = { 1, 2, 3, 4, 5, 6, 7 };
基准值为整个数组的极小值，在right向左找的比 1 小的元素时需要遍历整个数组，如果数组很长，可见效率是很低的，时间复杂度可能退化到O(n^2)。因此，快速排序中基准值的选取也是有讲究的，因为选取一个好的基准值，每次大致可以将数组对半分，从而达到O(logn)级别。
因此，为了避免选取到数组的极值，我们可以选取数组中左、中、右三个数的中值作为基准值，也就是三数取中法
int temp; int m = left+ (right - left) / 2; //让vec[right]为最大值 if (vec[left] > vec[right]) swp(vec[left], vec[right]); if (vec[m] > vec[right]) swp(vec[m], vec[right]); //让vec[left]为第二大值 if (vec[m] > vec[left]) swp(vec[m], vec[left]); temp = vec[left];
经过交换后最左边的值至少不会是数组的极值，因此效率不会降到最低。
还有一种优化是尾递归的优化
void quicksort(int l, int r) { while (l < r) { int left = l, right = r, tmp = vec[l]; while (left < right) { while (left < right && vec[right] >= tmp) right--; if (left < right) vec[left++] = vec[right]; while (left < right && vec[left] <= tmp) left++; if (left < right) vec[right--] = vec[left]; } vec[left] = tmp; quicksort(l, left - 1); l = left + 1; } }
多加一层循环while (l < r)，左半部分采用递归，右半部分循环迭代，避免过多的开辟栈空间，在空间上进行了优化。
![现有一个接口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)