个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2016-02-17 12:33:42
归并排序，其的基本思路就是将数组分成二组a，b，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将a，b组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
第一个问题，解决 合并两个有序数组。
这个问题比较简单，把两个有序数组看着两个顺序栈，比较栈顶元素，将较小者弹出到新的队列中；然后再次比较栈顶元素，如此重复。直到一个数组元素全部完毕，那么剩余数组的元素一次添加到新队列的尾部，即完成合并。
实现如下：
点击(此处)折叠或打开
-
static void mergelist(int lista[], int lena, int listb[], int lenb, int outlist[])
-
{
-
int idxa = 0;
-
int idxb = 0;
-
int idxout = 0;
-
int i;
-
-
while (idxa < lena && idxb < lenb)
-
{
-
if (lista[idxa] <= listb[idxb])
-
outlist[idxout] = lista[idxa];
-
else
-
outlist[idxout] = listb[idxb];
-
}
-
-
if (idxa < lena)
-
{
-
for (i = idxa; i < lena; i)
-
outlist[idxout] = lista[idxa];
-
}
-
-
if (idxb < lenb)
-
{
-
for (i = idxb; i < lenb; i)
-
outlist[idxout] = listb[idxb];
-
}
- }
基于上面的分析和实现，归并排序的算法实现：
（1）以步长为1（相邻元素），进行有序合并；合并后，每两个元素满足有序关系；
（2） 按2的倍数增大步长，同样进行相邻组有序合并，直到步长大于/等于 (len 1)/2，此时完成了最后一次将整个数组分为两个有序数组的合并。即完成了排序。
实现如下：
点击(此处)折叠或打开
-
void dacsort(int list[], int len)
-
{
-
int grplen = 1;
-
int grpleft; // left group start index
-
int grplftlen;
-
int grprtlen;
-
int i;
-
-
int *pconter;
-
int *pcur;
-
int *pbk;
-
int *ptemp;
-
int *pmerge;
-
-
// 辅助队列，与原始数据队列交替使用
-
pconter = (int *)malloc(sizeof(int) * len);
-
if (null == pconter)
-
return;
-
pbk = list;
-
pcur = pconter;
-
-
while(grplen <= (len 1) / 2)
-
{
-
pmerge = pcur;
-
for (grpleft = 0; grpleft < len; grpleft = grplen * 2)
-
{
-
if (grpleft grplen < len)
-
{
-
grplftlen = grplen;
-
-
if (grpleft 2 *grplen <= len)
-
grprtlen = grplen;
-
else
-
grprtlen = len - (grpleft grplen);
-
}
-
else
-
{
-
grplftlen = len - grpleft;
-
grprtlen = 0;
-
}
-
-
mergelist(pbk grpleft, grplftlen, pbk grpleft grplen, grprtlen, pmerge);
-
pmerge = grplftlen grprtlen;
-
}
-
-
ptemp = pbk;
-
pbk = pcur;
-
pcur = ptemp;
-
grplen *= 2;
-
}
-
-
if (pbk != list)
-
{
-
for (i = 0; i < len; i)
-
list[i] = pbk[i];
-
}
-
free(pconter);
- }
给主人留下些什么吧！~~