Chinaunix首页 | 论坛 | 博客
  • 博客访问: 739967
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1115
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,既当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-02-17 12:33:42

归并排序,其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了?可以将A,B组各自再分成二组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列,再合并数列就完成了归并排序。

第一个问题,解决 合并两个有序数组。
这个问题比较简单,把两个有序数组看着两个顺序栈,比较栈顶元素,将较小者弹出到新的队列中;然后再次比较栈顶元素,如此重复。直到一个数组元素全部完毕,那么剩余数组的元素一次添加到新队列的尾部,即完成合并。
实现如下:

点击(此处)折叠或打开

  1. static void mergeList(int listA[], int lenA, int listB[], int lenB, int outList[])
  2. {
  3.     int idxa = 0;
  4.     int idxb = 0;
  5.     int idxout = 0;
  6.     int i;

  7.     while (idxa < lenA && idxb < lenB)
  8.     {
  9.         if (listA[idxa] <= listB[idxb])
  10.             outList[idxout++] = listA[idxa++];
  11.         else
  12.             outList[idxout++] = listB[idxb++];
  13.     }

  14.     if (idxa < lenA)
  15.     {
  16.         for (i = idxa; i < lenA; i++)
  17.             outList[idxout++] = listA[idxa];
  18.     }

  19.     if (idxb < lenB)
  20.     {
  21.         for (i = idxb; i < lenB; i++)
  22.             outList[idxout++] = listB[idxb];
  23.     }
  24. }

基于上面的分析和实现,归并排序的算法实现:
(1)以步长为1(相邻元素),进行有序合并;合并后,每两个元素满足有序关系;
(2) 按2的倍数增大步长,同样进行相邻组有序合并,直到步长大于/等于 (len + 1)/2,此时完成了最后一次将整个数组分为两个有序数组的合并。即完成了排序。
实现如下:

点击(此处)折叠或打开

  1. void DACsort(int list[], int len)
  2. {
  3.     int grpLen = 1;
  4.     int grpLeft; // left group start index
  5.     int grpLftLen;
  6.     int grpRtLen;
  7.     int i;

  8.     int *pConter;
  9.     int *pCur;
  10.     int *pBk;
  11.     int *pTemp;
  12.     int *pMerge;

  13.     // 辅助队列,与原始数据队列交替使用
  14.     pConter = (int *)malloc(sizeof(int) * len);
  15.     if (NULL == pConter)
  16.         return;
  17.     pBk = list;
  18.     pCur = pConter;

  19.     while(grpLen <= (len + 1) / 2)
  20.     {
  21.         pMerge = pCur;
  22.         for (grpLeft = 0; grpLeft < len; grpLeft += grpLen * 2)
  23.         {
  24.             if (grpLeft + grpLen < len)
  25.             {
  26.                 grpLftLen = grpLen;

  27.                 if (grpLeft + 2 *grpLen <= len)
  28.                     grpRtLen = grpLen;
  29.                 else
  30.                     grpRtLen = len - (grpLeft + grpLen);
  31.             }
  32.             else
  33.             {
  34.                 grpLftLen = len - grpLeft;
  35.                 grpRtLen = 0;
  36.             }
  37.             
  38.             mergeList(pBk + grpLeft, grpLftLen, pBk + grpLeft + grpLen, grpRtLen, pMerge);
  39.             pMerge += grpLftLen + grpRtLen;
  40.         }

  41.         pTemp = pBk;
  42.         pBk = pCur;
  43.         pCur = pTemp;
  44.         grpLen *= 2;
  45.     }

  46.     if (pBk != list)
  47.     {
  48.         for (i = 0; i < len; i++)
  49.             list[i] = pBk[i];
  50.     }
  51.     free(pConter);
  52. }

阅读(1999) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~