Python花式编程案例集锦（9）：sorted()函数中消失的cmp参数

在之前发布过这样一篇文章Python组合列表中多个整数得到最小整数（一个算法的巧妙实现）。也就是，对于列表中的若干整数，求这些整数前后连接能够组成的最小的整数。严格来说，这个问题主要考查的是算法设计能力。

问题描述：给定一个含有多个整数的列表，将这些整数任意组合和连接，返回能得到的最小值。

算法描述：将这些整数变为相同长度（按最大的进行统一），短的右侧使用个位数补齐，然后将这些新的数字升序排列，补齐后一样大小的数字按原始数据降序排列，排序后，将低位补齐的数字删掉，把剩下的数字连接起来，即可得到满足要求的数字。

当时给出的代码是这样的：

看上去很复杂的样子，能更简单点吗？于是有了下面的代码：

上面实际上就是一行代码计算结果，为了方便阅读，才换了很多行。虽然代码简短了很多，但是对Python函数式编程要有一定了解才能看懂。那么就再来个暴力点的代码吧，在所有排列组成的整数中查找最小整数：

但是上面的代码时间复杂度有点高啊，毕竟要计算全排列，有没有更好的办法呢？下面代码最初版本由浙江温州永嘉县教师发展中心应根球老师提供。

思路倒推容易得到，在最终结果的最小整数的排列中，交换任意两个数字得到的数字都会使得结果变大。假设理想排列是x，也就是说，对于任意i和j都有int(str(x[i])+str(x[j]))<int(str(x[j])+str(x[i]))，这样的话，就变成了一个简单的排序问题。

但是问题又来了，在Python 3.x中，内置函数sorted()和列表方法sort()都取消了cmp参数而只保留了key参数，key参数指定的函数只能接收一个参数而在Python 2.x中的cmp参数指定的函数可以接收两个参数，那肿么办呢？Python标准库funtools中的cmp_to_key()可以帮助完成这个转换。