首页 > 代码库 > 20140525 冒泡

20140525 冒泡

1、冒泡排序(自己写)

#include<stdio.h>
#define swap(x,y)  x=x+y; y=x-y; x=x-y;
void maopao(int *a,int length)  //每次把最大的元素冒泡到数组末尾,从小到大的顺序,length是数组长度,a是数组名,作为形参之后,数组名退化为指针
{
    int i=0;
    int j=1;
    int temp=0;
    for(i=0;i<length;i++)
    {
        for(j=1;j<length-i;j++)
        {
            if(a[j-1]>a[j])
            {
                temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
            }
        }
    }
}

void display(int *a,int length)
{
    int i=0;
    while(i<length)
    {
        printf("%d ",a[i]);
        i++;
    }
    printf("\n");
}

void main( )
{
    int a[6]={2,4,3,7,6,1};
    int length=sizeof(a)/4;
    maopao(a,length);
    display(a,length);
}

2、鸡尾酒排序(冒泡排序的改进:如果序列开始已经大部分排序过的话,会接近O(n))

#include<stdio.h>
#define swap(x,y)  x=x+y; y=x-y; x=x-y;

void Cocktailsort(int *a,int length)
{
    int i=0,j=0,tail=length-1;
    int temp=0;
    for(i=0;i<tail;)  //排序范围是:i~tail
    {
        for(j=tail;j>0;j--)  //第一次冒泡,把最小的元素冒泡到最到i的位置
        {
            if(a[j]<a[j-1])
            {swap(a[j],a[j-1]);}//注意:一定要加大括号
        }
        i++;    //成功冒泡后,把起始索引加1
        for(j=i;j<tail;j++) //第二次冒泡,把最大的元素冒泡到tail的位置
            if (a[j]>a[j+1])
            {
                swap(a[j],a[j+1]);
            }
            tail--;   //成功冒泡把结束索引tail-1
    }
}

void display(int *a,int length)
{
    int i=0;
    while(i<length)
    {
        printf("%d ",a[i]);
        i++;
    }
    printf("\n");
}

void main( )
{
    int a[6]={2,4,3,7,6,1};
    int length=sizeof(a)/4;
    Cocktailsort(a,length);
    display(a,length);
}

3、直接插入排序

#include<stdio.h>

void Insertsort(int a[],int n)  
{
    int i=0,j=0;
    int temp=0;
    for(i=1;i<n;i++)
    {
        if(a[i]<a[i-1])
        {
            temp=a[i];
            for(j=i-1;j>=0&&a[j]>temp;j--)   //边检查边插入。代码比较完整
                a[j+1]=a[j];
            a[j+1]=temp;  //思考,这里为什么是a[j+1]
        }
    }
}

void display(int *a,int length)
{
    int i=0;
    while(i<length)
    {
        printf("%d ",a[i]);
        i++;
    }
    printf("\n");
}

void main( )
{
    int a[6]={2,4,3,7,6,1};
    int length=sizeof(a)/4;
    Insertsort(a,length);
    display(a,length);
}