可能是你最容易看明白的快速排序（C++实现） - 好文

我认为现在CSDN大多关于快速排序的程序都是在扯淡。

不是针对某一位，我是说，我看到CSDN的C++快排程序都是扯淡。

他们根本没有把重点放在快速排序本身，为什么我这么说？我们往下看。

快排的本质思想就是分而治之。

举例说明，我们要对3 5 2 1 4进行排序。

首先我们选中一个数字当做是pivot，就是支点啦，然后我们把所有比pivot小的都放在左边，比他大的放在右边。我们这里把数字2当做pivot。

（1） 2 （3 5 4）

ok，就变成了这样，下面我们要怎么样？我们只要对（1）这一部分和（3 5 4）这一部分再用相同的方法排序不就好了？

注意，原来（3 5 2 1 4）是五个数，现在变成了两部分+支点，这就是分而治之的典型思想。

如果用python非常好写，但是我们要用C++就会发生一些问题。不信的话，我们顺着C++的思路向下想——

第一步，我们写个函数叫quicksort，然后想一下，这个递归函数的基线条件是什么？你考虑一下。我们是不是可以用双指针，一个指向排序的头部，一个指向排序的尾部，当头部超过尾部的时候，说明待排序的数组小于等于1了，此时肯定是有序的。废话，[1]这不是有序的吗?一个数字当然有序啊。

第二步，我们找一个pivot，这个简单，双指针/2，二分法的经典做法就行。

第三步，我们把所有比pivot小的都放在前面，大的都放在后面（注意，我在程序里pivot指的是下标，我在文中直接指的是数字大小，在程序中应该是array[pivot]）。就是这一步啊，现在大家的代码都着重于写这玩意儿，这才是你们看的其他人写的快排的时候，理解最困难的地方！

第三步（新），那我就用最简单的办法，新建两个数组，less数组放小的，great数组放大的，一个int叫tmp放pivot。

第四步，把less，tmp和great连接起来。这就是新的data，然后带着新的data和双指针去递归吧！
#include "iostream" #include "vector" #include "algorithm" using namespace
std; //c++实现快速排序 void quicksort(vector<int> &data, int left,int right) { if
(left >= right) return; int pivot = (left+right)/2; vector<int> less;
vector<int> greater; int tmp; for (int i = left; i < right; i++) { if (i ==
pivot) tmp = data[pivot]; else if (data[i] < data[pivot])
less.push_back(data[i]); else greater.push_back(data[i]); } for (int i = left;
i < right; i++) { if (i < left + less.size()) data[i] = less[less.size() - i -
1 + left]; else if (i == left + less.size()) data[i] = tmp, pivot = i; else
data[i] = greater[greater.size() - i+ less.size() + left]; }
quicksort(data,left, pivot); quicksort(data, pivot+1,right); } int main() {
vector<int> data = { 12, 4, 34, 6, 8, 65, 3, 2, 988, 45 }; cout << "排序前："; for
each (auto var in data) { cout << var << " "; } cout << endl; quicksort(data,
0, data.size()); cout << "排序后："; for each (auto var in data) { cout << var << "
" ; } while (1); return 0; }

热门工具换一换