现有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接口

解：

Java代码 这个是最好最方便的办法
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 = src[p++];
else
dest = src[q++];
}
}

单就问题本身，如果数据完整，
班级名称是顺序的，没有间隔，
可以直接用一个Map<String, List<>>来解决
Map.put(班级名, List)
List是可以add(index, Object)的，add(0, 老师)
这样一个遍历下来，Map塞满也就塞满了
然后拼接字符串，就可以打印出来了

如果班级名称不严格，比如有间断，
单独对Map里面的keySet排序，再从map里面取出打印，也行哦

我也是相同的思路

使用LinkedHashMap,这样不需要对keySet排序
遍历List：
将每个user的classname作为key ，将List<user>作为value,同时排序List<user> (如果碰到type为老师的就跟第一个user交换)
end
for i=>0 – 10W：
List<User> users = map.get(i);
遍历users:
打印
end:

也可以直接对List冒泡（只会这么一种排序。。）
对算法效率计算方式不大清楚，也不知道map效率是否有排序快

现有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接口

解：

Java代码 这个是最好最方便的办法
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 = src[p++];
else
dest = src[q++];
}
}

单就问题本身，如果数据完整，
班级名称是顺序的，没有间隔，
可以直接用一个Map<String, List<>>来解决
Map.put(班级名, List)
List是可以add(index, Object)的，add(0, 老师)
这样一个遍历下来，Map塞满也就塞满了
然后拼接字符串，就可以打印出来了

如果班级名称不严格，比如有间断，
单独对Map里面的keySet排序，再从map里面取出打印，也行哦

我也是相同的思路

使用LinkedHashMap,这样不需要对keySet排序
遍历List：
将每个user的classname作为key ，将List<user>作为value,同时排序List<user> (如果碰到type为老师的就跟第一个user交换)
end
for i=>0 – 10W：
List<User> users = map.get(i);
遍历users:
打印
end:

也可以直接对List冒泡（只会这么一种排序。。）
对算法效率计算方式不大清楚，也不知道map效率是否有排序快