关于文本排序的那些事
大家都知道，排序算法是计算机学科最基础的知识之一，常见的排序算法有冒泡、快排等。这里讨论的文本排序不是一个排序算法，而是作为某个排序算法的底层依赖，常常在多语言环境下需要考虑，比如说中文的排序，日文的排序。
一个软件系统要做到全球化（globlization），应考虑以下几个方面：
- 国际化（internationizaion，i18n），国际化主要考虑文字翻译，让用户可以切换到他习惯的语言使用。
- 本地化（localization），本地化主要考虑一些因各个国家地区不同的习俗习惯而导致的问题，比如说日期显示格示，数字显示方式等。本文讨论的文本排序就属于本地化范畴。
一个系统要做到全球化，需要仔细考虑文本排序，因为文本排序可能会影响到系统的架构。之前就遇到过一个关于文本排序的问题，问题的原型是：
有一个电商平台，商家可以在平台上开店，在商家的后台产品管理界面，商家看到的产品列表默认以名字排序。现在有如下产品（名字）：“abc”, “#abc”, “abc a”, “!abc”, “ abc”, “~abc”，但是看到的排列顺序却是：“abc”, “~abc”，“ abc”, “!abc”, “#abc”, “abc a”，可以看到a打头的两个名字“abc”，“abc a”被其他的以特殊符号打头的名字（“~abc”，“ abc”, “!abc”, “#abc”）分开了，直观上看起来不合理，照道理说两个a打头的名字应该挨在一起，这是为什么呢？
后来研究发现，这个问题是一个文本排序问题。
这个问题的原因是：电商平台底层用的是Posgres数据库，页面上看到的产品列表的排序是在后台数据库完成的。简单讲，这个排序动作可以翻译成如下sql语句：
SELECT name FROM unnest(ARRAY[
'abc', '#abc', 'abc a', '!abc', ' abc', '~abc'
]) name ORDER BY name在数据库执行这条语句，得到的结果如下：
可以看到这个顺序和页面上显示的顺序是match的，说明问题就出在数据库这里。
那么数据库为什么会出现这样的排序结果呢？原因跟数据库的Locale Support相关，数据库Locale的设置会影响排序的方式，比如说locale设置成zh_CN，中文字符就会按照拼音排序；如果设置成zh_TW，中文字符就会按照笔画排序（其他字符则按照unicode的顺序）。
执行下面sql语句可以查看数据库支持哪些locale：
select * from pg_collation;
当执行sql语句做查询时，如果不指定任何collation key，就采用default的collation。关于default的collation是哪个，可以参考Postgres官方documentation - https://www.postgresql.org/docs/9.5/locale.html。
简单讲，如果创建db的时候没指定locale，就用默认的；指定了locale，就用指定的。
我们创建数据库的时候没有指定，所以用的是default的collation，default的会参考操作系统默认的locale设定，这里是en_US.utf8。在这种collation方式下，排序方式是：忽略打头的特殊字符，比如“~”，“！”，“ ”，拉丁字母按ASCII码顺序排序，其他字符按unicode顺序排序。如下：
排序方式也可以在执行sql语句的显示指定，如下显示指定分别按照简体中文和繁体中文排序：
繁体中文以笔划排序
简体中文以拼音排序
如果要解决上面的问题，我们也可以显示指定collation key为C，这种排序方式就是按照我们直观可理解的ASCII码顺序排序，a打头的两个名字挨着一起：
当然，对于一个电商平台（SaaS系统）来说，这种方案可以解决问题，但是会增加代码的复杂度，因为需要在每条sql语句后面根据商家的国家地区来显示指定一个collation key，如果这个平台面向的商家来自很多国家地区，这将会使代码变得非常复杂。针对这样的SaaS系统来说，我们可以考虑其他的一些解决方案：
1. 数据库的服务器直接落地在客户（商家）所在国家地区，这样可以使默认的locale和客户一致；
2. 当然，在平台setup的时候，不可能覆盖所有国家。针对一些小国家地区的客户（商家），可以使用统一的数据库服务器，但是setup独立的数据库instance，在setup instance的时候指定locale。
编程语言的支持
对于文本排序，各个开发语言也都有很好的支持。
Javascript
var items = ["一", "二", "三" , "四" , "五", "六", "七", " 七", "八", " 八", "a", "b", "1", "我"];
items.sort((a, b) => a.localeCompare(b, 'zh-TW', {ignorePunctuation: false, numeric: true}));
items.sort((a, b) => a.localeCompare(b, 'zh-CN-u-co-pinyin', {ignorePunctuation: false, numeric: true}));执行上面JS代码，得到如下结果：
Java
Locale l = new Locale("zh", "CN");
//Locale l = new Locale("zh", "TW");
String[] str = {"一", "二", "三" , "四" , "五", "六", "七", "' '七", "八", "' '八", "a", "b", "1", "我"};
List<String> strList = Arrays.asList(str);
Collator coll = Collator.getInstance(l);
Collections.sort(strList, coll);
System.out.println(strList);执行上面Java代码，得到如下结果：
从上面的排序结果可以看到，Java和Javascript排序的结果有点不一样，Java排序结果英文字符在中文字符前面，而Javascript排序结果英文字符在中文字符后面，这应该跟相应Library的实现有关，因为从Java官方文档可以看到，Java在处理打头的特殊字符时，会自动忽略掉，这个解释和上面最初的原型问题是吻合的，see
https://docs.oracle.com/javase/7/docs/api/java/text/RuleBasedCollator.html#compare(java.lang.String
同时可以看到javascript和Postgres的排序结果时吻合的，两者都是把英文字符在中文字符后面（至少从采用的排序locale来说）。
延伸
文章开头提到一些基础排序算法，有兴趣的同学可以网上搜索再回顾一下。See https://www.runoob.com/w3cnote/sort-algorithm-summary.html。
另外下面列出一些跟排序相关的应用场景：
- 数据库索引：二叉查找树（BST，二分查找，时间复杂度o(lonN)），B-树，B+树（多叉查找树，减少磁盘IO）。具体可以阅读：漫画：什么是B-树？，漫画：什么是B+树？。
- Java TreeMap HashMap：二叉查找树（BST，二分查找，时间复杂度o(lonN)），红黑树（平衡二叉查找树）。具体可以阅读：漫画：什么是红黑树？。
- 文本搜索：字典树，Trie，按照字典排序。具体可以阅读：看动画轻松理解「Trie树」。看动画轻松理解「Trie树」看动画轻松理解「Trie树」
References
- 查询unicode：https://unicodelookup.com/