归并排序_递归方法实现

/*

 *  递归方法实现归并排序

 *  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;            //k是Rl的下标，i、j分别为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]);

 

}