找女朋友——快排

找女朋友

Time Limit: 15MS Memory Limit: 65536KB

Problem Description

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

Input

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

Output

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

Example Input

5

1 3 2 5 4

Example Output

5 4 3 2 1

Hint

 

Author

思路：稳定快排，然后逆序；或者可以自己定义方向

 

代码：

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>int a[1000000];using namespace std;int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}stable_sort(a,a+n);reverse(a,a+n);for(int i=0;i<n-1;i++){cout<<a[i]<<" ";}cout<<a[n-1]<<endl;return 0;}

PS：题中的稳定快排是被人忽略的（可能只有我身边的人），重点是一直习惯了用STL，很多经典的算法源码已经模糊了。。。中毒很深。。。

下面附上快排源码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100000],n;
void quicksort(int l,int r){int i,j,t,temp;if(l>r)return;temp=a[l];  ///temp中存的是基准数i=l;j=r;while(i!=j){while(a[j]>=temp&&i<j)///先从右往左找j--;while(a[i]<=temp&&i<j)///再从左往右找i++;///交换两数的原始数组位置if(i<j){    ///当i和j没有遇到时t=a[i];a[i]=a[j];a[j]=t;}}///将基准数归位a[l]=a[i];a[i]=temp;quicksort(l,i-1);///排序左面的quicksort(i+1,r);///排序右面的return;
}
int main()
{int i,j,n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}quicksort(1,n);for(int i=1;i<=n-1;i++)cout<<a[i]<<" ";cout<<a[n]<<endl;return 0;
}///快排核心是二分思想