Chinaunix首页 | 论坛 | 博客
  • 博客访问: 230942
  • 博文数量: 75
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 848
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:27
文章分类
文章存档

2014年(9)

2013年(66)

我的朋友

分类: C/C++

2013-11-13 15:36:00

选择排序:
选择排序是交换排序的一种,从字面上理解就是交换元素以达到排序的目的。
选择排序算法的基本思想是对待排序的元素序列a[l]~a[r]进行r-l遍处理,第i遍处理是将第i小的元素放到第i个位置上,这样排序i次后前i小的元素都已经确定,下一次排序从第i+1个位置开始,对之后的元素与第i+1个元素进行比较,如果找到某元素比第i+1个位置上的元素还小,则交换。
C语言代码:


[cpp] view plaincopy
//选择排序所用的时间n*n,对于数比较多的时候相当费时  
//选择排序是交换排序的一种  
#include  
#include//为了使用malloc函数  
int count=0;//定义为局部变量,记录比较次数  
int sum=0;//定义为全局变量,记录交换次数  
void sort(int *a,int n)  
{  
 int i,j,t;  
    for( i=0;i     {  
          
        for( j=i+1;j         {     
          
            count++;//比较一次+1  
            if(a[i]>a[j])    //第i个位置的数与之后的数比较,如符合条件,则进行交换  
            {     
                sum++;//交换一次+1  
                 t = a[i];  
                a[i] = a[j];  
                a[j] = t;  
            }  
        }  
  
    }  
              
}  
int main()  
{  
    int *a;  //声明一个int 型指针  
    int n=10,t;//n可以自由输入,此处定义n=10;  
    a=(int *)malloc(sizeof(int)*n); //动态分配一片n个int 的空间 , 即数组a[n];  
    for( i=0;i         scanf("%d",&a[i]);  
    sort(a,n);//调用排序函数  
    for(i=0;i         printf("%d ",a[i]);  
    printf("\n比较次数:%d\n交换次数:%d\n",count,sum);   //输出比较次数和交换次数  
    return 0;  
}  


冒泡排序:
冒泡排序也是交换排序的一种,这种方法的基本思想是,将待排序的记录看作是竖着排序的“气泡”,键值较小的记录比较轻,因而要上浮。在冒泡排序算法中,要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的记录的顺序是否正确。如果发现两个相邻记录的顺序不对,即“轻”的记录在下,就要变换它们的位置。处理一遍之后,“最轻”的记录就浮到了最高的位置,处理两遍之后,“次轻”的记录就浮到了次高位置。在处理第二遍时,由于最高位置上的记录已经是最轻记录,所以不必检查。一般的,第i遍处理时,不必检查第i高位置以上的记录。
C语言代码:


[cpp] view plaincopy
//选择排序所用的时间n*n,对于数比较多的时候相当费时  
//选择排序是交换排序的一种  
#include  
#include//为了使用malloc函数  
int count=0;//定义为局部变量,记录比较次数  
int sum=0;//定义为全局变量,记录交换次数  
void sort(int *a,int n)  
{  
    int i,j,t;  
    for(i=0;i     {  
        for(j=0;j         {     
            count++;//比较一次+1  
            if(a[j]             {     
                sum++;//交换一次+1  
                t=a[j];  
                a[j] = a[j+1];  
                a[j+1] = t;  
            }  
        }  
    }  
}  
int main()  
{  
    int *a;  //声明一个int 型指针  
    int n=10,i;//n可以自由输入,此处定义n=10;  
    a=(int *)malloc(sizeof(int)*n); //动态分配一片n个int 的空间 , 即数组a[n];  
    for(i=0;i         scanf("%d",&a[i]);  
    sort(a,n);//调用排序函数  
    for(i=0;i         printf("%d ",a[i]);  
    printf("\n比较次数:%d\n交换次数:%d\n",count,sum);   //输出比较次数和交换次数  
    return 0;  
}  
阅读(1275) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~