排序算法的数组实现 -- 合并排序(五)
[cpp ]void Insert_sort_Swap_Node(EleLink *old_froMax_Node, EleLink *old_Max_Node,EleLink *froMax_Node, EleLink *Max_Node)
{
EleLink *tmp = Max_Node->pnext;
if(old_Max_Node->pnext == Max_Node)
{
old_froMax_Node->pnext = Max_Node;
Max_Node->pnext = old_Max_Node;
old_Max_Node->pnext = tmp;
}
else
{
old_froMax_Node->pnext = Max_Node;
Max_Node->pnext = old_Max_Node->pnext;
froMax_Node->pnext = old_Max_Node;
old_Max_Node->pnext = tmp;
}
}
void Link_Insert_Sort(EleLink *pNode)
{
if(!pNode || !pNode->pnext)
return;
EleLink *p = pNode->pnext;
int ncount = 0;
while (p)
{
ncount++;
p = p->pnext;
}
p = pNode;
EleLink *fro_Node, *froMax_Node;
EleLink *cur_Node, *Max_Node;
for (int i = 0; i < ncount - 1; i++)
{
froMax_Node = p;
Max_Node = p->pnext;
fro_Node = p->pnext;
cur_Node = fro_Node->pnext;
while(cur_Node)
{
if(Max_Node->Value > cur_Node->Value)
{
froMax_Node = fro_Node;
Max_Node = cur_Node;
}
fro_Node = cur_Node;
cur_Node = cur_Node->pnext;
}
if(Max_Node != p->pnext)
Insert_sort_Swap_Node(p, p->pnext,froMax_Node, Max_Node);
p = p->pnext;
}
}
void Bucket_Sort(int *a, int size, EleLink** bucket, int ncnt)
{
for(int i = 0; i < size; i++)
{
int temp = a[i] / 10;
EleLink *p_Ele = new EleLink;
p_Ele->pnext = NULL;
p_Ele->Value = a[i];
EleLink *ptr = bucket[temp];
EleLink *p_tmp = ptr->pnext;
ptr->pnext = p_Ele;
p_Ele->pnext = p_tmp;
}
int m = 0;
for (int j = 0; j < ncnt; j++)
{
Link_Insert_Sort(bucket[j]);
EleLink *ptr = bucket[j]->pnext;
while(ptr)
{
a[m++] = ptr->Value;
ptr = ptr->pnext;
}
}
assert(m == size);
}
作者:wchm_seu
补充:软件开发 , C++ ,