Kotlin程序员：按字母序排列字符数组的方法

【出自QNEW笔试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

已知字母序列[d，g，e，c，f，b，o，a]，请实现一个方法，要求对输入的一组字符串input[]={“bed”，“dog”，“dear”，“eye”}按照字母顺序排序并打印。本例的输出顺序为dear，dog，eye，bed。

分析与解答：

这道题本质上还是考察对字符串排序的理解，唯一不同的是，改变了比较字符串大小的规则，因此这道题的关键是如何利用给定的规则比较两个字符串的大小，只要实现了两个字符串的比较，那么利用任何一种排序方法都可以。下面重点介绍字符串比较的方法。

本题的主要思路：为给定的字母序列建立一个可以进行大小比较的序列，在这里采用map数据结构来实现map的键为给定的字母序列，其值为从0开始依次递增的整数，对于没在字母序列中的字母，对应的值统一按-1来处理。其这样在比较字符串中的字符时，不是直接比较字符的大小，而是比较字符在map中对应的整数值的大小。以“bed”、“dog”为例，[d，g，e，c，f，b，o，a]构建的map为char_to_int[‘d’]=0，char_to_int[‘g’]=1，char_to_int[‘e’]=2，char_to_int[‘c’]=3，char_to_int[‘f’]=4，char_to_int[‘b’]=5，char_to_int[‘o’]=6，char_to_int[‘a’]=7。在比较“bed”与“dog”的时候，由于char_to_int[‘b’]=5，char_to_int[‘d’]=0，显然5＞0，因此，‘b’＞’d’，所以，“bed”＞“dog”。(www.xing528.com)

下面以插入排序为例，给出实现代码：

程序的运行结果如下：

dea rdo geye bed

算法性能分析：

这种方法的时间复杂度为O（N^3）（其中N为字符串的长度）。因为insertSort函数中使用了双重遍历，而这个函数中调用了compare函数，所以这个函数内部也有一层循环。