快速排序最早由图灵获奖者Tony Hoare设计出来的，被列为20世纪十大算法之一，属于交换排序类。它也是通过不断比较和交换来实现的，只不过它的实现增大了记录比较和移动的距离（相比冒泡排序）。

快速排序的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部分的关键字小，则可分别对这两部分记录继续进行排序，最终达到整个序列有序的目的。

void Qsort(int a[], int low, int high){    int privot;    if(low

Partition函数是程序的关键，它的功能是选取一个关键字，然后使得它的左边的值都比它小，右边的值都比它大，这里称这个关键字为枢轴（privot）。

void swap(int a[], int i, int j){    int temp = a[i];    a[i] = a[j];    a[j] = temp;}//选取（子）序列第一个元素为枢轴int Partition(int a[], int low, int high){    int privotkey=a[low];    while(low
     
      privotkey)        {            high--;        }        swap(a,low,high);//把小记录交换到底段，high指向枢轴        while(low
     

快速排序的平均时间复杂度是O(nlogn)，由于关键字的比较和交换是跳跃进行的，因此，快速排序不是一种稳定的排序方法。

快速排序的优化

1、优化选择枢轴，我们希望选定的枢轴能把序列较为平均的分成两部分，来减少递归深度。所以有了随机选取、三数取中、九数取中等方法。

2、优化不必要的交换，在Partition函数中，swap部分在不断的交换枢轴的位置，其实只需记录枢轴的最终位置，把枢轴值赋予最后的位置即可。

3、优化小数组时的方案，在数组非常小时，递归的效率反而还不如直接插入排序高，可以添加一个判断，保证最大化利用两种排序的优势。

4、优化递归过程，用迭代来替代后一次递归，进而缩短堆栈深度，提高整体性能。

while(low

在实际应用中，C++/Java/Python中都有对快排的实现，可以很方便的进行调用。