归并排序，快速排序，堆排序，冒泡排序 c语言源代码

1.归并排序

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 50000

void merge(int [],int,int,int);//归并排序数组合并函数声明
void mergesort(int [],int,int);//归并排序数组排序函数声明

//主函数
int  main()
{
    int i,a1[N];
    double t1,t2,t3,t4;
        
    for(i=0;i<N;i++)
    {
        a1[i]=rand()%N;
    }
    

    //归并排序N个随机数字所用的时间
    t2=clock();
    mergesort(a1,0,N-1);
    t2=clock()-t2;
    
    /*排好序的结果*/
    for(i=0;i<N-1;i++)
    { 
        printf("%4d\n",a1[i]);
    }

    printf("\n归并排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);
    getch();
    return 1;
}



//归并排序
//归并排序合并数组函数的具体实现
void merge(int a[],int low,int middle,int high)
{
    int h,i,j,k;
    int b[N];
    h=low;
    i=low;
    j=middle+1;

    while(h<=middle&&j<=high)
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        { 
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>middle)
    for(k=j;k<=high;k++)
    {
        b[i]=a[k];
        i++; 
    }
    else
    {
        for(k=h;k<=middle;k++)
        { 
            b[i]=a[k];
            i++;
        }
    }
    for(k=low;k<=high;k++)
    {
        a[k]=b[k];
    }
}

//归并排序函数的具体实现
void mergesort(int a[],int low,int high)
{
    int middle;
    if(low<high)
    {
        middle=(low+high)/2;
        mergesort(a,low,middle);
        mergesort(a,middle+1,high);
        merge(a,low,middle,high);
    }
}

2.快速排序

#include"stdio.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 50000


void quickSort(int a[],int left,int right)
{
   int i,j,temp;
   i=left;
   j=right;
   temp=a[left];
   if(left>right)
      return;
   while(i!=j)/*找到最终位置*/
   {
      while(a[j]>=temp && j>i)
         j--;
      if(j>i)
         a[i++]=a[j];
       while(a[i]<=temp && j>i)
          i++;
       if(j>i)
          a[j--]=a[i];
         
   }
   a[i]=temp;
   quickSort(a,left,i-1);/*递归左边*/
   quickSort(a,i+1,right);/*递归右边*/
}

int main()
{
    double t2=clock();
    int i,a[N];
    for(i=0;i<N;i++)
    {
        a[i]=rand()%N;
    }

    quickSort(a,0,N-1);
    t2=clock()-t2;
    /*排好序的结果*/
    for(i=0;i<N-1;i++)
    { 
        printf("%4d\n",a[i]);
    }
        
    printf("\n快速排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);
    getch();
    return 1;
}

3.堆排序

#include <stdio.h>
#include <time.h>
#include <math.h>

#define LEFT(i)        ((i)<<1)
#define RIGHT(i)    (((i)<<1) + 1)
#define N 50000

void max_heapify(int a[], int i, int heapsize);
void heap_sort(int a[], int heapsize);
void build_max_heap(int a[], int heapsize);
void exchange(int *x, int *y);

//交换两个数的值
void exchange(int *x, int *y) {
    int temp;

    temp = *x;
    *x = *y;
    *y = temp;
}

//保持最大堆性质
void max_heapify(int a[], int i, int heapsize) {
    int left, right, largerest;

    left = LEFT(i);
    right = RIGHT(i);

    if (left <= heapsize && a[left]>a[i])
    {
        largerest = left;
    }else{
        largerest = i;
    }

    if (right <= heapsize && a[right]>a[largerest])
    {
        largerest = right;
    }

    if(largerest != i) {
        exchange(&a[i], &a[largerest]);
        max_heapify(a, largerest, heapsize);
    }

}

//建造最大堆
void build_max_heap(int a[], int heapsize) {
    int i;

    for (i=(int)ceil(heapsize/2); i >=1 ; i--)
    {
        max_heapify(a, i, heapsize);
    }
}

//堆排序
void heap_sort(int a[], int heapsize) {

    //build heap
    build_max_heap(a, heapsize);

    while(heapsize>1)
    {
        //exchange max
        exchange(&a[1], &a[heapsize]);
        heapsize--;
        max_heapify(a, 1, heapsize);
    }
    
}

int main() {
    
    double t2=clock();
    int i,a[N];
    for(i=0;i<N;i++)
    {
        a[i]=rand()%N;
    }

    heap_sort(a, N-1);
    t2=clock()-t2;

    //打印排序后的数组
    for (i=1; i<N ; i++)
    {
        printf("%d\n",a[i]);
    }
    printf("\n堆排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);
    getch();
    return 1;

}

4.冒泡排序

#include <stdio.h>
#include <time.h>
#include <math.h>

#define N 50000

int main()
{
    double t2=clock();
    int i,j,a[N];
    int flag=1;
    int temp;
    for(i=0;i<N;i++)
    {
        a[i]=rand()%N;
    }

    for(i=0;i<N;i++)
    {
        for(j=0;j<N-i;j++)
        {
            if(a[j+1]<a[j])
            {
              temp=a[j+1];
              a[j+1]=a[j];
              a[j]=temp;
              flag=0;
            }   
        }
        if(flag==1)
        {
           break;
        }   
    }
    t2=clock()-t2;

    //打印排序后的数组
    for (i=0; i<N ; i++)
    {
        printf("%d\n",a[i]);
    }
    printf("\n冒泡排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);
    getch();
    return 1;
}

时间性能最好的是快速排序，最差的是冒泡排序。。。。。。

原文地址：http://my.oschina.net/wangwang110/blog/11127