昨天晚上搞了好久，总有那么几个数据有点错误，原来数组是从1开始存的，没看清楚...
1 /* 2 请设计归并排序算法函数void mergeSort(int a[],int n)，对a[1]..a[n]进行升序排序。 3 并测试在不同数据规模下的排序效率。 4 */ 5 #include "Arrayio.h" 6 #define N 10000 /*N为数据量大小，因data1.txt中只有50万个数，所以自行设定N值时需让N<=500000*/ 7 8 /*请将本函数补充完整，并进行测试*/ 9 10 void merge(int a[], int u, int m, int v) 11 { /*将有序段a[u..m],a[m+1..v]归并到a[u..v]*/ 12 int i, j, k; 13 int t[N+1]; 14 i = u, j = m + 1, k = u; 15 while (i <= m && j <= v) 16 { 17 if (a[i] <= a[j]) 18 { 19 t[k++] = a[i++]; 20 } 21 else 22 { 23 t[k++] = a[j++]; 24 } 25 } 26 while (i <= m) 27 t[k++] = a[i++]; 28 while (j <= v) 29 t[k++] = a[j++]; 30 for (i = u; i <= v; i++) 31 a[i] = t[i]; 32 } 33 34 35 /*----一趟归并------*/ 36 void mergepass(int a[], int n, int len) 37 { /*对a[1..n]进行长度为len的一趟并归*/ 38 int i = 1; 39 while (i+2*len-1 <= n) 40 { 41 merge(a,i, i + len - 1, i + 2 * len - 1); 42 i = i + 2 * len; 43 } 44 if (i+len-1<n) 45 merge(a,i, i +len-1 , n); 46 } 47 48 /*----归并排序------*/ 49 void mergeSort(int a[], int n) 50 { 51 int len = 1; 52 while (len<=n) 53 { 54 mergepass(a, n, len); 55 len = 2 * len; 56 } 57 } 58 59 /*归并排序的递归实现*/ 60 void mergeSortdc(int a[], int low, int high) 61 { 62 int mid; 63 if (low<high) 64 { 65 mid = (low + high) / 2; 66 mergeSortdc(a,low, mid); 67 mergeSortdc(a,mid + 1, high); 68 merge(a, low,mid, high); 69 } 70 } 71 72 int main() 73 { 74 int a[N+1],n; /*数据存储在a[1]...a[N]中*/ 75 printf("数据初始化...\n"); 76 n=readData(a,N,"data1.txt"); /*从data1.txt中读入N个整数存入数组a，n为实际读入的数据个数*/ 77 printf("%d个数据排序中...\n",n); 78 mergeSort(a,n); /*mergeSortdc(a,1,n);*/ 79 saveData(a,n,"D:\\out.txt"); /*排序结果存放在out.txt文件中*/ 80 printf("排序结束，排序结果保存在out.txt文件中。\n"); 81 return 0; 82 }
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 #define MAX 500000 5 6 /*从文件中读入数据存入数组a*/ 7 int readData(int a[], int n,char *f ) /*函数返回成功读入的数据个数*/ 8 { 9 FILE *fp; 10 int i; 11 fp=fopen(f,"r"); 12 if (fp==NULL) return 0; 13 else 14 { 15 for (i=0;i<n && !feof(fp);i++) 16 fscanf(fp,"%d",&a[i]); 17 fclose(fp); 18 return i; 19 } 20 } 21 22 /*存盘函数*/ 23 void saveData(int a[],int n, char *f ) 24 { 25 FILE *fp; 26 int i; 27 fp=fopen(f,"w"); 28 if (fp==NULL) printf("文件建立失败！"); 29 else 30 { 31 for (i=0;i<n;i++) 32 { if (i%10==0) fprintf(fp,"%c",'\n'); 33 fprintf(fp,"%8d",a[i]); 34 } 35 fclose(fp); 36 } 37 } 38 39 40 /*输出长度为n的整型数组*/ 41 void output(int a[],int n) 42 { int i; 43 printf("\n数组的内容是：\n"); 44 for (i=0;i<n;i++) 45 { if (i%10==0) printf("\n"); 46 printf("%7d",a[i]); 47 } 48 printf("\n"); 49 }
