简述诱导排序(induce sort)

诱导排序(induce sort)"/>

简述诱导排序(induce sort)

最近跟小焦看了个很好玩的算法，叫诱导排序(induce sort)。它设计得很精妙，通过排好序的C*，就能正确快速排好C-和C+，而且不会有漏掉和重复的可能。
要理解诱导排序，先要搞清字典序的概念。字典序按照字面意思就是字典的字母顺序。接下来要搞懂C-，C+，C*的定义。首先C-就是后面的数据在字典序里要更小了，C+则反之。C*则是C+的变体，如果C+前是C-，那么这个就是C*。如果后面是相同字母，那么当前的+-状态跟前个字母相同，以此类推。然后是后缀排序的基本概念。把C后面一直到下个C*的内容拼起来就是后缀，对这些后缀进行排序就是后缀排序。
好了，明白这些基本概念，就要开始理解算法了。怎么利用C*完整地找出对应的C-，C+。因为C+的机制跟C-的机制差不多，所以重点说说C-就好了。C-的遍历过程是通过按照字典序遍历所有出现过的字母。在每次处理当前字母的时候顺序把已经在栈里的字母重新压栈，并且把接下来需要处理的字母进行压栈。如果当前字母前面有C-，那么这些C-都会顺序入栈。这样就能保证数据不重复。随着字母的不断往后迭代，就能保证所有字母都能迭代到，从而保证数据不漏。因为C*是有序的，那么C-，C+就是有序的。
以上就是诱导排序的基本算法。C*排序需要利用到另外一个算法(LSD radix sort)。它这个算法的核心在于，每次都利用单个字母位进行桶排序(bucket sort)，这样就能保证C*符合字典序。进而保证整个诱导排序都是正确的。