排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 |
---|---|---|---|---|
冒泡 | O(n2) | O(n2) | 稳定 | O(1) |
交换 | O(n2) | O(n2) | 不稳定 | O(1) |
选择 | O(n2) | O(n2) | 不稳定 | O(1) |
插入 | O(n2) | O(n2) | 稳定 | O(1) |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) |
Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) |
插入排序:
1 #include<stdio.h>
2 //╡ЕхКеепР
3 template<class T1 ,class T2>
4 void Isort(T1 *arg , T2 len){
5
6 T2 i,j;
7 for(i=1; i<len ; i++){
8 int val = arg[i];
9 for( j= i-1 ; j>=0&&val<arg[j]; j--)
10 arg[j+1]=arg[j];
11 arg[j+1]=val;
12 }
13 }
14 /*
15 template<class T1 ,class T2 ,size_t size>
16 void Isort(T1 (&arg)[size] , T2 len){
17
18 T2 i,j;
19 for(i=1; i<len ; i++){
20 int val = arg[i];
21 for( j= i-1 ; j>=0&&val<arg[j]; j--)
22 arg[j+1]=arg[j];
23 arg[j+1]=val;
24 }
25 }
26 */
冒泡排序:
1 void mPaoSort(int *arg , int len){
2 int i,j;
3 bool tag;
4 for(i=0;i<len ;i++){
5 for(j=i+1 , tag= false ;j<len ;j++){
6 if(arg[i]>arg[j]){
7 arg[i]^=arg[j];
8 arg[j]^=arg[i];
9 arg[i]^=arg[j];
10 tag=true;
11 }
12 }
13 if(!tag) break;
14 }
15 }
归并排序:
void Merge(int *A ,int ps ,int mid , int len){
int i=ps,j=mid,cnt=0;
int C[len-ps+1];
while(i<mid&&j<len ){
if(A[i]>A[j]) C[cnt++]=A[j++];
else C[cnt++]=A[i++];
}
while(i<mid) C[cnt++]=A[i++];
while(j<len) C[cnt++]=A[j++];
for(i=ps; i<len ;i++)
A[i]=C[i-ps];
}
//递归版
void Msort(int *arg ,int ps, int len){
if(ps+1<len) {
int mid = ps+((len-ps)>>1L);
Msort(arg ,ps ,mid);
Msort(arg, mid,len);
Merge(arg ,ps,mid, len);
}
}
//非递归版
void Msort_(int *arg , int ps , int len){
int s,t=1;
while(ps+t<=len){
s=t;
t=2*s;
int pos=ps;
while(pos+t<=len){
Merge(arg,pos,pos+s,pos+t);
pos+=t; //移动
}
if(pos+s<len)
Merge(arg,pos,pos+s,len);
}
if(ps+s<len)
Merge(arg,ps,ps+s,len);
}
计数排序:
1 //╪фйЩеепР
2 void JSort(int *arg , int len){
3 int ans[10]={0} ,i,j=0;
4 for(i=0; i<len ;i++)
5 ans[arg[i]]++;
6 for(j=i=0;i<10 ;i++)
7 while(ans[i]--)
8 arg[j++]=i;
9 }
桶排序:
//桶排序
#include<iostream>
#include<string.h>
typedef struct node{
int val ;
struct node * next;
void init(){
val=0;
next=NULL;
}
}Node;
void BSort(int *arg , int len , int blen ){
int i;
Node* Barry = (Node *)malloc(blen*sizeof(Node)); //定义一个二维数组
for( i=0;i<blen ;i++)
Barry[i].init();
Node *head =NULL;
for( i=0;i<len ;i++){
Node *p = (Node *)malloc(sizeof(Node));
p->val=arg[i];
p->next=NULL;
int sp = arg[i]/10;
head =&Barry[sp];
if(!head->val){
//为空,就直接将其加载到后面即可
head->next = p;
head->val=head->val+1; //统计个数
}else{
//如果不相等,选择插入排序
Node *tm=head->next ,*cur =head;
while(tm!=NULL&&tm->val<arg[i]){
cur =tm;
tm=tm->next;
}
cur->next=p ;
p->next = tm;
head->val=head->val+1;
}
}
for(int i=0; i<blen ;i++){
Node *p;
if(Barry[i].val){
p = Barry[i].next;
while(p){
printf("%d ",p->val);
p=p->next;
}
puts("");
}
}
}
int main1(int argc , char* argv[] ){
int ss[]={3,4,5,61,12,8,9,20,22,45,87};
BSort(ss ,sizeof(ss)/sizeof(int), 10);
return 0;
}
选择排序:
1 //选择排序
2 void Ssort(int *arg ,int len){
3 for(int i=0;i<len ;i++){
4 int mx=i;
5 for(int j=i+1; j<len ;j++){
6 if(arg[mx]<arg[j])mx=j;
7 }
8 if(i!=mx){
9 arg[mx]^=arg[i];
10 arg[i]^=arg[mx];
11 arg[mx]^=arg[i];
12 }
13 }
14 }
快速排序:
1 //快速排序
2 void qsort(int *arg ,int ps ,int len){
3
4 int i,j,val=arg[ps];
5 if(ps<len){
6 i=ps,j=len;
7 while(i!=j){
8 while(i<j&&arg[j]>=val) j--;
9 if(i<j) arg[i] = arg[j];
10 while(i<j&&arg[i]<=val) i++;
11 if(i<j)arg[j]=arg[i];
12 }
13 arg[i]=val;
14 qsort(arg,ps ,i-1);
15 qsort(arg,i+1,len);
16 }
17 }
堆排序:
1 //堆排序
2 void MaxHeap(int *arg ,int ps ,int len){
3 //构建一个堆
4 int cl = 2*ps , cr = 2*ps+1;
5
6 if(ps<=len/2){
7 int mx = ps; //父节点
8 if(cl<len&&arg[mx]<arg[cl]) mx = cl;
9 if(cr<len&&arg[mx]<arg[cr]) mx = cr;
10 if(mx!=ps){
11 arg[mx]^=arg[ps];
12 arg[ps]^=arg[mx];
13 arg[mx]^=arg[ps];
14 MaxHeap(arg,mx,len); //数据有改动,需要重新对改动的地方进行维护
15 }
16 }
17 }
18
19 //建立新堆
20 void Build(int *arg , int len){
21 for(int i=len/2 ; i>=1 ; i--){
22 MaxHeap(arg,i,len);
23 }
24 }
25
26 //堆排序Hsort
27 void Hsort(int *arg , int len){
28 Build(arg,len); //初始化
29 // (o(n))
30 for(int i=len ; i>1 ; i--){
31 arg[1]^=arg[i];
32 arg[i]^=arg[1];
33 arg[1]^=arg[i];
34 MaxHeap(arg,1,i);
35 }
36 }
基数排序:
1 //基数排序
2 typedef struct bas{
3 int val;
4 struct bas *next;
5 void init(){
6 val=0;
7 next=NULL;
8 }
9 }Bas;
10 void Basort(int *arg ,int len){
11 //对于数字在0-9
12 Bas *Barr[10]; //0-9
13 for(int i=0;i<10 ; i++){
14 Barr[i] = (Bas *)malloc(sizeof(Bas));
15 Barr[i]->init();
16 }
17 bool tag=false;
18 int mod =1;
19 while(1){
20 tag=false;
21 for(int i=0;i<10 ; i++)
22 Barr[i]->init();
23 for(int i=0;i<len ; i++){
24 Bas *p = (Bas *)malloc(sizeof(Bas));
25 p->val=arg[i];
26 p->next=NULL;
27 int hig =arg[i]/mod;
28 int dex = hig%10;
29 if(hig) tag=true; //只要有一位不为0,就继续
30 Bas *pb=Barr[dex];
31 while(pb->next)
32 pb = pb->next;
33 pb->next = p;
34 }
35 //将值全部放置到arg中
36 int cnt=0;
37 for(int i=0;i<10 ; i++){
38 Bas *pb = Barr[i]->next,*tm;
39 while(pb){
40 arg[cnt++]=pb->val;
41 tm=pb;
42 pb=pb->next;
43 free(tm);
44 }
45 }
46 if(!tag) return ;
47 mod*=10;
48 }
49 }
50
51 int main(){
52 int sss[]={100,123,45,67,123,1,4,5,10};
53 Basort(sss,sizeof(sss)/sizeof(int));
54 print(sss,sizeof(sss)/sizeof(int));
55 return 0;
56 }