搜索
 找回密码
 立即注册

简单一步 , 微信登陆

DTV多节目快速排序的方法

作者:halleyhuang | 时间:2016-11-16 16:24:48 | 阅读:4659| 显示全部楼层
对于卫星接收机,可以保存5000个节目,如果采用传统的冒泡等排序方式,会消耗很多时间。
递归排序,必须考虑堆栈空间,不建议使用:
static MS_BOOL QuickSort(SORT_SERVICENAME_STRUCTURE*pStServName,MS_U16*pOrder,MS_U16 num)
{
      MS_U16 i;
      MS_U16 n_small=1,n_big=num-1;//升序
      MS_U16 m_key=pOrder[0];
      MS_BOOL xiaokong=TRUE;//小头有空
      MS_U16 m_free = 0;
      MS_U16 wCompRes;
      if(num<=1)return TRUE;///递归终止条件
      for(i=0;i<num-1;i++)
      {
         if(xiaokong)//小头有空
         {
              wCompRes=COMPARE_ALPHAVALUE(pStServName[pOrder[n_big]].strServiceName,pStServName[m_key].strServiceName);
              if(wCompRes<1)
              {
                   pOrder[m_free] = pOrder[n_big];
                   m_free=n_big;
                   xiaokong=FALSE;
              }
              n_big--;
         }
         else//大头有空
         {
              wCompRes=COMPARE_ALPHAVALUE(pStServName[pOrder[n_small]].strServiceName,pStServName[m_key].strServiceName);
              if(wCompRes>1)
              {
                   pOrder[m_free] = pOrder[n_small];
                   m_free=n_small;
                   xiaokong=TRUE;
              }
              n_small++;
         }
      }
      if(m_free != 0)
      {
           pOrder[m_free] = m_key;
      }
      if(QuickSort(pStServName,&pOrder[0],m_free) && QuickSort(pStServName,&pOrder[m_free+1],num-(m_free+1) ) )
      {
             return TRUE;
      }
      return FALSE;
}

修改为如下排序方式,申请内存机制处理:
#define MAX_LEVELS  300
#define SWAP_U16(a,b) do{MS_U16 tmp=a;a=b;b=tmp;}while(0)
static MS_BOOL QuickSort(SORT_SERVICENAME_STRUCTURE *pStServName, MS_U16 *pu16Order, MS_U16 u16Num)
{
    MS_S32 s32Idx=0;
    MS_S32 s32Piv;
    MS_S32 s32L;
    MS_S32 s32R;
    MS_S32 *ps32Begin=NULL;
    MS_S32 *ps32End=NULL;
    ps32Begin = (MS_U16 *)MsOS_AllocateMemory(sizeof(MS_U16)*MAX_LEVELS, gs32CachedPoolID);
    if(!ps32Begin)
    {
        return FALSE;
    }
    ps32End = (MS_U16 *)MsOS_AllocateMemory(sizeof(MS_U16)*MAX_LEVELS, gs32CachedPoolID);
    if(!ps32Begin)
    {
        MsOS_FreeMemory((void*)ps32Begin, gs32CachedPoolID);
        return FALSE;
    }
    ps32Begin[0]=0;
    ps32End[0]=u16Num;
    while (s32Idx>=0)
    {
        s32L=ps32Begin[s32Idx];
        s32R=ps32End[s32Idx]-1;
        if(s32L<s32R)
        {
            s32Piv=pu16Order[s32L];
            while (s32L<s32R)
            {
                while (COMPARE_ALPHAVALUE(pStServName[pu16Order[s32R]].strServiceName, pStServName[s32Piv].strServiceName)<1 && s32L<s32R)
                {
                    s32R--;
                }
                if (s32L<s32R)
                {
                    pu16Order[s32L++]=pu16Order[s32R];
                }
                else
                {
                    break;
                }
                while (COMPARE_ALPHAVALUE(pStServName[pu16Order[s32L]].strServiceName, pStServName[s32Piv].strServiceName)>1 && s32L<s32R)
                {
                    s32L++;
                }
                if (s32L<s32R)
                {
                    pu16Order[s32R--]=pu16Order[s32L];
                }
            }
            pu16Order[s32L]=s32Piv;
            ps32Begin[s32Idx+1]=s32L+1;
            ps32End[s32Idx+1]=ps32End[s32Idx];
            ps32End[s32Idx++]=s32L;
            if (ps32End[s32Idx]-ps32Begin[s32Idx] > ps32End[s32Idx-1]-ps32Begin[s32Idx-1])
            {
                SWAP_U16(ps32Begin[s32Idx], ps32Begin[s32Idx-1]);
                SWAP_U16(ps32End[s32Idx], ps32End[s32Idx-1]);
            }
        }
        else
        {
            s32Idx--;
        }
    }
    MsOS_FreeMemory((void*)ps32Begin, gs32CachedPoolID);
    MsOS_FreeMemory((void*)ps32End, gs32CachedPoolID);
    return TRUE;
}


该会员没有填写今日想说内容.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册
手机版