刚刚做了阿里的模拟笔试题,算法题是一道多级排序的问题。这题其实以前就做过,之前测评的时候也是同一道题目。
这题的意思就是给条码排序,条码分三部分,主要根据第一部分从小到大排序,第一部分相同的情况下按第二部分从后往前排序,第二部分相同的情况下按第三部分从大到小排序。
举个例子,比如有下面这样五个条形码:
1 | 123AB456 |
按照排序规则,最后排序之后应该是像下面这样:
1 | 123BA444 |
一开始我想这怎么排序,如果一部分一部分排的话,那第一部分排完之后,再排第二部分,之前排的不是乱掉了么。。
后来突然想到,其实这三部分的重要程度是递减的,最主要是根据第一部分来排的,所以可以换个角度思考,先从最不重要的第三部分开始排,然后排第二部分,最后排第一部分。这里面最关键的就是前面已经排好的怎么能保持顺序,这时候我们就应该要想到排序算法所谓的“稳定排序”的特性,即排序前后,两个相同元素的相对位置不会发生变化,这就是我们需要的。
所以我们可以使用冒泡排序这种稳定排序算法来对这三部分进行排序,并且从最不重要的第三部分开始排序。
以下就是最终的算法:
1 | #!/usr/bin/env python |
测试一下: