归并排序的递归算法与非递归

昨天晚上搞了好久，总有那么几个数据有点错误，原来数组是从1开始存的，没看清楚...

/*
请设计归并排序算法函数void mergeSort(int a[],int n)，对a[1]..a[n]进行升序排序。
并测试在不同数据规模下的排序效率。
*/
#include "Arrayio.h"
#define N 10000     /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/

/*请将本函数补充完整，并进行测试*/

void merge(int a[], int u, int m, int v)
{ /*将有序段a[u..m],a[m+1..v]归并到a[u..v]*/
    int i, j, k;
    int t[N+1];
    i = u, j = m + 1, k = u;
    while (i <= m && j <= v)
    {
        if (a[i] <= a[j])
        {
            t[k++] = a[i++];
        }
        else
        {
            t[k++] = a[j++];
        }
    }
    while (i <= m)
        t[k++] = a[i++];
    while (j <= v)
        t[k++] = a[j++];
    for (i = u; i <= v; i++)
        a[i] = t[i];
}


/*----一趟归并------*/
void mergepass(int a[], int n, int len)
{ /*对a[1..n]进行长度为len的一趟并归*/
    int i = 1;
    while (i+2*len-1 <= n)
    {
        merge(a,i, i + len - 1, i + 2 * len - 1);
        i = i + 2 * len;
    }
    if (i+len-1<n)
        merge(a,i, i +len-1 , n);
}

/*----归并排序------*/
void mergeSort(int a[], int n)
{
    int len = 1;
    while (len<=n)
    {
        mergepass(a, n, len);
        len = 2 * len;
    }
}

/*归并排序的递归实现*/
void mergeSortdc(int a[], int low, int high)
{
    int mid;
    if (low<high)
    {
        mid = (low + high) / 2;
        mergeSortdc(a,low, mid);
        mergeSortdc(a,mid + 1, high);
        merge(a, low,mid, high);
    }
}

int  main()
{
  int a[N+1],n;                     /*数据存储在a[1]...a[N]中*/
  printf("数据初始化...\n");
  n=readData(a,N,"data1.txt");      /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/
  printf("%d个数据排序中...\n",n);
  mergeSort(a,n);                   /*mergeSortdc(a,1,n);*/
  saveData(a,n,"D:\\out.txt");          /*排序结果存放在out.txt文件中*/
  printf("排序结束，排序结果保存在out.txt文件中。\n");
  return 0;
}

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 500000

/*从文件中读入数据存入数组a*/
int readData(int a[], int n,char *f )  /*函数返回成功读入的数据个数*/
{
    FILE *fp;
    int i;
    fp=fopen(f,"r");
    if (fp==NULL)   return 0;
    else
    {
        for (i=0;i<n && !feof(fp);i++)
            fscanf(fp,"%d",&a[i]);
        fclose(fp);
        return i;
    }
}

/*存盘函数*/
void saveData(int a[],int n, char *f )
{
    FILE *fp;
    int i;
    fp=fopen(f,"w");
    if (fp==NULL)   printf("文件建立失败！");
    else
    {
        for (i=0;i<n;i++)
            {   if (i%10==0) fprintf(fp,"%c",'\n');
                fprintf(fp,"%8d",a[i]);
            }
        fclose(fp);
    }
}


/*输出长度为n的整型数组*/
void output(int a[],int n)
{  int i;
   printf("\n数组的内容是：\n");
   for (i=0;i<n;i++)
     { if (i%10==0) printf("\n");
       printf("%7d",a[i]);
     }
  printf("\n");
}