首页 > 代码库 > 后缀数组

后缀数组

先明白 基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

LSD与MSD:LSD从低位开始排到高位,每排一位都是把各个桶合并,再按下一位排序;MSD从高位开始排到低位,排完一位后不合并桶,相同的高位划分子桶继续分配,最后再合并

然后是 倍增算法

 

后缀数组