字符串排序算法， 哪位大侠给看下...

Question

要求 ： 用户输入"1234" 
返回结果
1324
1342
1432
1423
1243
1234
2431
2413
2143
2134
2314
2341
3142
3124
3214
3241
3421
3412
4213
4231
4321
4312
4132
4123
这样， 返回这个字符串中字符所有能组成的字符串集合小弟写了一个，但是4位字符以下还行，多了以后就有地方少循环了。public static void main(String[] args) {
TestReverse t = new TestReverse();
String str = "1234";
List<String> list = t.permutation(str);
System.out.println("共有数据:"+list.size());
for(int i = 0 ; i < list.size() ; i++){
System.out.println(list.get(i));
}
}


/**
 * 排列字符串
 * @param str 源字符串
 * @return List<String>
 */
public List<String> permutation(String str){
//创建返回集合,避免空指针
List<String> list = new ArrayList<String>();
try{
//创建char数组
char [] c = str.toCharArray();
//颠倒字符串用
char b = 0;
//遍历char数组，让每个字符都当一首头字符
for (int i = 0; i < c.length; i++) {
//颠倒除了首字符外所有字符串
rvd(c,list);
b = c[0];
//颠倒首字符
for(int j = 0 ; j < c.length-1 ; j++){
c[j] = c[j+1];
}
c[c.length-1] = b;
}
}catch(Exception e){
System.out.println("翻转字符串错误:"+e);
}
return list;
}


/**
 * 颠倒字符串
 * @param c 字符集合
 * @param list 返回字符串集合
 * @return List<String>
 */
public List<String> rvd(char[] c  , List<String> list){
try{
//克隆一个字符集合给m , 避免影响到源字符集合
char [] m = c.clone();
//用以当做第三方字符 ， 颠倒字符用
char b = 0;
//除了第一个字符外，所有字符全部颠倒一回
for(int i = 1 ; i < m.length ; i++){
for(int j = 1 ; j < m.length-1 ; j++){
b = m[j];
m[j]=m[j+1];
m[j+1]=b;
list.add(new String(m));
}
}
}catch(Exception e){
e.printStackTrace();
}
return list;
}

Answer 1

全排列网上很多啊·baidu一下·

Answer 2

不就是全排列么
核心思想是：依次取出字符串中每一个元素，放在第一位，完后对剩下的元素进行全排列（递归），最后把所有的情况罗列出来，不重复造轮子
import java.util.ArrayList;import java.util.List;public class Permutation {private static List<Integer> list = new ArrayList<Integer>();private static int total;/*** @param args*/public static void main(String[] args) {
String str = "1234";
for(int i = 0; i < str.length(); i++)
list.add(Integer.parseInt(str.substring(i,i + 1)));perm(list, new ArrayList<Integer>());System.out.println("total: " + total);}private static void perm(List<Integer> list, List<Integer> removed) {            int length = list.size();if (length == 1) {for (int value : removed) {System.out.print(value + " ");}System.out.println(list.get(0));total++;} else {for (int i = 0; i < length; i++) {                        List<Integer> temp = new ArrayList<Integer>();temp.addAll(list);            temp.remove(i);List<Integer> holder = new ArrayList<Integer>();holder.addAll(removed);    holder.add(list.get(i));perm(temp, holder);}}}}

Answer 3

递归和迭代的本质是一样的，但高手是很少写递归的，递归编译器还是会解析为迭代再执行，同时消耗很大资源。不过递归容易理解且代码简单。
//写个递归的伪码
fun(a){
if(length==1) print(a[0])
if(length==2) {print(a[0],a[1]),print(a[1],a[0])}
}
if(length>2){
  for (i 0:length-1){
     print(a[i]),a(a.remove(a[i]))
  }
}

Answer 4

public static void main(String[] agrs) throws Exception {
List<String> list = new ArrayList<String>(); list.add("1");
list.add("2");
list.add("3");
 list.add("4");
sort(list,""); }
static String temp="";
public static void sort(List<String> cs ,String s) {
for(int i=0;i<cs.size();i++){

if(cs.size()==1){
temp=s+cs.get(i);
System.out.println("resault:"+temp);

}
else{
 temp=s+cs.get(i);

List<String> list = new ArrayList<String>();
for(int z=0;z<cs.size();z++){
if(!cs.get(i).equals(cs.get(z))){
list.add(cs.get(z));

}
}

sort(list,temp);
}
} }

Answer 5

public static void main(String[] agrs) throws Exception {
List<String> list = new ArrayList<String>(); list.add("1");
list.add("2");
list.add("3");
 list.add("4");
sort(list,""); }
static String temp="";
public static void sort(List<String> cs ,String s) {
for(int i=0;i<cs.size();i++){

if(cs.size()==1){
temp=s+cs.get(i);
System.out.println("resault:"+temp);

}
else{
 temp=s+cs.get(i);

List<String> list = new ArrayList<String>();
for(int z=0;z<cs.size();z++){
if(!cs.get(i).equals(cs.get(z))){
list.add(cs.get(z));

}
}

sort(list,temp);
}
} }

Answer 6

递归，大家一同进步。应该是你想要的
public class tester {

static int size;
static int count;
static char[] arrChar = new char[100];

public static void main(String[] args) throws IOException{
System.out.print("Enter a word:");
String input = getString();
size = input.length();
count = 0;
for(int j=0;j<size;j++)
arrChar[j]=input.charAt(j);
doAnagram(size);
} public static void doAnagram(int newSize){
if(newSize==1)
return;
for(int j=0;j<newSize;j++){

doAnagram(newSize-1);
if(newSize==2)
displayWord();
rotate(newSize);
}
}

public static void rotate(int newSize){
int j;
int position = size-newSize;
char temp = arrChar[position];
for(j=position+1;j<size;j++)
arrChar[j-1]=arrChar[j];
arrChar[j-1] = temp;
}

public static void displayWord(){
if(count<99)
System.out.print(" ");
if(count<9)
System.out.print(" ");
System.out.print(++count+" ");
for(int j=0;j<size;j++)
System.out.print(arrChar[j]);
System.out.print(" ");
System.out.flush();
if(count%6==0)
System.out.println("");
}

public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}

Answer 7

public class AnagramApp {

static int size;
static int count;
static char[] arrChar = new char[100];

public static void main(String[] args) throws IOException{
System.out.print("Enter a word:");
String input = getString();
size = input.length();
count = 0;
for(int j=0;j<size;j++)
arrChar[j]=input.charAt(j);
doAnagram(size);
} public static void doAnagram(int newSize){
if(newSize==1)
return;
for(int j=0;j<newSize;j++){

doAnagram(newSize-1);
if(newSize==2)
displayWord();
rotate(newSize);
}
}

public static void rotate(int newSize){
int j;
int position = size-newSize;
char temp = arrChar[position];
for(j=position+1;j<size;j++)
arrChar[j-1]=arrChar[j];
arrChar[j-1] = temp;
}

public static void displayWord(){
if(count<99)
System.out.print(" ");
if(count<9)
System.out.print(" ");
System.out.print(++count+" ");
for(int j=0;j<size;j++)
System.out.print(arrChar[j]);
System.out.print(" ");
System.out.flush();
if(count%6==0)
System.out.println("");
}

public static String getString() throws IOException{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
}

Answer 8

package com.xuz.datastruct.recursion;public class AnagramApp {
private char[] chArray = new char[100];
private int size ;
private int count ;

public static void main(String[] args) {
String str = "1234";
new AnagramApp().play(str);
} public void play(String str){
chArray = str.toCharArray();
size = str.length();
doAnagram(size);
} private void doAnagram(int size2) {
if (size2 == 1) {
return ;
}

for (int i = 0; i < size2; i++) {
doAnagram(size2-1);
if (size2 == 2) {
displayWord();
}
rotate(size2);
}
} private void rotate(int size3) {
int i ;
int pos = size - size3;
char temp = chArray[pos];
for (i = pos + 1; i < size; i++) {
chArray[i-1] = chArray[i];
}
chArray[i - 1] = temp;
} private void displayWord() {
if (count < 99) {
System.out.print(" ");
}
if (count < 9) {
System.out.print(" ");
}
System.out.print(++count + " ");
for (int i = 0; i < size; i++) {
System.out.print(chArray[i]);
}
System.out.print(" ");
if (count % 6 == 0) {
System.out.println();
}
}
}
递归的。