排序

洛谷一道模版题：https://www.luogu.org/problemnew/show/P1177

归并排序（稳定排序）

每次的操作只针对相邻区间（合并相邻区间），适合与很多数都有序的情况，这符合只需要修改相邻几个数的排布状况的情况，即使和快排的复杂度相同，但是省掉了冗杂无用的操作，是一个极大的改良。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 const int maxn=1e5+5;
 9 int a[maxn],temp[maxn];
10 int n;
11 
12 void MArray(int l,int mid,int r)
13 {
14     int i=l,j=mid+1;
15     int k=0;
16 
17     while(i<=mid && j<=r)
18     {
19         if(a[i]<=a[j]) temp[k++]=a[i++];
20         else temp[k++]=a[j++];
21 
22     }
23     while(i<=mid) temp[k++]=a[i++];
24     while(j<=r) temp[k++]=a[j++];
25 
26     for(int i=0;i<=k-1;i++) a[l+i]=temp[i];//更新原数组,为了下次再利用
27 }
28 
29 void MSort(int l,int r)
30 {
31     if(l<r)
32     {
33         int mid=(l+r)/2;
34         MSort(l,mid);
35         MSort(mid+1,r);
36         MArray(l,mid,r);
37     }
38 }
39 
40 int main()
41 {
42     ios::sync_with_stdio(false); cin.tie(0);
43 
44     cin>>n;
45     for(int i=1;i<=n;i++) cin>>a[i];
46 
47     MSort(1,n);
48 
49     for(int i=1;i<=n-1;i++) cout<<a[i]<<' ';
50     cout<<a[n]<<endl;
51 
52     return 0;
53 }

快速排序（冒泡改进而来，稳定排序）

sort无疑是一个很浪费的算法，sort其实就是快速排序，而快速排序其实就是二分的思想。

因为所谓的快排效率高，是针对随机的数列的。

