一般语言都提供了按字典排序的api，比如跟微信公众平台对接时就需要用到字典排序。按字典排序有很多种算法，最容易想到的就是字符串搜索的方式，但这种方式实现起来很麻烦，性能也不太好。trie树是一种很常用的树结构，它被广泛用于各个方面，比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等，而且在输入法中也能看到trie树的身影。 什么是trie树 trie树通常又称为字典树、单词查找树或前缀树，是一种用于快速检索的多叉树结构。如图数字的字典是一个10叉树：
同理小写英文字母或大写英文字母的字典数是一个26叉树。如上图可知，trie树的根结点是不保存数据的，所有的数据都保存在它的孩子节点中。有字符串go, golang, php, python, perl，它这棵trie树可如下图所示构造：
我们来分析下上面这张图。除了根节点外，每个子节点只存储一个字符。go和golang共享go前缀，php、perl和python只共用p前缀。为了实现字典排序，每一层节点上存储的字符都是按照字典排序的方式存储(这跟遍历的方式有关)。我们先来看看对单个字符如何进行字典排序。本文只考虑小写字母，其它方式类似。’a’在’b’的前面，而’a’的ascii码小于’b’的ascii码，因此通过它们的ascii相减就可以得到字典顺序。而且python内置了字典排序的api，比如：
代码如下:
#!/usr/bin/env python#coding: utf8
if __name__ == ‘__main__’: arr = [c for c in ‘python’] arr.sort() print arr
而且也可以使用我之前的一篇文章介绍的bitmap来实现：python: 实现bitmap数据结构 。实现代码如下：
代码如下:
#!/usr/bin/env python#coding: utf8
class bitmap(object): def __init__(self, max): self.size = self.calcelemindex(max, true) self.array = [0 for i in range(self.size)]
def calcelemindex(self, num, up=false): ”’up为true则为向上取整, 否则为向下取整”’ if up: return int((num + 31 – 1) / 31) #向上取整 return num / 31
def calcbitindex(self, num): return num % 31
def set(self, num): elemindex = self.calcelemindex(num) byteindex = self.calcbitindex(num) elem = self.array[elemindex] self.array[elemindex] = elem | (1