呵呵，这几天复习排序算法，gsb童鞋给我们找了几道题做，这是其中的一道，正好借这道题把所有的排序算法写一遍。
题目链接 http://www.bianchengla.com/course/ds/practise/problem?id=1426 （有的排序应用于这道题是超时的）
1.
//直接插入排序
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define N 10000
int a[N];
int main()
{
int n,i,t,j;
int k;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
if(a[i]<a[i-1])
{
k=a[i];
j=i-1;
do
{
a[j+1]=a[j];
j--;
}while(j>=0&&k<a[j]);
a[j+1]=k;
}
}
for(i=0;i<n;i++)
cout<<a[i]<<"";
cout<<endl;
}
return 0;
}
2.
//冒泡排序
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
#define N 10000
int a[N];
int main()
{
int n,i,t;
int k,j;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1]){k=a[j];a[j]=a[j+1];a[j+1]=k;}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}
return 0;
}
3.
1 //折半插入排序
2 #include<stdio.h>
3 #include<iostream>
4 #include<string.h>
5 using namespace std;
6 #define N 10000
7 int a[N];
8 int main()
9 {
10 int n,i,t,h;
11 int k;
12 cin>>t;
13 while(t--)
14 {
15 cin>>n;
16 for(i=1;i<=n;i++)
17 cin>>a[i];
18 for(i=1;i<=n;i++)
19 {
20 k=a[i];
21 int low=0;
22 int high=i-1;
23 while(low<=high)
24 {
25 int mid=(low+high)/2;
26 if(k<a[mid])
27 high=mid-1;
28 else low=mid+1;
29 }
30 for(h=i-1;h>=low;h--) a[h+1]=a[h];
31 a[low]=k;
32 }
33 for(i=1;i<=n;i++)
34 cout<<a[i]<<"";
35 cout<<endl;
36 }
37 return 0;
38 }
4.
1 //希尔排序
2 #include<stdio.h>
3 #include<string.h>
4 #include<iostream>
5 using namespace std;
6 #define N 10000
7 int a[N];
8 int main()
9 {
10 int t,i,j,n;
11 cin>>t;
12 while(t--)
13 {
14 cin>>n;
15 for(i=1;i<=n;i++)
16 cin>>a[i];
17 int gap=n+1;
18 do
19 {
20 gap=gap/3+1;
21 for(i=0+gap;i<=n;i++)
22 {
23 if(a[i]<a[i-gap])
24 {
25 int k=a[i];
26 j=i-gap;
27 do
28 {
29 a[j+gap]=a[j];
30 j-=gap;
31 }while(j>0&&k<a[j]);
32 a[j+gap]=k;
33 }
34 }
35
36 }while(gap>1);
37 for(i=1;i<=n;i++)
38 cout<<a[i]<<"";
39 cout<<endl;
40 }
41 return 0;
42 }
5.
1 //快速排序
2 #include<stdio.h>
3 #include<string.h>
4 #include<iostream>
5 using namespace std;
6 #define N 10000
7 int a[N];
8 void sort(int a[],int l,int r)
9 {
10 int ll=l;
11 int rr=r;
12 int key=a[ll];
13 if(ll>rr) return ;
14 while(ll<rr)
15 {
16 while(ll<rr&&key<=a[rr]) rr--;
17 a[ll]=a[rr];
18 while(ll<rr&&key>a[ll]) ll++;
19 a[rr]=a[ll];
20 }
21 a[ll]=key;
22 sort(a,l,ll-1);
23 sort(a,ll+1,r);
24 }
25 int main()
26 {
27 int t,i,n;
28 cin>>t;
29 while(t--)
30 {
31 cin>>n;
32 for(i=1;i<=n;i++)
33 cin>>a[i];
34 sort(a,1,n);
35 for(i=1;i<=n;i++)
36 cout<<a[i]<<"";
37 cout<<endl;
38 }
39 return 0;
40 }
6.
//选择排序
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
#define N 10000
int a[N];
int main()
{
int t,i,n,j;
cin>>t;
while(t--)
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<n;i++)
{
int k=i;
for(j=i+1;j<=n;j++)
{
if(a[j]<a[k]) k=j;
}
if(k!=i) swap(a[i],a[k]);
}
for(i=1;i<=n;i++)
cout<<a[i]<<"";
cout<<endl;
}
return 0;
}
7.我就是不明白为啥这个归并排序用在这里是超时的，归并排序的时间复杂度和快排是一样一样滴呀，都是log级别的
1 //归并排序
2
3 #include<stdio.h>
4 #include<string.h>
5 #include<iostream>
6 using namespace std;
7 #define N 100001
8 #define MAX 999999999
9 int a[N],x[N],y[N];
10 void rank(int a[],int p,int q,int r)
11 {
12 int n1=q-p+1;
13 int n2=r-q;
14 int i,j,k;
15 memset(x,0,sizeof(x));
16 memset(y,0,sizeof(y));
17 for(i=1;i<=n1;i++)
18 {
19 x[i]=a[p+i-1];
20 }
21 for(i=1;i<=n2;i++)
22 {
23 y[i]=a[n1+p+i-1];
24 }
25 x[n1+1]=y[n2+1]=MAX;
26 for(k=p,i=1,j=1;k<=r;k++)
27 {
28 if(x[i]<=y[j]) a[k]=x[i++];
29 else a[k]=y[j++];
30 }
31 }
32 void guibing(int a[],int l,int r)
33 {
34 if(l<r)
35 {
36 int mid=(l+r)/2;
37 guibing(a,l,mid);
38 guibing(a,mid+1,r);
39 rank(a,l,mid,r);
40 }
41 }
42 int main()
43 {
44 int t,n,i;
45 cin>>t;
46 while(t--)
47 {
48 cin>>n;
49 for(i=0;i<n;i++)
50 scanf("%d",a+i);
51 guibing(a,0,n-1);
52 for(i=0;i<n-1;i++)
53 printf("%d ",a[i]);
54 //printf("")
55 cout<<a[n-1]<<endl;
56 }
57 return 0;
58 }
8.这个就是经典的堆排序，以前花了一个下午才搞明白到底怎么回事，没想到前天写的时候又被卡住了。真的是很弱呀
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 #define N 100001
6 int a[N],n;
7 void adjust(int x,int y)
8 {
9 int i,j,key;
10 i=x;
11 j=i*2;
12 key=a[x];
13 while(j<=y)
14 {
15 if(j<y&&a[j+1]<a[j]) j++;
16 if(key>a[j])
17 {
18 a[i]=a[j];
19 i=j;
20 j=i*2;
21 }
22 else break;
23 }
24 a[i]=key;
25 }
26 int main()
27 {
28 int i,t;
29 cin>>t;
30 while(t--)
31 {
32 cin>>n;
33 for(i=1;i<=n;i++)
34 scanf("%d",&a[i]);
35 for(i=n/2;i>0;i--) adjust(i,n);
36 while(n--)
37 {
38 printf("%d ",a[1]);
39 a[1]=a[n+1];
40 adjust(1,n);
41 }
42 cout<<endl;
43 }
44 return 0;
45 }
今天就先写到这里吧，还有几个其他的排序算法，想桶排序，基数排序等，弄明白了再往上填