华师一附中OI组

标题: P1177 【模板】O（nlogn)级别排序 [打印本页]
作者: universehyf    时间: 2018-9-14 15:47
标题: P1177 【模板】O（nlogn)级别排序
题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式
输入格式：第1行为一个正整数N，第2行包含N个空格隔开的正整数ai​，为你需要进行排序的数，数据保证了Ai​不超过1000000000
输出格式：将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例
输入样例#1：
5
4 2 4 5 1

输出样例#1：1 2 4 4 5

说明
对于20%的数据，有N≤1000；
对于100%的数据，有N≤100000。
作者: universehyf    时间: 2018-9-14 15:48
快排
  1. #include<iostream>
  2. using namespace std;
  3. int a[1000001];
  4. int n;
  5. int temp;
  6. void qs(int l,int r)
  7. {
  8.     int i,j,mid;
  9.     i=l;j=r;
  10.     mid=a[(l+r)/2];
  11.     do
  12.     {
  13.         while(a[i]<mid) i++;
  14.         while(a[j]>mid) j--;
  15.         if(i<=j)
  16.         {
  17.             temp=a[i];a[i]=a[j];a[j]=temp;
  18.             i++;j--;
  19.         }
  20.     }while(i<=j);
  21.     if(l<j) qs(l,j);
  22.     if(i<r) qs(i,r);
  23. }
  24. int main()
  25. {
  26.     cin>>n;
  27.     for(int i=0;i<n;i++) cin>>a[i];
  28.     qs(0,n-1);
  29.     for(int i=0;i<n;i++) cout<<a[i]<<" ";
  30.     return 0;
  31. }
复制代码
作者: universehyf    时间: 2018-9-14 15:49
堆排序
  1. #include<iostream>
  2. using namespace std;
  3. ///int a[n];
  4. void heap(int *a,int n,int i)
  5. {
  6.     int x=a[i];
  7.     int j=i<<1;
  8.     while(j<=n)
  9.     {
  10.         if(j<n&&a[j]<a[j+1]) j++;
  11.         if(x<a[j])
  12.         {
  13.             a[i]=a[j];
  14.             i=j;j=i<<1;
  15.         }
  16.         else j=n+1;
  17.     }
  18.     a[i]=x;
  19. }
  20. void heapsort(int *a,int n)
  21. {
  22.     for(int i=n;i>=1;i--) heap(a,n,i);
  23.     for(int i=n;i>=2;i--)
  24.     {
  25.         swap(a[1],a[i]);
  26.         heap(a,i-1,1);
  27.     }
  28. }
  29. int a[100010];
  30. int main()
  31. {
  32.     int n;
  33.     cin>>n;
  34.     for(int i=1;i<=n;i++)
  35.         cin>>a[i];
  36.     heapsort(a,n);
  37.     for(int i=1;i<=n;i++)
  38.         cout<<a[i]<<" ";
  39. }
复制代码
作者: universehyf    时间: 2018-9-14 15:49
归并排序
  1. #include<iostream>
  2. using namespace std;
  3. ///int a[n];
  4. void heap(int *a,int n,int i)
  5. {
  6.     int x=a[i];
  7.     int j=i<<1;
  8.     while(j<=n)
  9.     {
  10.         if(j<n&&a[j]<a[j+1]) j++;
  11.         if(x<a[j])
  12.         {
  13.             a[i]=a[j];
  14.             i=j;j=i<<1;
  15.         }
  16.         else j=n+1;
  17.     }
  18.     a[i]=x;
  19. }
  20. void heapsort(int *a,int n)
  21. {
  22.     for(int i=n;i>=1;i--) heap(a,n,i);
  23.     for(int i=n;i>=2;i--)
  24.     {
  25.         swap(a[1],a[i]);
  26.         heap(a,i-1,1);
  27.     }
  28. }
  29. int a[100010];
  30. int main()
  31. {
  32.     int n;
  33.     cin>>n;
  34.     for(int i=1;i<=n;i++)
  35.         cin>>a[i];
  36.     heapsort(a,n);
  37.     for(int i=1;i<=n;i++)
  38.         cout<<a[i]<<" ";
  39. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2