快速排序由C. A. R. Hoare在1960年提出。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
其中一部分的所有数据都比另外一部分的所有数据都要小，
然后再按此方法对这两部分数据分别进行快速排序，
整个排序过程可以递归进行，以此达到整个数据变成有序序列。
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。 [2]
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。 [2]
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 [2]
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。回顾一下快速排序代码：
#include<cstdio>
#include<iostream>
using namespace std;int partition(int a[] , int left , int right) {//保存动态变化的左、右索引位置 int l = left;int r = right;//定义中枢轴 int pivot = a[l]; while(l < r) {while(l < r) {if(a[r] < pivot) {a[l] = a[r]; l++;break;} else {r--;}}while(l < r) {if(a[l] > pivot) {a[r] = a[l]; break;} else {l++;}}}//这个时候l==r a[l] = pivot;return l;
}void quickSort(int a[] , int left , int right) {if(left < right) {int parti = partition(a , left , right);quickSort(a , left , parti-1);quickSort(a , parti+1 , right);}
}
int main() {int a[] = {5,4,7,2,9,1,77};int n = 7;quickSort(a , 0 , n-1);for(int i=0;i<n;i++) cout<<a[i]<<" "; return 0;
}