简单的排序算法
简单扑克排序
题目
A A 2 2 3 3 4 4，一共4对扑克牌。请把他们排成一行。
要求
两个A中间有1张牌，两个2中间有2张牌，两个3中间有3张牌，两个4中间有4张牌。
请填写出所有符合要求的排列中，字典序最小的那个
过程
最先想到的办法就把所有排列组合全部输出，然后去掉不符合要求的，效率极低，垃圾cpu测了一下运行时间3万多ms,直接放弃。
由于一对牌中间的数量是固定的，可以先把对牌的长度定死，符合要求的写入list集合中.
假如给list集合初始化为 "00000000"
这样就需要插入4对牌:
- 400004
- 30003
- 2002
- A0A
每次写入值得时候都是成对的写入，即list.set(i,4) 和list.set(i+5,4)
32A也一样。
代码
List<Integer> list = new ArrayList<Integer>();
list = intial(list);
for(int a=0;a<3;a++){
list.set(a,4);
list.set(a+5,4);
for(int b=0;b<4;b++){
int m = list.get(b);
int n = list.get(b+4);
list.set(b,3);
list.set(b+4,3);
for(int c=0;c<5;c++){
int m1 = list.get(c);
int n1 = list.get(c+3);
list.set(c, 2);
list.set(c+3,2);
for(int d=0;d<6;d++){
int m2 = list.get(d);
int n2 = list.get(d+2);
list.set(d, 1);
list.set(d+2,1);
boolean flag = true;
for(int i:list){
if(i==0) {
flag = false;
break;
}
}
if(flag==true){
for(int i:list){
System.out.print(i);
}
System.out.println();
}
list.set(d, m2);
list.set(d+2,n2);
}
list.set(c, m1);
list.set(c+3,n1);
}
list.set(b,m);
list.set(b+4,n);
}
list = setlin(list);
}
运行时间在5ms左右，发现所有的循环都走了一遍，继续做进一步优化
第一对牌先放进了list集合中，再放的一对牌是不可能放在已经放了牌的位置上的，所以后面的循环也没必要走。所以
代码
package com.yb.test_02;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
/**
* Created by 杨波 on 2016/11/24.
*/
public class Test1 {
private static List<String> list = new ArrayList<String>();
/**初始化00000000*/
public void init(){
for (int i=0;i<8;i++){
list.add("0");
}
}
/**重新初始化为0*/
public void reinit(){
for (int i=0;i<8;i++){
list.set(i,"0");
}
}
/**输出*/
public void output(){
for (String s:list){
System.out.print(s);
}
System.out.println();
}
/**判断算法*/
public void run(){
for (int a=0;a<3;a++){
//同时放两个4
list.set(a,"4");
list.set(a+5,"4");
for (int b=0;b<4;b++) {
//不能在已有的位置上放
if (b != a && b != (a + 1)) {
list.set(b, "3");
list.set(b + 4, "3");
for (int c = 0; c < 5; c++) {
if (c != a && c != (a - 3) && c != (a + 2) && c != b && c != (b + 1) && c != (b - 3) && c!=(b+4)) {
list.set(c, "2");
list.set(c + 3, "2");
for (int d = 0; d < 6; d++) {
if (d != a && d != (a + 5) && d != b && d != (b + 4) && d != c && d != (c + 3) && (d + 2) != a && (d + 2) != (a + 5) && (d + 2) != (b) && (d + 2) != (b + 4) && (d + 2) != (c) && (d + 2) != (c + 3)) {
list.set(d, "A");
list.set(d + 2, "A");
output();
} else {
continue;
}
}
} else {
continue;
}
}
} else {
continue;//如果都牌放不进去，直接进行下一次循环。本次循环内部的循环都不执行。
}
}
reinit();//每次放第一张牌的时候，重新给list置0。
}
}
@Test
public void test(){
long startTime = System.currentTimeMillis();//获取当前时间
init();
run();
long endTime = System.currentTimeMillis();
System.out.println("程序运行时间："+(endTime-startTime)+"ms");
}
}
最终运行时间为1ms。
结果
只有两个，坑爹
4A3A2432
2342A3A4