而一轮比赛下来，有一半人的相对顺序已经确定了，所以快排就没有了优势。（因此，归并排序优势就体现出来了，稳定排序）

  1 //普通快排基础书本写法(虽说基准数选第一个好写,但最坏情况n^2易出现,有的题专门卡这个,所以后面一般优化选中值)
  2 #include <iostream>
  3 #include <string>
  4 #include <algorithm>
  5 #include <cstdio>
  6 #include <cstring>
  7 using namespace std;
  8 const int maxn=1e5+5;
  9 int a[maxn];
 10 int n;
 11 
 12 int Partition(int l,int r)
 13 {
 14     int i=l,j=r;
 15     int temp=a[l];//为了比较,和最后相等时归位
 16     while(i<j)
 17     {
 18         while(i<j && a[j]>=temp) j--;//必须先进行j指针比较!必须>=,当>时4,2,4,5,1死循环
 19         a[i]=a[j];//即使相等也无所谓,和自己交换不影响
 20 
 21         while(i<j && a[i]<=temp) i++;
 22         a[j]=a[i];
 23     }
 24     a[i]=temp;//i,j相等时中轴归位
 25 
 26     return i;
 27 }
 28 
 29 void QSort(int l,int r)
 30 {
 31     if(l<r)
 32     {
 33         int pivotloc=Partition(l,r);//获取中轴位置,并调整顺序将序列一分为二
 34         QSort(l,pivotloc-1);//递归左子序列再一分为二
 35         QSort(pivotloc+1,r);//递归右子序列再一分为二
 36     }
 37 }
 38 
 39 int main()
 40 {
 41     ios::sync_with_stdio(false); cin.tie(0);
 42 
 43     cin>>n;
 44     for(int i=1;i<=n;i++) cin>>a[i];
 45 
 46     QSort(1,n);
 47 
 48     for(int i=1;i<n;i++) cout<<a[i]<<' ';
 49     cout<<a[n]<<endl;
 50 
 51     return 0;
 52 }
 53 //普通快排另一种写法(两个都找到了再交换一样效果)
 54 #include <iostream>
 55 #include <string>
 56 #include <algorithm>
 57 #include <cstdio>
 58 #include <cstring>
 59 using namespace std;
 60 const int maxn=1e5+5;
 61 int a[maxn];
 62 int n;
 63 
 64 int Partition(int l,int r)
 65 {
 66     int i=l,j=r;
 67     int temp=a[l];//为了比较,和最后相等时归位
 68     while(i<j)
 69     {
 70         while(i<j && a[j]>=temp) j--;//必须先进行j指针比较!
 71 
 72         while(i<j && a[i]<=temp) i++;
 73 
 74         swap(a[j],a[i]);
 75     }
 76     a[l]=a[i];//i,j相等时不符合结束回到第一个元素
 77     a[i]=temp;//中轴归位
 78 
 79     return i;
 80 }
 81 
 82 void QSort(int l,int r)
 83 {
 84     if(l<r)
 85     {
 86         int pivotloc=Partition(l,r);//获取中轴位置,并调整顺序将序列一分为二
 87         QSort(l,pivotloc-1);//递归左子序列再一分为二
 88         QSort(pivotloc+1,r);//递归右子序列再一分为二
 89     }
 90 }
 91 
 92 int main()
 93 {
 94     ios::sync_with_stdio(false); cin.tie(0);
 95 
 96     cin>>n;
 97     for(int i=1;i<=n;i++) cin>>a[i];
 98 
 99     QSort(1,n);
100 
101     for(int i=1;i<n;i++) cout<<a[i]<<' ';
102     cout<<a[n]<<endl;
103 
104     return 0;
105 }
106 //优化1:普通快排+三数去中法
107 #include <iostream>
108 #include <string>
109 #include <algorithm>
110 #include <cstdio>
111 #include <cstring>
112 using namespace std;
113 const int maxn=1e5+5;
114 int a[maxn];
115 int n;
116 
117 int Partition(int l,int r)
118 {
119     int i=l,j=r;
120 
121     int m=(l+r)/2;
122     if(a[l]>a[r]) swap(a[l],a[r]);//三数取中法
123     if(a[m]>a[r]) swap(a[m],a[r]);
124     if(a[m]>a[l]) swap(a[m],a[l]);
125 
126     int temp=a[l];//为了比较,和最后相等时归位
127     while(i<j)
128     {
129         while(i<j && a[j]>=temp) j--;//必须先进行j指针比较!
130         a[i]=a[j]
131         while(i<j && a[i]<=temp) i++;
132         a[j]=a[i];
133     }
134     a[i]=temp;//i,j相等时中轴归位
135 
136     return i;
137 }
138 
139 void QSort(int l,int r)
140 {
141     if(l<r)
142     {
143         int pivotloc=Partition(l,r);//获取中轴位置,并调整顺序将序列一分为二
144         QSort(l,pivotloc-1);//递归左子序列再一分为二
145         QSort(pivotloc+1,r);//递归右子序列再一分为二
146     }
147 }
148 
149 int main()
150 {
151     ios::sync_with_stdio(false); cin.tie(0);
152 
153     cin>>n;
154     for(int i=1;i<=n;i++) cin>>a[i];
155 
156     QSort(1,n);
157 
158     for(int i=1;i<n;i++) cout<<a[i]<<' ';
159     cout<<a[n]<<endl;
160 
161     return 0;
162 }
163 //优化2:普通快排+三数去中法+三向切分法(针对大量重复元素!)
164 #include <iostream>
165 #include <string>
166 #include <algorithm>
167 #include <cstdio>
168 #include <cstring>
169 using namespace std;
170 const int maxn=1e5+5;
171 int a[maxn];
172 int n;
173 
174 int Partition(int l,int r)
175 {
176     int i=l,j=r;
177 
178     int m=(l+r)/2;
179     if(a[l]>a[r]) swap(a[l],a[r]);//三数取中法
180     if(a[m]>a[r]) swap(a[m],a[r]);
181     if(a[m]>a[l]) swap(a[m],a[l]);
182 
183     int temp=a[l];//为了比较,和最后相等时归位
184     while(i<j)
185     {                               //为什么不是>=
186         while(i<j && a[j]>temp) j--;//优化关键,>和i++
187         if(i<j)
188         {
189             a[i]=a[j];
190             i++;//为什么要i++?
191         }
192         while(i<j && a[i]<temp) i++;
193         if(i<j)
194         {
195             a[j]=a[i];
196             j--;
197         }
198     }
199     a[i]=temp;//i,j相等时中轴归位
200 
201     return i;
202 }
203 
204 void QSort(int l,int r)
205 {
206     if(l<r)
207     {
208         int pivotloc=Partition(l,r);//获取中轴位置,并调整顺序将序列一分为二
209         QSort(l,pivotloc-1);//递归左子序列再一分为二
210         QSort(pivotloc+1,r);//递归右子序列再一分为二
211     }
212 }
213 
214 int main()
215 {
216     ios::sync_with_stdio(false); cin.tie(0);
217 
218     cin>>n;
219     for(int i=1;i<=n;i++) cin>>a[i];
220 
221     QSort(1,n);
222 
223     for(int i=1;i<n;i++) cout<<a[i]<<' ';
224     cout<<a[n]<<endl;
225 
226     return 0;
227 }

