Chinaunix首页 | 论坛 | 博客
  • 博客访问: 7688066
  • 博文数量: 961
  • 博客积分: 15795
  • 博客等级: 上将
  • 技术积分: 16612
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-07 14:23
文章分类

全部博文(961)

文章存档

2016年(1)

2015年(61)

2014年(41)

2013年(51)

2012年(235)

2011年(391)

2010年(181)

分类: C/C++

2011-05-31 10:34:45

/*

 *  递归方法实现归并排序

 *  Lzy     2011-5-25

 */

#include

#define N 8

 

//归并排序 递归实现

void merge(int X[], int low, int mid, int high) /*两个有序表的合并算法*/

{                                               //R[low..mid]R[mid+1..high]是两个有序表

    int R1[N];                                  //临时缓冲区

    int i = low, j = mid+1, k = low;            //kRl的下标,ij分别为R[low..m]R[m+1..high]的下标

 

    for(; i <= mid && j <= high; k++)           /*依次比较两个了序列中数据元素的大小*/

    {

        if(X[i] <= X[j])                        /*将较小的数移入缓冲区*/

            R1[k] = X[i++];                     //R[low..m]中的记录放入R1

        else

            R1[k] = X[j++];                     //R[m+1..high]中的记录放入R1

    }

   

    while(i <= mid)                             //R[low..m]余下部分复制到R1

        R1[k++] = X[i++];  

    while(j <= high)                            //R[m+1..high]余下部分复制到R1

        R1[k++] = X[j++];

 

    for(k = low; k <= high; k++)                /*将缓冲区中的数据元素复制回原序列中*/

        X[k] = R1[k];

}

 

void Merge_Sort(int X[], int low, int high)     /* 定义归并排序函数,递归方式 */

{

    int mid;

    if(low < high)

    {

        mid = (low + high) / 2;

        Merge_Sort(X, low, mid);                /* 递归调用,将子序列x[low~mid]归并为有序序列 */

        Merge_Sort(X, mid + 1, high);           /* 递归调用,将子序列x[mid+1~high]归并为有序序列 */

        merge(X,low,mid,high);                  /* 将子序列x[low~mid]x[mid+1~high]进行归并 */

    }

}

 

/******测试程序*******/

int main(void)

{

    int i;

    int X[N] = {26,23,96,13,36,67,45,15};

    Merge_Sort(X,0,7);

   

    for(i = 0; i < 8; i++)

        printf("%d ",X[i]);

 

}

 

阅读(3797) | 评论(0) | 转发(2) |
给主人留下些什么吧!~~