快速排序法

快速排序法

算法的大致过程是对于一个无序序列，找到一个 “哨兵数”,将序列中所有比哨兵数小的数字都在哨兵数的左边，所有比哨兵数大的数字都在哨兵数的右边;然后分别对哨兵数左边和右边再使用同样的方法找到新的哨兵数，并再次进行分类，直到集合不可分割为止。
怎么选择哨兵呢?随便选，可以是第一个，可以是中间那个，也可以在序列中随机选择。选择好哨兵，然后从序列左端开始寻找第一个比哨兵大的数字从右边选择第一个比哨兵小的数字，然后交换这两个数，接着继续从左边找到比哨兵大的数字，右边比哨兵小的数字并交换。一直到将序列分为两组，左边序列都不大于哨兵，右边序列都不小于哨兵，就可以分别对左边和右边进行排序。

 

用代码实现：

void qsort (int a[] ,int l, int r)

int i=1,j=r,flag=a[(l+r)/2];
do{
while  (a[i] < flag)i++; //从左找比哨兵大的数

whilе (a[j]> flag)j--; //从右找比哨兵小的数
if(i<=j){//交换
tmp = a[i] ; a[i] =a[j]; a[j] = tmp;

i++;

j--;}

}
while (i <= j) ;

if(1 < j ) qsort (a,l,j) ;
if (i < r)qsort (а,i,r) ;
}