插入排序(基础排序中用最多,当数较少!或基本有序!时,性能是最好的!)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 const int maxn=1e6+5;
 9 int a[maxn];
10 int n;
11 
12 void ISort()
13 {
14     for(int i=2;i<=n;i++)
15     {
16         if(a[i]<a[i-1])//>=有序,直接跳过(减少了比较次数,但交换移动次数没变)
17         {
18             int temp=a[i];
19             a[i]=a[i-1];//直接先移动一个
20 
21             int j;
22             for(j=i-2;a[j]>temp&&j>=1;j--) a[j+1]=a[j];//从后往前找位置(找的同时顺便移了位置),<时找到停下来插入(j>=1防止负数时死循环)
23 
24             a[j+1]=temp;
25         }
26     }
27 }
28 
29 int main()
30 {
31     ios::sync_with_stdio(false); cin.tie(0);
32 
33     cin>>n;
34     for(int i=1;i<=n;i++) cin>>a[i];
35 
36     ISort();
37 
38     for(int i=1;i<=n-1;i++) cout<<a[i]<<' ';
39     cout<<a[n]<<endl;
40 
41     return 0;
42 }

冒泡排序(交换这种思想用得挺多)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 const int maxn=1e6+5;
 9 int a[maxn];
10 int n;
11 
12 void Swap(int &a,int &b)
13 {
14     int t=a;
15     a=b;
16     b=t;
17 }
18 
19 void BSort()
20 {
21     for(int i=1;i<=n-1;i++)//每轮比较之后浮出一个最大的放到后面(只要有,比较后就交换移动)
22     {
23         for(int j=1;j<=n-i;j++)
24         {
25             if(a[j]>a[j+1])
26             {
27                 Swap(a[j],a[j+1]);
28             }
29         }
30     }
31 }
32 
33 int main()
34 {
35     ios::sync_with_stdio(false); cin.tie(0);
36 
37     cin>>n;
38     for(int i=1;i<=n;i++) cin>>a[i];
39 
40     BSort();
41 
42     for(int i=1;i<=n-1;i++) cout<<a[i]<<' ';
43     cout<<a[n]<<endl;
44 
45     return 0;
46 }

选择排序(比较后,有条件选择进行)

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 const int maxn=1e6+5;
 9 int a[maxn];
10 int n;
11 
12 void Swap(int &a,int &b)
13 {
14     int t=a;
15     a=b;
16     b=t;
17 }
18 
19 void SSort()
20 {
21     for(int i=1;i<=n-1;i++)//每轮选出一个最小的放到前面(相比冒泡减少了交换移动次数,但比较次数没变)
22     {
23         int k=i;
24         for(int j=i+1;j<=n;j++) if(a[j]<a[k]) k=j;//循环之后,j是最小值下标
25 
26         Swap(a[i],a[k]);
27     }
28 }
29 
30 int main()
31 {
32     ios::sync_with_stdio(false); cin.tie(0);
33 
34     cin>>n;
35     for(int i=1;i<=n;i++) cin>>a[i];
36 
37     SSort();
38 
39     for(int i=1;i<=n-1;i++) cout<<a[i]<<' ';
40     cout<<a[n]<<endl;
41 
42     return 0;
43 }