算法思想一：贪心排序

解题思路：

基本思路：
根据贪心的思路，字典序小的放在前面。比如"abc"放到"bca"的前面更好。
但是这样有个问题，就是字符串长度的问题，比如"bc""bca"此时应该将字典序大的"bca"放到前面。
为了解决此问题，不能直接按字典序排序，但是可以按照两个字符串连起来后的字符串的字典序排序。
比如"bc""bca",比较"bcbca"和"bcabc"那个字典序小，来确定"bc""bca"的位置

利用编程语言中的排序函数加排序规则实现字符串拼接生成字典序最小字符

代码展示：

JAVA版本 
import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    // 字典序最小判断函数
    public static class MyComparator implements Comparator<String>{
        public int compare(String a,String b){
            return (a+b).compareTo(b+a);
        }
    }
    
    public String minString (String[] strs) {
        // write code here
        // 特殊情况
        if(strs==null || strs.length==0){
            return "";
        }
        // 字符串数组排序，规则 new MyComparator()
        Arrays.sort(strs,new MyComparator());
        StringBuffer res=new StringBuffer();
        // 拼接生成字符串
        for(int i=0;i<strs.length;i++){
            res.append(strs[i]);
        }
        return res.toString();
    }
}

Python版本 

from functools import cmp_to_key
class Solution:
    def minString(self , strs ):
        # write code here
        if not strs or len(strs) == 0:
            return ""
        # 重载sort排序函数,定义排序规则key
        strs = sorted(strs, key=cmp_to_key(lambda x,y: 1 if x+y > y+x else -1))
        # 拼接字符串
        return ''.join(strs)

复杂度分析

时间复杂度：N表示字符串数组的长度，自带排序函数时间，拼接字符串时间

空间复杂度：仅使用常数级变量空间

算法思想二：贪心排序优化

解题思路：

方法一主要是使用语言自带的排序函数，方法二是自己实现排序过程，主要是以快速排序为对象实现，其他的均和方法一相同

快速排序图解：

代码展示：

C++版本 
class Solution {
public:
    /**
     * 
     * @param strs string字符串vector the strings
     * @return string字符串
     */
    static bool cmp(const string &a, const string &b) {
        return (a+b) <= (b+a);
        // 这里需要注意, 要写成小于等于, 因为排序的时候, 如果遇到了相等的情况
    }
    // quicksort 快速排序算法, 待排序区间为[start, end]
    void quicksort(vector<string> &strs, int start, int end) {
        if (start >= end) return; // 递归终点: 区间不合法(长度<=0)
        int i = start, j = end;
        string p = strs[i]; // 中轴随便取,本题中取最左边的元素
 
        while (i < j) {
            // 右边的字符串如果大于等于基准, 则j指针往左走
            while (i<j && cmp(p, strs[j])) j--;
            // j指针推到第一个「严格小于」基准的, 将i换过去
            strs[i] = strs[j];
 
            // 逻辑同上, 直到ij相遇
            // 这里如果cmp函数不写等号, 有可能ij永不相遇
            while (i<j && cmp(strs[i], p)) i++;
            strs[j] = strs[i];
        }
 
        // ij相遇时, 就是一轮快速排序完成, 终点赋值为中轴
        strs[i] = p;
        quicksort(strs, start, i-1);
        quicksort(strs, i+1, end);
    }
    
    string minString(vector<string>& strs) {
        // write code here
        int n = strs.size();
        quicksort(strs, 0, n-1); // 对数组strs排序
        string res;
        // 拼接生产字符串输出
        for (auto a : strs) {
            res += a;
        }
        return res;
    }
};

复杂度分析

时间复杂度：N表示字符串数组的长度，排序函数时间，拼接字符串时间

空间复杂度：仅使用常数级变量空间