P1177 【模板】快速排序

快速排序模板

 1 #include <iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int a[100010],n;
 5 int t[100010];
 6 void msort(int l,int r) {
 7     if(l>=r) return;//序列中只有一个数，一定有序
 8     int mid=(l+r)/2;//让序列分成两部分
 9     msort(l,mid);//让左边有序
10     msort(mid+1,r); //让右边有序
11     //归并：让左右合起来
12     int i=l,j=mid+1,p=l;
13     while(i<=mid&&j<=r) {
14         if(a[i]<=a[j]) {
15             t[p]=a[i];
16             p++;
17             i++;
18         } else {
19             t[p]=a[j];
20             p++;
21             j++;
22         }
23     }
24     while(i<=mid) { //假设左边序列有剩余的数
25         t[p]=a[i];
26         p++;
27         i++;
28     }
29     while(j<=r) { //假设右边序列有剩余的数
30         t[p]=a[j];
31         p++;
32         j++;
33     }
34     for(int i=l;i<=r;i++) a[i]=t[i];
35     return ;
36 }
37 
38 int main() {
39     cin>>n;
40     for(int i=1; i<=n; i++) cin>>a[i];
41     msort(1,n);
42     for(int i=1; i<=n; i++) cout<<a[i]<<' ';
43     return 0;
44 }