注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

排序算法之异谈  

2014-08-23 20:36:51|  分类: 学习录 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

      首先接上文排序算法汇总,先把基数排序写了。

       基数排序是利用了多个关键码来进行循环排序,这种思想并没有比较元素,通过每一次对不同基数的排序,最后把n次基数排序后的基本有序序列进行整合,这样就得到了有序的序。

 就好像扑克牌一样,假设梅花<方块<红桃<黑桃,那么我们一般是先对相同花色的牌进行排序之后,再做一次花色的排序,这里的关键码是花色和面值,我们讨论的基数排序中关键码数---序列元素的d位数中的个位、十位、百位...假设我们从最低位排起,按照关键码的不同值将序列中的元素分到d个子序列中,再将该次排序元素装入临时存储空间;再根据次关键码进行第二次排序...直到排完d次,我们用链表结构来存储每趟排序存储到该序列下的元素(排序整数序列的话,那么就是0-9了,此时d=10,共需要10个链表来存储),最后进行一次按照基数0-9的元素收集。

 看例子,序列R={179,208,306,93,859,984,55,8,271,33}下面是整个排序过程。

 排序算法之异谈 - mihooke - mihooke的博客

     这个过程值得玩味,请好好琢磨一下,如果你不仔细看,可能会有这种想法:为什么不直接先以百位上的数字为基数排序呢?如果这样排下去,原序列中的数字重新收集到临时序列中时,相对位置就有可能会改变,即失去了基数排序的稳定性。还有一点值得注意,那就是基数排序不是建立在元素比较的基础上的,那么必然会增加辅助空间使用来提高算法的效率,可以看到整个过程用到了2个临时序列。下面是数据结构和算法代码。

#define KEY 8  //关键码数

#define RADIX 10   //基数

#define MAX 100

typedef struct {

   int keys[KEY];

   int next;

}NodeType;

typedef struct {

   int f;

   int e;

}Q_Node;

typedef Q_Node queue[RADIX];

void distribute(NodeType R[],int i,queue q)

{//分配过程,把所有元素分配到10个基数子序列中,此时每个基数子序列中元素都是有序的

   int j,p;

   for(j=0;j<RADIX;j++)

   q[j].f=q[j].e=0;  //初始化各个子链表,这两个分别是指向链表的头部和尾部

   for(p=R[0].next;p;p=R[p].next)

   {

     j=R[p].keys[i];//i个元素映射到各个子链表中

     if(!q[j].f)

q[j].f=q[j].e=p;

     else

     {

       R[q[j].e].next=p;

       q[j].e=p;

     }

   }

}

void collect(NodeType R[],int i,queue q)

{//收集每个子链表中的元素,即q[]序列

   int t,j;

   for(j=0;!q[j].f;j=j.next);//j.nextj的后继

   R[0].next=q[j].f;

   t=q[j].e;

   while(j<RADIX)

   {

     for(j=j.next;j<RADIX&&!q[j].f;j=j.next);

       if(q[j].f)

       {

         R[j].next=q[j].f;

 t=q[j].e;

       }

   }

   R[t].next=0;

}

void Radixsort(NodeType R[],int n)

{

   int i;

   queue q;

   for(i=0;i<n;i++)

      R[i].next=i+1;

   R[n].next=0;

   for(i=0;i<KEY;i++)

   {

     distribute(R,i,q);

     collect(R,i,q);

   }

}

int MaxBit(int arr[], int len)
{
int d = 1;
int redix = 10;
for (int i=0; i< len; i++)
{
while (arr[i] > radix)
{
d++;
radix = radix*10;
}
}
return d;
}

