电话号码排序

  n个7位电话号码，号码没有重复 请在2M的内存中对其排序.

  内存不够用,我这里想到的是外部排序,外部排序与分治合并有点类似...话不多说了,写的头都大了,读写文件是我不足的地方

  这里我修改成了100000个7位数,内存为100*4byte,最近都是在dev c++写程序的,可别被linux骨灰级人给BS了,俺也是terminal王者的.喜欢写写程序,看看web,music,qq and thunder^_^

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>

#define TOTAL_NUM 100000
#define NumOf(a) (sizeof(a)/sizeof(a[0]))
typedef unsigned int uint;
int gs=0;
int buf[100];

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);
uint get_rand();

/*
*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;
    uint rnd ;
    int i;

    fp_src = fopen("c:\\src.txt", "wt+");
    fp_dst = fopen("c:\\dst.txt", "wb+");
    srand((unsigned)time(NULL));
    for (i=1; i<TOTAL_NUM+1; ++i)
    {
        //char str[43];

        rnd = get_rand();
        fprintf(fp_src, "%8d\t", rnd);
        if (i%5 == 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("c:\\rlt.txt", "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;
}

uint get_rand()
{
  int i = 0;
  uint a1 = 0;
  uint a2 = 0;
  uint ret = 0;
  a1 = rand()%9+1;
  for(;i<6;i++)
   {
     a1 *= 10;
     a2 = a2*10 + rand()%10;
   }
   ret = a1 + a2;
   return ret;
 }

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);
    }
}

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,"%8d\t",a_int);
        if (++i%5 == 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<n; j++)
        {
            t = *(x+j);
            for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
            {
                *(x+k+h) = *(x+k);
            }
            *(x+k+h) = t;
        }
    }
}