[REVIEW] O(nlogn)排序算法集合

quick sort（快速排序） //quick sort #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=100005; int n; int a[mxn]; inline void qsort(int l,int r) { int i=l,j=r,mid=a[(l+r)/2]; while(i<=j) { while(a[i]<mid) i++; while(a[j]>mid) j--; if(i<=j) { swap(a[i],a[j]); i++;j--; } } if(l<j) qsort(l,j); if(i<r) qsort(i,r); } int main() { int i,j; scanf("%d",&n); fo(i,1,n) scanf("%d",&a[i]); qsort(1,n); fo(i,1,n) printf("%d ",a[i]); return 0; }

---

merge sort（归并排序） //merge sort #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=100005; int n; int a[mxn],tmp[mxn]; inline void msort(int l,int r) { if(l>=r) return; int mid=(l+r)/2; int i=l,j=mid+1,cnt=l; msort(l,mid),msort(mid+1,r); while(i<=mid && j<=r) { if(a[i]<a[j]) tmp[cnt++]=a[i++]; else tmp[cnt++]=a[j++]; } while(i<=mid) tmp[cnt++]=a[i++]; while(j<=r) tmp[cnt++]=a[j++]; fo(i,l,r) a[i]=tmp[i]; } int main() { int i,j; scanf("%d",&n); fo(i,1,n) scanf("%d",&a[i]); msort(1,n); fo(i,1,n) printf("%d ",a[i]); return 0; }

---

heap sort（堆排序） //heap sort #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; priority_queue < int, vector <int> , greater <int> > q; const int mxn=100005; int n; int main() { int i,j,x; scanf("%d",&n); fo(i,1,n) { scanf("%d",&x); q.push(x); } fo(i,1,n) { printf("%d ",q.top()); q.pop(); } return 0; }

事实证明…heap sort确实比较慢，也许是因为STL的缘故