想要一个C++实现外排序的源代码

发布网友发布时间：2022-04-24 09:57

共2个回答

热心网友时间：2022-06-18 19:12

这点分还着急，呵呵
估计看到你的帖子的人不多
200分，马上你会有很多收获.

“给后我视情况最少20分悬赏（最多50分，恩）”这种语句会令人看起来很不舒服，真正的高手是不会帮你的，给人感觉像是完成你的任务。如果这样，为了虚拟的分，不值得费这时间和脑筋。

我的建议是，lz问问题很好，但要注意语气。高分会让更多的人看到你的问题，所以比较着急的问题我一般都给200分，如果问题真着急，这点虚拟的分又算什么呢？你说是不是这个理，呵呵。
祝你早日解决问题

热心网友时间：2022-06-18 19:13

外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中需要多次访问外存
包括：
计数排序 Counting Sort
基数排序 Radix Sort
桶排序 Bin Sort
1.
//计数排序 Counting Sort
void CountingSort(const char *A, int len, char **ret)
{
if(len < 2 || !ret || !A)
{
return;
}

int Temp[256];
for(int i = 0; i < 256; i++)
{
Temp[i] = 0;
}

for(int i = 0; i<len; i++)
{
Temp[int(A[i])]++;
}

for(int i = 1; i<256;i++)
{
Temp[i]=Temp[i]+Temp[i-1];
}

for(int i = len-1; i >= 0 ; i--)
{
(*ret)[Temp[int(A[i])]-1] = A[i];
Temp[int(A[i])]--;
}
}
2.
//基数排序
int get_radix(int num, int radix)//取得基数位的数
{
int temp;
for(int i=0; i<radix; i++) {
temp = num%10;
num = num/10;
}
return temp;
}

void radix_sort(int *array, int size)
{
list<int> temp_list[10];
int max, radix, i, j, k;
char temp_buf[20];
list<int>::iterator iter;

memset(temp_buf, 0, sizeof(temp_buf));
max = array[0];
//找到最大数，算出最大数的位数作为基数
for (i=0; i<size; i++)
if (max < array[i])
max = array[i];

sprintf(temp_buf, "%d", max);
radix = strlen(temp_buf);

for (i=1; i<=radix; i++) {
for (j=0; j<size; j++)
temp_list[get_radix(array[j], i)].push_back(array[j]);

for (j=0, k=0; j<10; j++) {
iter = temp_list[j].begin();
for (; iter!=temp_list[j].end(); iter++)
array[k++] = *iter;
temp_list[j].clear();
}
}
}
3.
//
void comp(int k[],int m,int l)
{
int i=10,j=0,z=1,y=1,x,w,b[500][10];
for(w=0;w<m;w++)
for(x=0;x<10;x++)
{
b[w][x]=-1;
}
while(z>0)
{
z=l/i;
i=i*10;
++j; //记录最大数的位数
}
i=10;
while(j>0)
{
for(z=0;z<=m;z++)
{
x=(k[z]/y)%i;
b[z][x]=k[z];
}
w=0;
for(z=0;z<10;z++)
for(x=0;x<m;x++)
{
if(b[x][z]>=0)
{
k[w]=b[x][z];
b[x][z]=-1;
w++;
}
}
--j;
y=y*10;
}
for(z=0;z<m;z++)
{
printf("%d ",k[z]);
}
}

///////////////////////////////
下面给你一个外排序中基数排序的例子，实现从文件读取数据，在我的空间。
http://hi.baidu.com/freeemperor/blog/item/6f2222870bde2c2ec75cc300.html

参考资料：http://hi.baidu.com/freeemperor/blog/item/6f2222870bde2c2ec75cc300.html