基本算法----排序

排序有2种常用方法：

归并排序,快速排序

以下为总结代码(参考)

归并排序

稳定性好

代码难度一般

 1 #include<iostream>
 2 using namespace std;
 3 int n,a[100005];
 4 void qsort(int l,int r)
 5 {
 6     if(l>=r) return ;
 7     int mid=(l+r)>>1;
 8     qsort(l,mid);qsort(mid+1,r);
 9     int k=0,i=l,j=mid+1,t[100005];
10     while(i<=mid&&j<=r)
11     {
12         if(a[i]<a[j])
13         {
14             t[++k]=a[i];i++;
15         }
16         else
17         {
18             t[++k]=a[j];j++;
19         }
20     }
21     while(i<=mid)
22     {
23         t[++k]=a[i];i++;
24     }
25     while(j<=r)
26     {
27         t[++k]=a[j];j++;
28     }
29     for(int i=l,j=1;i<=r;i++,j++)
30     {
31         a[i]=t[j];
32     }
33 }
34 int main()
35 {
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++)
38     {
39         scanf("%d",&a[i]);
40     }
41     qsort(1,n);
42     for(int i=1;i<=n;i++)
43     {
44         printf("%d ",a[i]);
45     }
46     return 0;
47 }

归并 Code

快速排序

稳定性一般

代码难度一般

 1 #include<iostream>
 2 using namespace std;
 3 int n,a[100005];
 4 void qsort(int l,int r)
 5 {
 6     if(l>=r) return ;
 7     int i=l-1,j=r+1;
 8     int mid=a[(l+r)>>1];
 9     while(i<j)
10     {
11         do i++; while(a[i]<mid);
12         do j--; while(a[j]>mid);
13         if(i<j) swap(a[i],a[j]);
14     }
15     qsort(l,j);qsort(j+1,r);
16 }
17 int main()
18 {
19     scanf("%lld",&n);
20     for(int i=1;i<=n;i++)
21     {
22         scanf("%lld",&a[i]);
23     }
24     qsort(1,n);
25     for(int i=1;i<=n;i++)
26     {
27         printf("%lld ",a[i]);
28     }
29     return 0;
30 }

快排 Code

有不足之处可随时评论