前言
说到快速排序，在学数据结构的时候都已经学到了，不过当时总是有些云里雾里的，就算是照着书上的代码敲出来，也不是很明白是什么意思。后来在大三上学期的时候又接触到了快速排序，虽然实现的方法不一样。数据结构将的时候右边和右边一起向中间靠近，而算法导论将的是从做往右靠近，其实大概的思路都是差不多的。这里不想说一些时间复杂度，算法分析什么的，网上的资料很多，也不班门弄斧了。只是把自己的一点理解写出来，也许有后来的新手对于快速排序有相同的一点疑问，而且恰好看到我这偏文章并得以解惑，那就很是不错了。
分析
快速排序主要的思想就是在待排序的数组中取一个数字作为标兵，暂且就这么理解了。然后以这个标兵为界，把比标兵小的放在标兵的左边，把比标兵大的放在标兵的右边，这样我们可以知道不管左边或者右边的是怎么样，但是这个标兵已经处于排好序的数组中的正确的位置了。当然这是升序排序，降序也是一样的道理，思想就是这么简单。但是这个数字怎么取，取哪一个，然后怎么实现标兵的左边大，右边小，这就是重点所在了。最理想的情况当然是每次取到最中间大小的那个数，因为这样的话每次两边都刚好可以分到一半；而最坏的情况就是取到最大或者最小的，这样每次标兵虽然在正确的位置，但会存在一边没有元素，而另一边则是剩下的所有元素，这已经退化为插入排序了。所以为了尽量得到好的标兵，优化的快速排序算法有三数取中快速排序，随机化的快速排序，随机化三数取中快速排序等。三数取中指的是从数组的开头、结尾、中间的中取一个中间大小的数作为标兵，这样取出的数很可能靠近最优标兵；而随机化指的是随机从数组取出一个数作为标兵；而随机化三数取中则是前面两种算法的集中。
partition
为什么要一直说这个标兵呢？标兵为什么这么重要？那就不得不说快速排序的最重要的操作partition了。 partition接受一个待排序的数组作为参数，返回标兵的正确位置。另外，这里的一个编程技巧是将标兵移到最后一个位置，这样在遍历数组的过程中便于交换。完整的partition函数如下：
/**
* @param A 传入的数组
* @param l 最左边位置
* @param r 最右边位置
* @return 标兵的位置
*/
int partition(int A[], int l, int r) {
//最后一个元素
int x = A[r];
int i = l - 1;
for (int j = l; j < r; j++) {
//如果不大于最后一个元素，就放在i的左边，并且i的位置加1
if (A[j] <= x) {
i++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
//交换i位置与最后位置的元素，这样i的左边的元素都小于A[i]，右边的元素都大于A[i]
int temp = A[i + 1];
A[i + 1] = A[r];
A[r] = temp;
//返回标兵的位置
return i + 1;
}
完整的代码
#include <iostream>
using namespace std;
void quick_sort(int A[], int p, int r);
int partition(int A[], int l, int r);
void print(int A[], int length);
int main(int argc, char const *argv[]) {
int length;
cout << "请输入待排序的个数：";
cin >> length;
int A[length];
cout << "请输入排序的数字，以空格分开：";
for (int i = 0; i < length; ++i) {
cin >> A[i];
}
quick_sort(A, 0, length - 1);
print(A, length);
return 0;
}
/**
* @param A 传入的数组
* @param l 最左边位置
* @param r 最右边位置
* @return 标兵的位置
*/
int partition(int A[], int l, int r) {
//最后一个元素
int x = A[r];
int i = l - 1;
for (int j = l; j < r; j++) {
//如果不大于最后一个元素，就放在i的左边，并且i的位置加1
if (A[j] <= x) {
i++;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
//交换i位置与最后位置的元素，这样i的左边的元素都小于A[i]，右边的元素都大于A[i]
int temp = A[i + 1];
A[i + 1] = A[r];
A[r] = temp;
//返回标兵的位置
return i + 1;
}
void print(int *A, int length) {
for (int i = 0; i < length; i++) {
cout << A[i] << " ";
}
cout << endl;
}
void quick_sort(int A[], int p, int r) {
if (p < r) {
//q即是标兵的正确位置
int q = partition(A, p, r);
//对左边部分继续调用quick_sort
quick_sort(A, p, q - 1);
//对右边部分继续调用quick_sort
quick_sort(A, q + 1, r);
}
}
结语
算法一道真的是博大精深，作为一个计算机专业的，我的算法其实也是很差，比较汗颜。回想刚接触这个专业时什么都不懂，到现在更是觉得学海无涯。有道是一入IT深似海，从此妹纸是路人，咳，不是，从此青春是路人。且行且学习吧。
