这是一个外部归并排序的实现，写这个源于在网上经常看到这样一类问题——"只用一个大小为10的数组来排序10000个随机整数?"。刚好闲来有空，就试着写了，真诚的希望大家给点建议（其它的话就不要多说了）:
/*只用一个大小为10的数组来排序1000个随机整数?
*/
#include
#include
#include
#include
#define TOTAL_NUM 10000
#define NumOf(a) (sizeof(a)/sizeof(a[0]))
void shell_sort(int *x, int n);
void merge(FILE *fp1,FILE *fp2, int low,int mid,int high);
void merge_sort(FILE *fp1,FILE *fp2,int low,int high);
void bin_to_txt_file(FILE *fp_dst, FILE *fp_src);
void sort_cell(FILE *fp1,int low,int mid,int high);
int gs=0;
int buf[10];
/*
*argv[1]: orignal data file name; 10000个随机整数
*argv[2]: sorted data file name; 排序结果
*/
int main(int argc, char *argv[])
{
FILE *fp_src, *fp_dst, *fp_tmp, *fp_rlt;
char *str = (char*)buf;
int rnd = rand();
int i;
//fp_src = fopen(argv[1], "wt+");
//fp_dst = fopen("dst.bin", "wb+");
fp_src = fopen("src.txt", "wt+");
fp_dst = fopen("dst.bin", "wb+");
srand((unsigned)time(NULL));
for (i=1; i
{
char str[43];
rnd = rand();
fprintf(fp_src, "%16 0x%x\t", rnd);
if (i%10 == 0)
fprintf(fp_src, "\n");
fwrite((const char*)(&rnd), sizeof rnd, 1, fp_dst);
}
fclose(fp_src);
rewind(fp_dst);
fp_tmp = fopen("tmp.bin", "wb+");
merge_sort(fp_dst, fp_tmp, 0, TOTAL_NUM-1);
rewind(fp_dst);
fp_rlt = fopen("rlt.txt", "wt+");
//fp_rlt = fopen(argv[2], "wt+");
bin_to_txt_file(fp_rlt, fp_dst);
fclose(fp_dst);
fclose(fp_tmp);
fclose(fp_rlt);
remove("tmp.bin");
remove("dst.bin");
system("PAUSE");
return EXIT_SUCCESS;
}
void sort_cell(FILE *fp1,int low,int mid,int high)
{
int offset, count;
assert(mid-low<=NumOf(buf) && high-mid+1<=NumOf(buf));
offset = low * sizeof(buf[0]);
count = mid - low;
fseek(fp1, offset, SEEK_SET); //fsetpos(fp1,&offset);
fread(buf, sizeof(int), count, fp1);
shell_sort(buf, count);
fseek(fp1, offset, SEEK_SET);
fwrite(buf, sizeof(int), count, fp1);
offset = mid * sizeof(buf[0]);
count = high - mid + 1;
fseek(fp1, offset, SEEK_SET);
fread(buf, sizeof(buf[0]), count, fp1);
shell_sort(buf, count);
fseek(fp1, offset, SEEK_SET);
fwrite(buf, sizeof(buf[0]), count, fp1);
}
void bin_file_copy(FILE *fp_dst, FILE *fp_src)
{
int count, buf_int;
while (fread(&buf_int, 1, sizeof buf_int, fp_src) == sizeof buf_int)
{
fwrite(&buf_int, sizeof buf_int, 1, fp_dst);
}
//do{
// count = fread(buf, 1, sizeof buf, fp_src);
// fwrite(buf, count, 1, fp_dst);
//}while(count==sizeof buf);
}
void bin_to_txt_file(FILE *fp_txt, FILE *fp_bin)
{
int a_int, i=0;
while (fread(&a_int, 1, sizeof(int), fp_bin) == sizeof(int))
{
fprintf(fp_txt,"%16 0x%x\t",a_int);
if (++i%10 == 0)
fprintf(fp_txt, "\n");
}
}
void merge(FILE *fp1,FILE *fp2, int low,int mid,int high)
{
int i=low,j=mid+1,k=low;
int left,right;
fseek(fp2, sizeof(int)*k, SEEK_SET);
while(i<=mid && j<=high)
{
fseek(fp1, sizeof(int)*i, SEEK_SET);
fread(&left,sizeof(int),1,fp1);
fseek(fp1, sizeof(int)*j, SEEK_SET);
fread(&right,sizeof(int),1,fp1);
if(left < right)
fwrite(&left,sizeof(int),1,fp2),++i;
else
fwrite(&right,sizeof(int),1,fp2),++j;
++k;
}
for(i=i>mid?j:i; k<=high; k++,i++)
{
fseek(fp1, sizeof(int)*i, SEEK_SET);
fread(&left, sizeof(int), 1, fp1);
fwrite(&left, sizeof(int), 1, fp2);
}
rewind(fp1);
rewind(fp2);
bin_file_copy(fp1,fp2);
}
void merge_sort(FILE *fp1, FILE *fp2, int low, int high)
{
++gs;
printf("lvl:%d$\n",gs);
int mid = (low+high)/2;
if (low+2*(NumOf(buf)-1) < high)
{
merge_sort(fp1, fp2, low, mid);
merge_sort(fp1, fp2, mid+1, high);
}
else
{
sort_cell(fp1, low, mid+1, high);
}
merge(fp1, fp2, low, mid, high);
}
void shell_sort(int *x, int n)
{
int h, j, k, t;
for (h=n/2; h>0; h=h/2)
{
for (j=h; j
{
t = *(x+j);
for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
{
*(x+k+h) = *(x+k);
}
*(x+k+h) = t;
}
}
}
