注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

简单排序  

2015-05-16 14:02:32|  分类: 算法&数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    简单排序一般指时间复杂度o(n^2)的排序算法。下面介绍三种简单排序:选择排序、冒泡排序、插入排序。

   (注意:从大到小)

1,选择排序

     思路,每次找最大数,交换至第一位,再从第二位找最大数,交换至第二位,如此类推。

     优点:交换次数少。

     缺点:最好打算为o(n^2)。

     程序:

#include<iostream>

using namespace std;

void _xz(int a[], int len);   //选择排序函数

int main()
{
    int n,a[10000];
    cin>>n;
    for (int i=0; i<n; i++)
      cin>>a[i];
    _xz(a,n);    //调用选择排序函数
    for (int i=0; i<n; i++)
      cout<<a[i]<<" ";
    return 0;
}

void _xz(int a[], int len)
{
     for (int i=0; i<len; i++)
     {
         int p=i;
         for (int j=i+1; j<len; j++)
           if (a[p]<a[j]) p=j;            //找最大数位置

         swap(a[i],a[p]);    //交换
     }
}

2,冒泡排序

     思路:

     1  2  3  4  5  //原数组

       步骤:

       1  2  3  5  4

       1  2  5  3  4

       1  5  2  3  4

       5  1  2  3  4  //第一趟循环,把最大数浮上去

       5  1  2  4  3

       5  1  4  2  3

       5  4  1  2  3  //第二趟,‘4’浮上去

       5  4  1  3  2

       5  4  3  1  2  //第三趟

       5  4  3  2  1  //第四趟

     优点:短,是稳定排序,优化程序时,最好打算的时间复杂度为o(n)。

     缺点:交换次数太多。

     程序:

#include<iostream>

using namespace std;

void _mp(int a[],int len);  //冒泡排序函数

int main()
{
 int n,a[10000];
 cin>>n;
 for (int i=0; i<n; i++)
   cin>>a[i];
 _mp(a,n);  //调用冒泡排序函数
 for (int i=0; i<n; i++)
      cout<<a[i]<<" ";
    return 0;
}

void _mp(int a[], int len)
{
 for (int i=0; i<len; i++)
   for (int j=len-1; j>i; j--)
     if (a[j]>a[j-1])    //可以浮上去

      swap(a[j],a[j-1]);  //交换
}

三,插入排序

       思路:像打牌一样,拿到一张新牌时,插入原先排好序的牌。

       优点:最好打算时,时间复杂度为o(n),和可用于其他方面。

       缺点:长,编写麻烦。

       程序:

#include<iostream>

using namespace std;

void _cr(int a[],int len);  //插入排序函数

int main()
{
 int n,a[10000];
 cin>>n;
 a[0]=2147483647;
 for (int i=1; i<=n; i++)
   cin>>a[i];
 _cr(a,n);  //调用插入排序函数
 for (int i=1; i<=n; i++)
      cout<<a[i]<<" ";
    return 0;
}

void _cr(int a[],int len)
{
 for(int i=1; i<=len; i++)  //取出新牌
 {
  int p=i,s=a[i];
  for (p=i; s>a[p-1]; p--) a[p]=a[p-1];  //找到合适位置和移动
  a[p]=s;  //插入
 }
}

  评论这张
 
阅读(8)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018