document.write('这道题本质上还是考察对字符串排序的理解，唯一不同的是，改变了比较字符串大小的规则，因此
这道题的关键是如何利用给定的规则比较两个字符串的大小，只要实现了两个字符串的比较，那么
利用任何一种排序方法都可以。下面重点介绍字符串比较的方法。
本题的主要思路为：为给定的字母序列建立一个可以进行大小比较的序列，在这里我们采用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"。
下面以插入排序为例，给出实现代码：
#根据char_to_int规定的字符的大小关系比较两个字符的大小
def compare(str1,str2,char_to_int):
len1=len(str1)
len2=len(str2)
i=0
j=0
while i＜len1 and j＜len2:
#如果字符不在给定的序列中, 那么把值赋为-1
if list(str1)[i] not in char_to_int.keys():
char_to_int[list(str1)[i]]=-1
if list(str2)[j] not in char_to_int.keys():
char_to_int[list(str2)[j]]=-1
#比较各个字符的大小
if char_to_int[list(str1)[i]]＜char_to_int[list(str2)[j]]:
return -1
elif char_to_int[list(str1)[i]]＞char_to_int[list(str2)[j]]:
return 1
else:
i+=1
j+=1
if i==len1 and j ==len2:
return 0
elif i==len1:
return -1
else:
return 1
def insertSort(s,char_to_int):
#对字符串数组进行排序
lens=len(s)
i=1
while i＜lens:
temp=s[i]
j=i-1
while j＞=0:
#用给定的规则比较字符串的大小
if compare(temp,s[j],char_to_int)==-1:
s[j+1]=s[j]
else:
break
j-=1
s[j+1]=temp
i+=1
if __name__="__main__":
s=["bed","dog","dear","eye"]
sequence="dgecfboa"
lens=len(sequence)
#用来存储字母序列与其对应的值的键值对
char_to_int=dict()
#根据给定字符序列构造字典
i=0
while i＜lens:
char_to_int[list(sequence)[i]]=i
i+=1
insertSort(s,char_to_int)
i=0
while i＜len(s):
print s[i],
i+=1
程序的运行结果为：
dear dog eye bed
算法性能分析：
这种方法的时间复杂度为O(N3
)(其中N为字符串的长度)。因为insertSort函数中使用了双重遍
历，而这个函数中调用了compare函数，所以这个函数内部也有一层循环。
');