快速排序（QuickSort）由C. A. Hoare在1962年提出的一种划分交换排序。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序算法代码如下：
void QuickSort(SeqList R, int low, int high){ //对R[low..high]快速排序 int pivotpos; //划分后的基准记录的位置 if(low<high){ pivotpos=Partition(R, low, high); //对R[low..high]做划分 QuickSort(R, low, pivotpos-1); //对左区间递归排序 QuickSort(R, pivotpos+1, high); //对右区间递归排序 } }//QuickSort int Partition(SeqList R, i, j){ //调用Partition(R, low, high)做划分并返回基准记录的位置 ReceType pivot=R[i]; //用区间的第一个记录作为基准 while(i<j){ //从区间的两端交替向中间扫描，直至i=j为止 while(i<j&&R[j].key>=pivot.key) //pivot相当于在位置i上 j--; //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] if(i<j) //表示找到的R[j]，使R[j]<pivot.key R[i++]=R[j]; //相当于交换R[i]和R[j] 交换后i指针加1 while(i<j&&R[j].key<=pivot.key) //pivot相当于在位置j上 i++; //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] if(i<j) //表示找到的R[i]，使R[j]>pivot.key R[j--]=R[i]; //相当于交换R[i]和R[j] 交换后j指针减1 } R[i]=pivot; //基准位置已被最后定位 return i; //返回基准记录的位置 }快速排序的执行过程： 快速排序执行的全过程可用递归树来描述，如下图所示。
一次划分过程如下图所示。 QuickSort执行时的递归树：
快速排序算法是一种不稳定的排序方法，平均时间复杂度为O(n×lgn/lg2)，最差情况时间复杂度为O(n×n)。
