排序

排序法

平均时间

最差情形

稳定度

额外空间

冒泡

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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

从星际2深度学习环境到神经机器翻译,上手机器学习这些开源项目必不可少

本文主要编译于 Github 文章「Getting started with machine learning」(原文链接:https://github.com...

384110
来自专栏深度学习之tensorflow实战篇

用户画像行为分析流程

什么是用户画像? 简而言之,用户画像是根据用户社会属性、生活习惯和消费行为等信息而抽象出的一个标签化的用户模型。构建用户画像的核心工作即是给用户贴“标签”,...

81380
来自专栏深度学习之tensorflow实战篇

随机森林,random forest

模型组合(比如说有Boosting,Bagging等)与决策树相关的算法比较多,这些算法最终的结果是生成N(可能会有几百棵以上)棵树,这样可以大大的减少单决策树...

30550
来自专栏AI研习社

YOLO,一种简易快捷的目标检测算法

YOLO全称You Only Look Once,是一个十分容易构造目标检测算法,出自于CVPR2016关于目标检测的方向的一篇优秀论文(https://arx...

37440
来自专栏深度学习之tensorflow实战篇

R语言 判别分析

#判别分析 用以判别个体所属群体的一种统计方法 判别分析重点是两类群体的判别方法 #主要判别分析方法 有距离判别 贝叶斯判别 费歇判别法 1、关键点: #贝叶斯...

32450
来自专栏AI研习社

高级数据科学家阿萨姆:如何应对机器学习过程中的多项选择问题?| 分享总结

AI 研习社按:随着硬件算力的上升、数据量的加大以及各种新算法的浮现,机器学习也变得一天比一天火热。不夸张的说,这是机器学习的时代。然而,机器学习虽然能够给出惊...

37660
来自专栏AI研习社

2017 摩拜杯算法挑战赛,第三名团队解决方案

比赛已经结束快两个月了,一直拖到现在才开始总结。 官网网址:https://biendata.com/competition/mobike/ GitHub源码:...

57060
来自专栏深度学习之tensorflow实战篇

SPSS Modeler 介绍决策树

本文将通过 SPSS Modeler 介绍决策树 (Decision tree) 演算法于银行行销领域的应用实例。通过使用网路公开电销资料建立不同决策树模型,分...

40880
来自专栏程序员互动联盟

C语言最难啃的三块硬骨头

提到C语言很多初学者都觉得,学到中间就进行不下去了,因为碰到了几个硬骨头死活翻不过去,于是很多人给C语言下结论太难了,太靠近底层了,特别是那几块难啃的骨头,直接...

48050
来自专栏AI研习社

AlphaZero 实战:从零学下五子棋(附代码)

2 个多月前,AlphaGo Zero 横空出世,完全从零开始,仅通过自我对弈就能天下无敌,瞬间刷爆朋友圈,各路大神分分出来解读,惊叹于其思想的简单、效果的神奇...

86160

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励