void Jishusort(int arr[], int len)
{
int *temp = new int[len];
int *count = new int[10];
int i=j=k=0;
int d = MaxBit(arr, len);
int radix = 1;
for (i=1; i<=d; i++)
{
for (j=0;j<10;j++)
count[j] = 0;
for (j=0; j<len; j++)
{
k = (arr[j]/radix)%10;
count[k]++;
}
for (j=1; j<10; j++)
{
count[j] = count[j-1]+count[j];
}
for (j=len-1;j>=0;j--)
{
k = (arr[j]/radix)%10;
temp[count[k]-1] = arr[j];
count[k]--;
}
for (j=0;j<len;j++)
arr[j] = temp[j];

radix = radix *10;
}
delete []temp;
delete []count;
}


      在分配元素到各个子链表中的过程可能有点复杂,只要熟悉了链表的每步操作,思路就清晰了。基数排序要进行d趟的分配收集元素,而每趟时间复杂度是O(n+RADIX),那总的时间复杂度就是O就是(d(n+RADIX)),除此之外,还要额外增加2*RADIX个队列头部尾部指针的辅助空间,具体的时间复杂度参考《算法导论》第110页,详细推导了基数排序的正确性和时间代价

       基数排序和我们用的最多的快速排序比较哪个更好呢?我们已经知道快速排序的时间复杂度是O(nlog2n),当d~log2n的时候,我们认为两种排序时间复杂度差不多,但是背后隐藏的常数项因子是不相同的,在排序中,尽管所用趟数比快速排序少,但是每趟所用时间要比快速排序长的多,而且辅助空间也要大。通常选择哪一种算法,依赖于具体实现和底层硬件,因为快速排序可以比基数排序更有效地利用缓存空间,所以当主存紧张时,选择基于原址排序的快速排序是明智的。

       本来文章写到这就打算收笔的,但是当我看到刘未鹏的一篇文章"快排为什么这么快"(参见http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/或他的书《暗时间》-数学之美番外篇),瞬间我就有一种醍醐灌顶的感觉,一种学习算法以来从未有过的那种感觉,居然算法可以和称小球的经典智力题联系到一块。而排序算法和称小球问题看似不搭干的问题有着本质的联系:那就是均分策略。我相信,只要你看了刘未鹏的文章,对我的文章就没兴趣了~~,因为他讲的太详细了,有好多他自己的见解,但是我下面讲的比较通俗。哈哈。

      先来回忆一下称小球问题,我们把此问题简单化,有6只小球,最少次数称出那只和其他5只重量不一样的小球。最合适的方法就是先2个、2个称,因为称小球会出现3种情况:平衡、左倾、右倾。根据均分策略,只要我们在称的时候均分这3种情况即可得到最少的次数,这样在每次称完都会将可能缩小可能的1/3,不知道此刻的你想到这种方法了么?

接着看排序,排序也会出现3种情况,大于、小于和等于,但是我们对等于的情况不做处理,所以就是2种情况,我们只要在排序过程中等分这两种情况,就能分析出算法是否是高效的了。

      首先看快速排序,快排中用到一个轴值k,它是随机的一个元素,然后用low,high元素和k作比较。现在假设是按照升级排序的,已经有a[1]<k,那么low++,继续比较a [2]和k,由于在a[2]<k的情况下,a[1]和a[2]的关系不能确定,因此会出现2种情况:a[1] <a[2]<ka[2]<a[1]<k。那么当然还有k<a[2]的情况要考虑呀,可以证明k<a[2]的情况下,a[1],a[2],k,只有一种排列:a[1]<k<a[2]。所以在一次比较后,还有2/3的可能要排除。继续往下比较,k>a[2]了,那么会交换a[2]high元素,继续比较a[high-1]k,那么又会出现上面2/3需要排除的情。注意,前文中我们讲到的快排用到了二分法,所以每次概率都一样,假若用《算法导论》中的快排思想,那么下一次要排除的概率就是3/44/5。。。所以说,快排也不那么快。基于比较排序的算法的时间复杂度最优的也是O(nlog2n)


      我们前面讲了,基数排序综合来说是没有快速排序快的,效率上也没有快速排序好,但是这里我们从均分策略上分析,又可以发现基数排序却又是那么的快。由于基数排序不是基于比较的排序,所以每趟循环中只是根据基位来移动序列中的元素。根据基数有e[0]e[9]10个位置,每出现一个元素,则把元素放在对应的e位置下面,第一个元素179会直接放在e[9]之下,第二个元素放置的位置和第一个元素没有任何影响,还是有10种可能,一旦放下去,可能性就确定了,也就是说每次可以排除9种可能,而上面用二分法思想实现的快速排序每次最多只能排除一半的可能性。所以从均分策略上将,基数排序符合这种规律,所以也要快得多。基数排序时间复杂度最优可以是O(n)

  评论这张
 
阅读(138)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017