0906--拼接出最小整数

题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
程序输出：联接成的多位数

例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）

 

算法思想:

1. 首先找出每个整数的唯一标识作为该整数的前缀，组成一个前缀和整数值相对应的哈希表

2. 对前缀进行排序(直接插入排序): 从最高位开始比，如果对应位相同则比较下一位，如果某个前缀已经比完最后一位了，那么用最后一位和另一的数的下一位（以及再下一位)比较，直到比出大小，看哪个大就排在后面。

3. 输出hash表中所有值，则找出了最小整数序列。

 

空间复杂度：O(n)