`

关于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;
	}
	
	@Override
	public 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();
	}

	@Override
	public 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());
		}
	}
}



分享到:
评论

相关推荐

    android10k面试题

    ### Android 10K 面试题解析 #### 一、Android系统架构 Android系统采用了层次化的架构设计,从上至下分为四个主要层级: 1. **应用程序层(Application Layer)**:这一层包含了预装的应用程序以及第三方开发者...

    EPF10K10LC84-4芯片资料

    EPF10K10LC84-4芯片资料he industry’s first embedded programmable logic device (PLD) family, providing System-on-a-Programmable-Chip (SOPC) integration – Embedded array for implementing ...

    Kadid-10k 图像质量评价IQA(Image Quality Assessment)数据集

    我们创建了两个数据集,康斯坦茨人为扭曲图像质量数据库(kADID-10k)和康斯坦茨人为扭曲图像质量集(kADis-700k)。前者包含81个原始图像,每个图像在5个水平上被25个失真降级。后者有140,000个原始图像,每个有5个降级...

    2011年4月张孝祥移动计费系统(月薪10K面试题).ppt

    2011年4月张孝祥移动计费系统(月薪10K面试题).ppt 超详细 紧密~ 32页 张老师的绝密课件

    EPF10K10LC84-4(84)+AT89C2051+TLC5510+IDT7205原理图设计资料

    这份资料主要涵盖了基于EPF10K10LC84-4(84) FPGA、AT89C2051 单片机、TLC5510 模拟到数字转换器以及IDT7205 时钟发生器的电路设计。下面将分别对这些关键器件进行详细讲解,并探讨它们在原理图设计中的应用。 1. ...

    cocostuff10k, ( 过期) COCO 10K 数据集的官方主页.zip

    cocostuff10k, ( 过期) COCO 10K 数据集的官方主页 coco-stuff dataset dataset dataset ( 过时的),Ferrari,Ferrari,Ferrari,Ferrari,Ferrari,Ferrari,Ferrari,Ferrari,Ferrari 。概述

    基于EPF10K10LC84-3的FPGA最小系统

    基于EPF10K10LC84-3的FPGA最小系统,是电子设计自动化(EDA)领域中的一项重要实践课题,旨在让学生通过实际操作,深入理解FPGA(Field Programmable Gate Array,现场可编程门阵列)的原理与应用。本报告详细介绍了...

    ath10k-firmware, ath10k的固件文件,mac80211 802.11交流设备的驱动程序.zip

    ath10k-firmware, ath10k的固件文件,mac80211 802.11交流设备的驱动程序 ath10k-firmware这些是ath10k的最新固件文件,用于 QCA988x 。QCA6174.QCA99XX和类似的mac80211驱动程序。 下载ath10k映像的官方位置来自...

    ath10k-firmware-2019-10-03-d622d160.tar.xz

    openwrt中的dl目录文件,编译工具链、目标平台的软件包等需要下载的文件

    BI常见面试题

    BI 常见面试题汇总 BI(Business Intelligence)是企业智能化的核心组件,涉及到数据分析、报表设计、数据仓库、数据挖掘等多个方面。面试BI相关岗位时,需要具备丰富的知识储备和实践经验。以下是BI常见面试题汇总...

    10K 1% 3950 (-30-300℃).doc

    NTC温度传感器,温度电阻值R/T对照表,温度范围零下三十摄氏度至三百摄氏度的R/T对照表

    初级前端面试题总结(面试,10K以上,初级前端)

    适合刚刚毕业的学生寻找实习,以及培训班毕业出来寻找工作的前端工程师。 以上都是本人在杭州面试下来的面试题总结,保真。目前就职于一家自研公司,目前11k+13 本人也是培训班出来的

    MSRA10K_Imgs_GT.zip

    《MSRA10K_Imgs_GT:深度学习中的图像分割与显著性检测》 MSRA10K_Imgs_GT 是一个专为图像分割和显著性检测任务设计的大型数据集,它包含了10,000张高质量的图像,其中一半是原始图像,另一半则是经过人工精细分割...

    下载 Corel10k图像库Java代码

    该文件包括下载Corel10k图像库的Java代码,也包含Java代码所需要的jar包,可以方便的下载完整的、真正的 Corel10K图像库,该图像库包含100类图像,总共10000幅图像,都已经分好类。

    EPF10K10LC84-4

    "EPF10K10LC84-4 数字钟设计" 本设计报告旨在使用 EPF10K10LC84-4 芯片,设计一个动态数码管显示的数字钟,学习使用 EDA 开发工具 MAX+PLUS II 和 VHDL 语言,熟悉日历和数字钟的原理和设计过程。 知识点一:EDA ...

    128道Python面试题.pdf

    "128道Python面试题.pdf" Python基础知识点: 1. 文件操作:文件读写、文件类型、文件权限等。 2. 模块与包:Python中的模块和包、模块的导入、模块的使用等。 3. 日期处理:Python中的日期处理、日期格式化、日期...

    ohmyzsh:使用powerlevel10k和插件安装oh-my-zsh

    **ohmyzsh:使用Powerlevel10k和插件安装oh-my-zsh** Oh My Zsh是一款流行的开源shell框架,用于增强Unix或Linux系统的Zsh shell体验。它提供了丰富的预配置主题、插件和自动补全功能,使得日常命令行操作更加便捷...

    GoodBooks, 推荐你可能喜欢的好书.zip

    "GoodBooks"是一个开源项目,其目标是推荐用户可能喜欢的书籍。开源意味着该项目的源代码是公开的,允许开发者查看、学习甚至修改代码来适应自己的需求。这种开放的特性鼓励了社区协作和创新,使得项目能够持续改进...

    关于python的面试题

    Python基础 文件操作 1.有一个jsonline格式的文件file....企业面试题 15.python新式类和经典类的区别? 16.python中内置的数据结构有几种? 17.python如何实现单例模式?请写出两种实现方式? 18.反转一个整数,例如-123

    月薪10k 阿里腾讯大厂java面试题

    本文将深入探讨Java方向的核心知识点,特别是针对面试的要点。 首先,Servlet是Java Web开发中的核心概念,它是一种服务器端的组件,用于处理HTTP协议,允许开发者扩展Web服务器的功能。Servlet的运行原理涉及以下...

Global site tag (gtag.js) - Google Analytics