大部分排序用冒泡可以解决，但是在冒泡排序中双层for循环所有的循环次数不能超过10的8次方，以此运用快排法可较快的解决问题；

以100000个数为例 for(i=1;i<=100000-2;i++) for(j=1;j<=100000-2-i;j++) ｛ .......； ｝ 共需要循环100000*100000次 所以肯定超时；  

找女朋友

Time Limit: 15MS Memory limit: 65536K

题目描述

山东理工大学有很多学生，当然也有很多美女，机械实验班的学委（外号：大王八）很想找个女朋友，但他想找个身高和自己相配的女生坐女朋友，现有理工大N个美女的身高数据，但由于N的值较大，为了尽快找到合适的女友，大王八想请你帮他完成这N个美女的身高排序，按降序排列。

输入

输入包括两行，第一行是一个正整数N（N<=1000000），表示理工大共N个美女。第二行有N个正整数分别表示N位美女的身高，每个正整数的值不会超过10^9。 （输入数据之间会用空格隔开）

输出

输出只有一行，为这N个数的降序序列，数与数之间用空格隔开。

示例输入

5 1 3 2 5 4

示例输出

5 4 3 2 1     快排法 #include #include #define MAX 10000001 int a[MAX];void px(int l,int r); int qp(int l,int r); int main() {  int i,n; scanf("%d",&n);  for(i=1;i<=n;i++)  {   scanf("%d",&a[i]);  }  px(1,n);  for(i=n;i>=1;i--)  {   printf("%d",a[i]);   if(i!=1)printf(" ");   else printf(" ");  }  return 0; } void px(int l,int r) {  if(l>=r)return 0;  int mid=qp(l,r);  px(l,mid-1);  px(mid+1,r); } int qp(int l,int r) {  int bj=a[l];  while(l=a[l]&&l归并法 #include int a[1100001]; int c[1100001]; void hebing(int l,int r,int ll,int rr) { int i=l; int j=ll; int k=l; for(i,j,k;i<=r&&j<=rr;) { if(a[i]=r)return ; int mid=(l+r)/2; paixu(l,mid); paixu(mid+1,r); hebing(l,mid,mid+1,r); } int main() { int i; int n; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } paixu(1,n); for(i=n;i>=1;i--) { printf("%d",a[i]); if(i!=1)printf(" "); else printf(" "); } return 0; }