P1177 【模板】O（nlogn)级别排序

universehyf

题目描述
利用快速排序算法将读入的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

快排

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

堆排序

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

归并排序

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. }

复制代码