java一道10k面试题，看看值不值？？？

现有List集合中存放有10W个无序的User（属性：classes 班级；type 身份【学生 or 老师】；name 姓名）对象。要求：用JAVA实现将List集合中的User对象按照1-n班并且每个班的老师必须放在该班级学生的前面输出。（一个班只有一个老师，一个班存在多个老师，这两只情况可以分开用两个算法实现，也可以用一个算法实现，但要考虑性能）例如下面格式：
1班 老师 张三
1班 学生 李四
1班 学生 王五
1班 学生 刘六

……

2班 老师 张三2
2班 学生 李四2
2班 学生 王五2
2班 学生 刘六2

……

3班 老师 张三3
3班 学生 李四3
3班 学生 王五3
3班 学生 刘六3

……

 

备注：自己实现算法，不能用Comparable和Comparator接口

1、基数排序,如何做到高效的排序(时间复杂度n^2以下,空间复杂度1或时空都为n),应该很有趣
2、低效快捷的做法,实现Comparable/Conparator接口,通过Collections.Sort()排序,实质是快速排序

好吧,假如仅仅需要班级和身份有序,名字可以无序，那么可以在时间n,空间1的复杂度内完成。

简单，不用任何排序，只要按班级调整老师和学生的位置即可。

分成1-n各班可看作将10w记录分成1-n个段。遍历时调整位置即可。

各位高手可以将算法贴出来瞧瞧

好吧，我来抛砖引玉，用最简单Collections.sort实现啦一把：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;


public class Sort {
	List<User> users;
	enum Type{Student, Teacher};

	class User implements Comparable<User>{
		int id;
		String name;
		Type t;

		public User(int id, String name, Type t) {
			this.id  = id;
			this.name = name;
			this.t = t;
		}

		@Override
		public int compareTo(User user) {
			if(this.id < user.id) {
				return -1;
			} else if (this.id == user.id) {
				if(this.t == Type.Teacher)
					return -1;
				if(user.t == Type.Teacher)
					return 1;
				return 0;
			} else {
				return 1;
			}
		}
	}

	private List<User> SortList(List<User> users) {
		Collections.sort(users);
		return users;
	}

	@Before
	public void setup() {
		users = new ArrayList<User>();

		users.add(new User(1, "u3", Type.Student));
		users.add(new User(2, "u5", Type.Teacher));
		users.add(new User(3, "u8", Type.Student));


		users.add(new User(2, "u4", Type.Student));
		users.add(new User(1, "u2", Type.Teacher));
		users.add(new User(2, "u6", Type.Teacher));

		users.add(new User(3, "u9", Type.Student));
		users.add(new User(3, "u7", Type.Student));
		users.add(new User(1, "u1", Type.Student));
	}

	@Test
	public void testSort() {
		List<User> sortedList = SortList(users);
		Assert.assertEquals("u2", sortedList.get(0).name);
		Assert.assertEquals("u3", sortedList.get(1).name);
		Assert.assertEquals("u1", sortedList.get(2).name);

		Assert.assertEquals("u5", sortedList.get(3).name);
		Assert.assertEquals("u6", sortedList.get(4).name);
		Assert.assertEquals("u4", sortedList.get(5).name);

		Assert.assertEquals("u8", sortedList.get(6).name);
		Assert.assertEquals("u9", sortedList.get(7).name);
		Assert.assertEquals("u7", sortedList.get(8).name);
	}

}

TreeMap<string,TreeSet<UserBean>> t 
 for(User u :list){

   TreeSet temp =  t.get(u.getClass());
   if(temp==null) temp = new TreeSet();
   
   temp.add(u);
   t.put(u.getClass,temp);

}

我觉得不仅考算法，还考对集合框架的理解，集合类的选择。

//先转换成数组，用jdk源码中提供的一个算法实现排序
/**
*
* @param src 转换到数组的的克隆，用clone深度复制
* @param dest 需要排序的对象数组
* @param low 排序的范围，这里是开始数组索引
* @param high 排序的范围，这里是结束数组索引
* @param off 本例没用到默认0
*/
private static void mergeSort(Object[] src, Object[] dest, int low,
int high, int off) {
int length = high - low;

// 如果长度比较小，直接排序
if (length < 7) {
for (int i = low; i < high; i++)
for (int j = i; j > low
&& ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
swap(dest, j, j - 1);
return;
}

// 二分法递归排序
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);

//具体实现排序的算法
if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}

// 对两个有序的集合进行排序。具体的术语忘了。回去复习下拉
for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid
&& ((Comparable) src[p]).compareTo(src[q]) <= 0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}

其实有更好的方法，就是再开辟一个空间来进行存储，这样就不需要调整位置这么麻烦。