快速排序

基本思想

每趟使表的第1个元素放入适当位置（归位），并且左边的元素小于这个元素，右面的元素大于这个元素，我们称这个元素为pivot，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出口）。

快速排序二叉递归树：

正因为是将最左边的元素提取出来当pivot，所以左边都比它小，右边都比它大，继续划分也是如此，因此这个pivot在序列中的位置就已经决定好了，其他的序列继续如此划分，直至最后分到子表长度只有1或0。由于划分是按照整体有序的方式进行的，所以最后得到的序列必然是有序的。
顺带一提，STL的sort的实现原理就是快速排序。因为相比冒泡等时间换空间的算法以及桶排序等空间换时间的算法来说，快排没有严重失衡，得到优化后更是如此，无愧于20世纪十大算法之一。

实现代码

void QuickSort(List &L,int left,int right)
{
    int l=left,r=right;         //记录此时的左边界和右边边
    int temp=L[left];           //记录左边界为pivot
    if(l<r)
    {
      while(l!=r)
      {
        while(l<r&&L[r]>=temp)  //如果右边的元素大于等于pivot则正常
        {
          r--;              //向pivot靠近
        }
        L[l]=L[r];          //若小于pivot，则调整

        while(l<r&&L[l]<=temp)
        {
          l++;
        }
        L[r]=L[l];
      }
      L[l]=temp;    //最终r<l失败，令其为pivot。
      QuickSort(L,left,l-1);    //划分[left,...,l-1]并进行排序
      QuickSort(L,l+1,right);   //划分[l+1,...,right]并进行排序
    }
}

算法复杂度

最好的情况：

选取的pivot正好可以等分序列，每次要处理的序列长度几乎相等，经过次嵌套调用，便可得到长度为1的子表，在递归树的同一级别上，没有两个调用会处理原序列的相同部分（线性），因此每个级别的调用只要O(n)次，因此整个算法的时间复杂度为O(nlogn)。
由嵌套调用次数就可知，递归树深度为logn，那么空间复杂度=O(logn)。