在计算机中，字符可以进行大小比较，ASCCI码字符大小关系如图(ASCCI码字符大小)，和数轴类似，左边的字符小于右边的字符。而字符串由字符组成，因此简单的字符串排序方法，可以逐字符进行大小比较排序。

ASCCI码字符大小

例如 a9.txt, a10.txt, 假设按字符升序逐个排序，则排序的结果为a10.txt, a9.txt。第1个字符双方都是'a'，大小相等；由于按升序排序，第2个字符'1'排在字符'9'前面，即'1'<'9'，因此'a1'排在'a9'前面，后面就不需要再继续比较了。

注：为了更好的区分是数字还是字符，这里使用计算机中习惯的表达方式，字符使用单引号''引用。

但是上面排序的结果，和我们直观感受的排序不一样。由于我们对数字比较敏感，一般会把数字字符串'10'看成数字10，'9'看成数字9，而9<10，因此按数字升序排序，则排序的结果为a9.txt, a10.txt。

Windows 和 MACOS 操作系统中的文件列表按文件名称排序设计时也非常人性化的考虑到这一点，它们不是简单的按字符进行排序，而是按字符和数字进行排序。虽然二者会稍微有细微的不同，主要是存在冗余的前缀0数字字符时会有不同。

稍加思考后，其实不难想到一种简单的排序算法，我把该算法称之为字符串自然排序。这里要解决的问题本质上是2个字符串大小比较。 比较大小的算法如下：

逐字符比较2个字符串:

1. 如果2个字符中任意一个不是数字字符，则直接按字符大小比较，大小不相等，则直接返回这2个字符相比后的大小；否则，继续逐字符比较。

2. 如果2个字符都是是数字字符，那么找出各自这一段连续的数字字符串，把这一段连续的数字字符串输入到下面的步骤进行大小比较。大小不相等，则直接返回相比后的大小；否则，接着继续逐字符比较。

2.1 去掉冗余的前缀0数字字符，例如 0012，实际上为数字12。

2.2 先按位数判断大小。位数相等的，从高位开始逐位比较大小。

2.3 前一个步骤如果判断的数字大小相等，则依据冗余的前缀0的长度大小比较，冗余的前缀0越长则规定为越大。例如 0012 > 012。

注： 上面描述的字符串自然排序算法不考虑负数和小数，即会出现 -1 > +1(因为 '-' > '+'), 以及 3.14 < 3.100 (因为'.'看成一个字符，数字14 < 100)的情况。Windows 和 MACOS 操作系统按文件名称排序也会出现类似的情况。

上面的大小比较算法，显然能满足对称性：字符串A < 字符串B，则必定有字符串B > 字符串A ，同样字符串A = 字符串B，则必定有字符串B = 字符串A。即交互两者的顺序，不会改变他们之间的大小关系。

但是传递性，却不那么显然了。传递性是讲，如果字符串A < 字符串B，并且字符串B < 字符串C，那么一定有字符串A < 字符串C。如果传递性不成立，那么这个大小比较算法就不能用于排序算法。 所以传递性的证明是重要的。我们知道，如果A、B、C是数字，那么小学生也会认可传递性的成立。但是在某些方面，传递性可能是不成立的，我举个例子。例如在象棋比赛中，如果选手A赢了选手B, 可以记为A > B，反之则 A < B，和棋则 A = B。 若选手A > 选手B, 选手B > 选手C, 我们不能断定选手A一定能赢选手C，即选手A > 选手C 不一定成立。

传递性不显然的原因在于，比较时会发生一些细微的变化。例如假设字符串A=a9, 字符串B=a10, 字符串C=abc。 A在和B比较时，A中的'9'和B中的'10'被当成了数字9和10进行比较，得出 A < B; 而在B和C比较时，B中的'10'被当成了字符进行比较，得出B < C; 同样在A和C比较时，A中的'9'被当成了字符进行比较，得出A < C。一会看成数字，一会看成字符，会不会影响到传递性呢？

其实我们可以换个角度看问题。我们可以把字符串任意连续的数字看成一个字符，把我们想象出来的新增字符放到下面想象的字符顺序表。由于数字有无穷多个，所以下面的表其实中间的数字字符有无穷多个的。这样只需要根据这个表的字符顺序进行大小比较，那么和上面的算法的大小比较的结果是一致的。从而容易看出，传递性是成立的。

想象的字符顺序表