Question

字典序排序

Answer 1

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。
对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。
中文名
字典序
外文名
lexicographical order
别名
词典顺序
定义
按字母顺序排列的方法
相关术语
有序集合
快速
导航
形式定义多个集合乘积描述程序源码算法说明
简单理解
设想一本英语字典里的单词，何者在前何者在后？
显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。
通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序：下面用形式化的语言说明。
形式定义
给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔积A×B，则字典序定义为
(a,b) ≤ (a′,b′) 当且仅当a<a′ 或 (a=a′ 且b≤b′).
结果是偏序。如果A和B是全序, 那么结果也是全序。