Just enjoy programming

插入排序,选择排序,冒泡排序,归并排序(c语言实现)

今天复习了下一些常见的排序算法,并用c语言实现了下。代码如下:
#include<stdio.h>
#include<stdlib.h>

#define MAX 65536 /*用于归并排序中的哨兵*/

/*简单插入排序,时间复杂度为o(n2),稳定排序,适合已经排好序的*/
void insertSort(int arr[],int len)
{
    int i,j;
    int key;
    for(i=1;i<len;i++)
    {
        key=arr[i];
        for(j=i-1;j>=0;j--)
        {
            if(arr[j]>key)
                arr[j+1]=arr[j];
            else
                break;
        }
        arr[j+1]=key;
    }
}

/*选择排序,时间复杂度为o(n2),不稳定排序,适合规模比较小的*/
void selectSort(int arr[],int len)
{
    int i,j,temp;
    for(i=0;i<len;i++)
    {
        for(j=i+1;j<len;j++)
        {
            if(arr[i]>arr[j])
            {
                temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }
    }
}

/*冒泡排序,时间复杂度为o(n2),稳定排序,适合规模比较小的*/
void bubbleSort(int arr[],int len)
{
    int i,j,temp;
    for(i=0;i<len;i++)
    {
        for(j=0;j<len-i-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

/*合并(归并)排序,时间复杂度为o(nlogn),稳定排序,适合规模比较大的排序*/
void merge(int arr[],int p,int q,int r)
{
    int *A,*B;
    int n1,n2,i,j,k;
    n1=q-p+1;
    n2=r-q;
    if((A=(int*)malloc((n1+1)*sizeof(int)))==NULL)
    {
        perror("malloc error");
        exit(1);
    }
    if((B=(int*)malloc((n2+1)*sizeof(int)))==NULL)
    {
        perror("malloc error");
        exit(1);
    }
    for(i=0;i<n1;i++)
    {
        A[i]=arr[p+i];
    }
    A[i]=MAX;
    for(i=0;i<n2;i++)
    {
        B[i]=arr[q+i+1];
    }
    B[i]=MAX;
    i=0;j=0;
    for(k=p;k<=r;k++)
    {
        if(A[i]>B[j])
        {
            arr[k]=B[j];
            j++;
        }else{
            arr[k]=A[i];
            i++;
        }
    }
}

void mergeSort(int arr[],int begin,int end)
{
    int mid;
    if(begin<end)
    {
        mid=(begin+end)/2;
        mergeSort(arr,begin,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,begin,mid,end);
    }
}

int main()
{
    int a[8]={5,2,4,7,1,3,2,6};
    int b[8]={5,2,4,7,1,3,2,6};
    int c[8]={5,2,4,7,1,3,2,6};
    int d[8]={5,2,4,7,1,3,2,6};
   
    int i;
    /*测试插入排序*/
    insertSort(a,8);
    printf("after 插入排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");

    /*测试选择排序*/
    selectSort(b,8);
    printf("after 选择排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",b[i]);
    }
    printf("\n");
   
    /*测试冒泡排序*/
    bubbleSort(c,8);
    printf("after 冒泡排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",c[i]);
    }
    printf("\n");
   
    /*测试归并排序*/
    mergeSort(d,0,7);

    printf("after 归并排序\n");
    for(i=0;i<8;i++)
    {
        printf("%d ",d[i]);
    }
    printf("\n");
}

posted on 2011-03-15 16:15 周强 阅读(5318) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理