快速排序

快速排序的思想就是分治法。 选取一个基准元，将数组分割，然后将大于等于该基准元的数放到该数右边，小于等于的数放到左边。

（1）固定的基准元选取，第一个数或最后一个数

#include<stdio.h> void quicksort(int a[1000],int l,int r) { if(l>r) return; int i,j,x,t; i=l,j=r,x=a[l];//a[l]作为基准数，存入x a[l]挖洞 while(i<j) { while(j>i&&a[j]>=x)//从右边查找小于等于基准数的数 j--; a[i]=a[j];//a[j]填洞 while(i<j&&a[i]<=x)//从左边查找大于等于基准数x的数 i++; a[j]=a[i];//a[i]填洞 } a[i]=x;//基准数放入a[i] quicksort(a,l,i-1);//递归继续排序 quicksort(a,i+1,r); } int main() { int a[1000],i,n; while(~scanf("%d",&n)) { for(i=0;i<n;i++) scanf("%d",&a[i]); quicksort(a,0,n-1); for(i=0;i<n;i++) printf("%d ",a[i]); putchar('\n'); } return 0; }

这种方法选取的基准元对于随机数组数组较快

参考：http://www.codeceo.com/article/3-sort-quick-sort-improve.html