一个特殊序列的排序问题
有一个关于排序的问题：
类似于在学校时的站队：在一次排好队后，老师可能是这么跟大家说的：“记住自己前面的是谁,以后按这个顺序排！”
抽象出来就是，比如有一个队列[1，2，3]，在排序的时候，1和2比较可以知道1在2前面,2和3比较也可以知道2在3前面，但1和3比较是不知道结果的。这样一来，我们的排序算法/比较器（还是不能用比较器了？）该怎么写呢？
有一个关于排序的问题：
类似于在学校时的站队：在一次排好队后，老师可能是这么跟大家说的：“记住自己前面的是谁,以后按这个顺序排！”
抽象出来就是，比如有一个队列[1，2，3]，在排序的时候，1和2比较可以知道1在2前面,2和3比较也可以知道2在3前面，但1和3比较是不知道结果的。这样一来，我们的排序算法/比较器（还是不能用比较器了？）该怎么写呢？
这里，只知道：A<B1,A<B1,B2<C1,B2<C2
也就是说排序排成：[A，B2，C1，C2，B1]
或者[A，B2，B1，C1，C2]
或者[A，B1，B2，C1，C2]
或者[A，B1，B2，C2，C1]
都是可以的。这就有点像树了
这里，只知道：A <B1,A <B2,B2 <C1,B2 <C2
也就是说排序排成：[A，B2，C1，C2，B1]
或者[A，B2，B1，C1，C2]
或者[A，B1，B2，C1，C2]
或者[A，B1，B2，C2，C1]
都是可以的。这就有点像树了
用代码说话：
class Item implements Comparable<Item>{
private int i;
public Item(int i) {
super();
this.i = i;
}
public int getI() {
return i;
} public void setI(int i) {
this.i = i;
} @Override
public int compareTo(Item o) {
int c = i - o.i;
if (c == 1 || c == -1) {
return c;
}
return 0;
}
@Override
public String toString() {
return String.valueOf(i);
}
}那问题就是：给定一个Item的集合，如何得到一个该集合的序列，使得序列中任意元素都小于等于（compareTo返回结果小于等于零）它后面的元素。
1）为什么是TreeMap?
2)"根据元素可以从Map中求得其序号，比较序号就可以了。" + "无论如何你得有一个预设的序列吧。也就是说每一个元素都有一个唯一的序号于之对应。"
=> 原来序列就是有序的？？ 我上面给出是有序的是为了说明要求啊
package test;import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class Sorter {
public static void main(String[] args) {
List<Item> list = new ArrayList<Item>();
for (int i = 0; i < 10; i++) {
list.add(new Item((int) (Math.random()*12)));
}
Collections.shuffle(list);
System.out.println("排序前:" + Arrays.toString(list.toArray()));
sort(list);
System.out.println("排序后:" + Arrays.toString(list.toArray()));
} private static void sort(List<Item> list) {
// TODO Auto-generated method stub
}
}package test;public class Item {
private int i;
public Item(int i) {
super();
this.i = i;
}
public int compareTo(Item o) {
int c = i - o.i;
if (c == 1 || c == -1) {
return c;
}
return 0;
}
@Override
public String toString() {
return String.valueOf(i);
}
}
如上代码，只允许在Sorter的sort方法内添加代码的限制下，如何能让sort后list有顺序？
class Item implements Comparable<Item>{
private int i;
public Item(int i) {
super();
this.i = i;
}
public int getI() {
return i;
} public void setI(int i) {
this.i = i;
} @Override
public int compareTo(Item o) {
int c = i - o.i;
if (c == 1 || c == -1) {
return c;
}
return 0;
}
@Override
public String toString() {
return String.valueOf(i);
}
}
public class Sorter{
private HashMap<Item,Integer> originalList=new HashMap<Item,Integer>();
Sorter(List<Item> myList){
for(int i=0;i<myList.size();i++){
originalList.put(myList.get(i),i);
}
}
public void sort(List<Item> myList){
Collections.sort(myList,new comparator());
}
public class comparator implements Comparator<Item>{
public int compare(Item i1,Item i2){
return originalList.get(i1)-originalList.get(i2);
}
public boolean equals(Object o){
return false;
}
}
public static void main(String[] args){
Random rand=new Random();
List<Item> list = new ArrayList<Item>();
for (int i = 0; i < 10; i++) {
list.add(new Item(rand.nextInt(10)));
}
Sorter mySorter=new Sorter(list);
System.out.println("排序之前");
System.out.println(list);
Collections.shuffle(list);
for(int i=0;i<3;i++){
System.out.println(list.remove(i)+"被删除了");
}
mySorter.sort(list);
System.out.println("排序之后");
System.out.println(list);
}
}
F:\java>java Sorter
排序之前
[3, 1, 6, 3, 4, 5, 7, 5, 6, 2]
5被删除了
2被删除了
5被删除了
排序之后
[3, 1, 6, 3, 4, 7, 6]
就是：
有若干集合 A B C
其中
A={a}
B={b1, b2}
C={c1, c2}
b1,b2之间没有明确的顺序，同样c1,c2也没有明确的顺序
已知排列 A->B->C
现在要将 集合中的所有元素按上面A->B->C的顺序填回去。
那么：
可以先将ABC排序，然后再对每个集合求出其所有元素可能的排列，最后把两个结果并在一起。
A={a}
B={b2}
C={b1, c1, c2}
b1,b2之间没有明确的顺序，同样b1,c1,c2也没有明确的顺序
排列 A->B->C
1） 把我的例子里的compareTo方法直接等同于基本/标准的比较方法了。
我已经明确说了，这是一个特殊的排序问题。一般来说，compareTo返回0指的是两者相同/等价；但我这里返回0可能是没法在两者间比较。2）我给的123,ABC例子仅仅作为一个说明方法。能不能把Item做为一个对象来看待啊（而且对象里面的东西是没有提供getter&setter的）
1）代码里public int compareTo(Item o) {
int c = i - o.i;
if (c == 1 || c == -1) {
return c;
}
return 0;
}
这个方法只能用来作排序后是自然序列的比较方法。因为如果中间漏掉一些数据的话它返回的结果就不对了。而且这个方法没有考虑两者相等的情况（那就只考虑没有相等的情况吧）2）关于上面提到的“简单实现”
也就是说我自己已有一个办法去实现，如下：
private static void sort(List<Item> list) {
for (int i = 0; i < list.size()-1; i++) {
for (int j = 0; j < list.size()-1; j++) {
for (int k = j; k < list.size(); k++) {
if (list.get(j).compareTo(list.get(k)) > 0) {
Item temp = list.get(j);
list.set(j, list.get(k));
list.set(k, temp);
}
}
}
}
}很明显，这里用了三层循环，而且里面的两层循环就是大家所熟悉的冒泡排序~
以上，我觉得已经尽可能的表达清楚了。如果还是不明白，那只能说明我表达有限，没有办法了~
private static void sort(List<Item> list) {
List<Item> ll = new LinkedList<Item>();
ll.add(list.remove(0));
for (int j = 0, size = list.size(); j < size && list.size() > 0; j++) {
int pre = -1, next = -1;
for (int k = 0; k < list.size(); k++) {
if (list.get(k).compareTo(ll.get(0)) < 0) {
pre = k;
} else if (list.get(k).compareTo(ll.get(ll.size()-1)) > 0) {
next = k;
}
}
if (pre >= 0) {
ll.add(0, list.get(pre));
}
if (next >= 0) {
ll.add(list.get(next));
}
if (pre >= 0 && next >= 0) {
list.remove(pre > next ? pre : next);
list.remove(pre > next ? next : pre);
} else {
if (pre >= 0) {
list.remove(pre);
}
if (next >= 0) {
list.remove(next);
}
}
}
list.addAll(ll);
}
这对于完全有序的集合是对的。
但是类似于[1,2,3,5,6,7]这种集合就出错了~注：我提到的什么例子，都是以它的有序序列列出来的；排序前可能是任意顺序的。
[1,2,3,5,6,7]的另一种顺序是[5,6,7,1,2,3]
在上面的
list.addAll(ll);
前面加上：
if (!list.isEmpty()) {
sort(list);
}
就可以了我再想想如果有相等元素的情况就OK了~
private static void sort(List list) {
for (int i = 0; i < list.size() - 1; i++) {
for (int j = i+1; j < list.size(); j++) { if ((list.get(j)).compareTo( list.get(i) ) < 0 ) {
Item temp = list.get(j);
list.set(j, list.get(i));
list.set(i, temp);
}
}
} }
不要想当然好吧你明白我的要求&试过你的代码？