快速排序（Quick  Sort）是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将待排序记录划分成两部分，使得其中一部分记录的关键字比另一部分记录的关键字小;

然后再分别对这两部分记录进行这种排序，直到每个部分为空或只包含一个记录时，整个快速排序结束。

假设待排序的序列为（r［s］，r［s-1］，…，r［t］）。首先任意选取一个记录（通常可选第一个记录r［s］作为基准记录或称为支点），然后重新排列这些记录。将所有关键字较它小的记录都排到它的位置之前，将所有关键字较它大的记录都排到它的位置之后。由此可以将该基准记录所在的位置i作为分界线，将待排序记录序列划分成两个子序列（r［s］，…，r［i-1］）和（r［i+1］，…，r［t］）。这个过程称为一趟快速排序。

一趟快速排序完成后得到前后两个子序列，可再分别对分割后的两个子序列进行快速排序。整个快速排序过程结束。

例如，待排序记录的关键字为:

    42 36 56 78 67 11 27 36

int Partition(int r[],int s,int t)

{

   int i,j,rp;

   i=s;j=t;

   rp=r[s];                         /*基准记录暂存入rp*/

   while(i<j)                       /*从序列的两端交替向中间扫描*/

   {

      while(i<j&&r[j]>=rp) 

         j--;                       /*扫描比基准记录小的位置*/

      r[i]=r[j];                    /*将比基准记录小的记录移到低端*/

      while(i<j&&r[i]<=rp)

         i++;                       /*扫描比基准记录大的位置*/

      r[j]=r[i];                    /*将比基准记录大的记录移到高端*/

   }

   r[i]=rp;                         /*基准记录到位*/

   return i;                        /*返回基准记录位置*/

}

void Qsort(int r[],int s,int t)     /*快速排序递归算法*/

{

   int k;

   if(s<t)                          /*长度大于1*/

   {

      k=Partition(r,s,t);           /*调用一趟快速排序算法将r[s]..r[t]一分为二*/

      Qsort(r,s,k-1);               /*对低端子序列递归排序,k是支点位置*/

      Qsort(r,k+1,t);               /*对高端子序列递归排序*/

   }

}

快速排序的时间复杂度平均为 O（nlog2n），当n较大时， 这种算法是平均速度最快的排序算法，因此称为快速排序。快速排序是一种不稳定的排序方法。