前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布

排序

作者头像
Gxjun
发布2018-03-26 16:31:55
6210
发布2018-03-26 16:31:55
举报
文章被收录于专栏:ml

排序法

平均时间

最差情形

稳定度

额外空间

冒泡

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)

插入排序:

代码语言:javascript
复制
 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 */

冒泡排序:

代码语言:javascript
复制
 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 }

归并排序:

代码语言:javascript
复制
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);

}

计数排序:

代码语言:javascript
复制
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 }

桶排序:

代码语言:javascript
复制
//桶排序
#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;
}

选择排序:

代码语言:javascript
复制
 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 }

快速排序:

代码语言:javascript
复制
 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 }

堆排序:

代码语言:javascript
复制
 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 }

基数排序:

代码语言:javascript
复制
 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 }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-09-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档