排序算法总结

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef unsigned long long ULL;
 5 typedef long long LL;
 6 typedef long double LB;
 7 const int INF_INT=0x3f3f3f3f;
 8 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
 9 
10 int num[100000];
11 
12 void unite(int s,int t,int mid)
13 {
14     int n=t-s+1;
15     int temp[n];
16     int i=s,j=mid+1,k=0;
17     while(i<=mid&&j<=t)
18     {
19         if(num[i]<num[j]) temp[k++]=num[i++]; //<代表从小到大排序
20         else temp[k++]=num[j++];
21     }
22     while(i<=mid) temp[k++]=num[i++];
23     while(j<=t) temp[k++]=num[j++];
24     k=0;
25     while(s<=t) num[s++]=temp[k++];
26 }
27 
28 void merge_sort(int s,int t) //这里的[s,t]是闭区间
29 {
30     if(s<t)
31     {
32         int mid=(s+t)/2;
33         merge_sort(s,mid);
34         merge_sort(mid+1,t);
35         unite(s,t,mid);
36     }
37 }
38 
39 int main()
40 {
41 //    freopen("testdata.in","r",stdin);
42 //    freopen("std.out","w",stdout);
43     int n;
44     while(cin>>n)
45     {
46         for(int i=0;i<n;i++) cin>>num[i];
47         merge_sort(0,n-1);
48         cout<<num[0];
49         for(int i=1;i<n;i++) cout<<‘ ‘<<num[i];
50         cout<<endl;
51     }
52     return 0;
53 }

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef unsigned long long ULL;
 5 typedef long long LL;
 6 typedef long double LB;
 7 const int INF_INT=0x3f3f3f3f;
 8 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
 9 
10 int num[100000];
11 
12 void quick_sort(int s,int t) //这里的[s,t]是闭区间
13 {
14     if(s<t)
15     {
16         int k=num[s],l=s,r=t; //以k为基准分两组序列
17         while(l<r) //小的放左边 大的放右边
18         {
19             while(num[r]>=k&&l<r) r--; 
20             num[l]=num[r];
21             while(num[l]<=k&&l<r) l++;
22             num[r]=num[l];
23         }
24         num[l]=k;
25         quick_sort(s,l-1),quick_sort(l+1,t);
26     }
27 }
28 
29 int main()
30 {
31 //    freopen("testdata.in","r",stdin);
32 //    freopen("std.out","w",stdout);
33     int n;
34     while(cin>>n)
35     {
36         for(int i=0;i<n;i++) cin>>num[i];
37         quick_sort(0,n-1);
38         cout<<num[0];
39         for(int i=1;i<n;i++) cout<<‘ ‘<<num[i];
40         cout<<endl;
41     }
42     return 0;
43 }