先用上面的一张图说明逻辑，这就是递归的逻辑。

xy排序就相当于在x的空位插上y，x只有两个空位，y插前面得带yx，y插后面得到xy

xyz排序就相当于在xy排序的所有结果插上z，结果如图

代码实现如下

public static void main(String[] args){

List list = sort("xy","k");

for(String s:list){

System.out.println(s);

}

}

public static List sort(String main,String insert){

List result  = new ArrayList<>();

if(main.length() == 1){

result.add(main+insert);

result.add(insert+main);

}else{

List lastResult = sort(main.substring(0,main.length()-1),main.substring(main.length()-1));

for(String s:lastResult){

int insertIndex = 0;

while(insertIndex<=s.length()){

if(insertIndex == 0){

result.add(insert+s);

}else if(insertIndex == s.length()){

result.add(s+insert);

}else{

result.add(s.substring(0, insertIndex)+insert+s.substring(insertIndex, s.length()));

}

insertIndex++;

}

}

}

return result;

};

测试结果是：zxy;xzy;xyz;zyx;yzx;yxz;

另外测试abcd排序结果是：dcab;cdab;cadb;cabd;dacb;adcb;acdb;acbd;dabc;adbc;abdc;abcd;dcba;cdba;cbda;cbad;dbca;bdca;bcda;bcad;dbac;bdac;badc;bacd;