关于10K面试题的组合排序-归并排序
package com.kevin.demo;import java.util.ArrayList;import java.util.List;import org.apache.commons.lang.builder.EqualsBuilder;import org.apache.commons.lang.builder.HashCodeBuilder;/** * @author <a href="mailto:foohsinglong@gmail.com">kevin.long</a> * @description 2011-12-07 02:14:58 */public class TestUser {/** * 班级 */private Integer classes; /** * 类型(teacher or student) */private String type;/** * 姓名 */private String name;public TestUser(Integer classes, String type, String name){this.classes = classes;this.type = type;this.name = name;}@Overridepublic boolean equals(Object other) {if(!(other instanceof TestUser)){return false;}TestUser testUser = (TestUser)other;return new EqualsBuilder().append(classes, testUser.getClasses()).append(type, testUser.getType()).append(name, testUser.getName()).isEquals();}@Overridepublic int hashCode() {return new HashCodeBuilder().append(classes).append(type).append(name).toHashCode();}public String getType() {return type;}public void setType(String type) {this.type = type;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Integer getClasses() {return classes;}public void setClasses(Integer classes) {this.classes = classes;}/** * 归并排序法 * @param users 需要排序集合 */public static void quickSort(List<TestUser> users) {quickSort(users, 0, users.size() - 1);}private static void quickSort(List<TestUser> users, int start, int end) { int left = start; int right = end - 1; int pivot = users.get(end).getClasses(); int typeKey = users.get(end).getName().hashCode(); while (left < right) { if (users.get(left).getClasses() <= pivot) { left++; continue; } if (users.get(right).getClasses() > pivot) { right--; continue; } swap(users, left++, right); } if (users.get(left).getClasses() < pivot) { left++; }else if(users.get(left).getClasses() == pivot){ if(users.get(left).getName().hashCode() < typeKey){ left++; } } swap(users, left, end); if(left - 1 > start) { quickSort(users, start, left - 1); } if(left + 1 < end) { quickSort(users, left + 1, end); }}private static void swap(List<TestUser> userSwaps, int a, int b) {TestUser t = userSwaps.get(a);userSwaps.set(a, userSwaps.get(b));userSwaps.set(b, t);}/** * 现有List集合中存放有10W个无序的User（属性：classes 班级；type 身份【学生 or 老师】；name 姓名）对象。 * 要求：用JAVA实现将List集合中的User对象按照1-n班并且每个班的老师必须放在该班级学生的前面输出。 * （一个班只有一个老师，一个班存在多个老师，这两只情况可以分开用两个算法实现，也可以用一个算法实现，但要考虑性能）例如下面格式： * 1班 老师 张三 * 1班 学生 李四 * 1班 学生 王五 * 2班 老师 张三2 * 2班 学生 李四2 * 2班 学生 王五2 */public static void main(String[] args) {List<TestUser> users = new ArrayList<TestUser>();users.add(new TestUser(1, TestUserType.TEACHER, "张三"));users.add(new TestUser(2, TestUserType.TEACHER, "张三2"));users.add(new TestUser(1, TestUserType.STUDENT, "李四"));users.add(new TestUser(2, TestUserType.STUDENT, "李四2"));users.add(new TestUser(1, TestUserType.STUDENT, "王五"));users.add(new TestUser(2, TestUserType.STUDENT, "王五2"));long start = System.currentTimeMillis();quickSort(users); //排序优先级 班级,老师System.out.println("耗时:" + (System.currentTimeMillis() - start));for(TestUser user : users){System.out.println(user.getClasses() +"\t"+ user.getType() +"\t"+ user.getName());}}}