import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
public class ByteToInputStream {
public static final InputStream byte2Input(byte[] buf) {
return new ByteArrayInputStream(buf);
}
public static final byte[] input2byte(InputStream inStream)
throws IOException {
ByteArrayOutputStream swapStream = new ByteArrayOutputStream();
byte[] buff = new byte[100];
int rc = 0;
while ((rc = inStream.read(buff, 0, 100)) > 0) {
swapStream.write(buff, 0, rc);
}
byte[] in2b = swapStream.toByteArray();
return in2b;
}
}
package others.interesting;
import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import javazoom.jl.decoder.JavaLayerException;
import javazoom.jl.player.Player;
public class MP3Player {
private String fileName;
private Player player;
public MP3Player(String fileName) {
this.fileName = fileName;
}
public void play() {
try {
BufferedInputStream buffer = new BufferedInputStream(
new FileInputStream(fileName));
player = new Player(buffer);
player.play();
} catch (FileNotFoundException e) {
System.err.println("FileNotFoundException:");
e.printStackTrace();
} catch (JavaLayerException e) {
System.err.println("JavaLayerException:");
e.printStackTrace();
}
}
public static void main(String[] args) {
MP3Player mp3Player = new MP3Player(
"C:\\Users\\Athrunwang\\Desktop\\杀死那个石家庄人.mp3");
mp3Player.play();
}
}
package org.study.sort;
import java.util.Arrays;
/**
* 问题描述：
* 吸血鬼数字是指位数为偶数的数字，可以由一对数字相乘而得到，而这对数字各包含乘积的一半位数的数字，
* 其中从最初的数字中选取的数字可以任意排序。
* 例如：
* 1260 = 21 * 60 1827 = 21 * 87 2187 = 27 * 81
* 要求输出所有四位数的吸血鬼数字。
*
* @author heng.ai
*
* 注：参考了CSDN一朋友的写法
*/
public class VampireNumber {
public static void main(String[] args) {
for(int i = 1; i < 100; i++){
for(int j = i+1; j < 100; j++){
//只要求输出四位数
if(i * j >= 1000){
String a = i + "" + j;
String b = i * j + "";
if(equal(a, b)){
System.out.printf("%d * %d = %d", i, j, i*j);
System.out.println();
}
}
}
}
}
//判断两个字符串包含的数字是否一致
private static boolean equal(String a, String b) {
//先排序
char[] as = a.toCharArray();
char[] bs = b.toCharArray();
Arrays.sort(as); //排序
Arrays.sort(bs); //排序
if(Arrays.equals(as, bs)){
return true;
}
return false;
}
}
在看这篇文章前，我推荐你看一下Eclipse 快捷键手册，我的eclipse版本是4.2 Juno。
先提三点
- 不要使用System.out.println作为调试工具
- 启用所有组件的详细的日志记录级别
- 使用一个日志分析器来阅读日志
1、条件断点想象一下我们平时如何添加断点，通常的做法是双击行号的左边。在debug视图中，BreakPoint View将所有断点都列出来，但是我们可以添加一个boolean类型的条件来决定断点是否被跳过。如果条件为真，在断点处程序将停止，否则断点被跳过，程序继续执行。
2、异常断点
在断点view中有一个看起来像J！的按钮，我们可以使用它添加一个基于异常的断点，例如我们希望当NullPointerException抛出的时候程序暂停，我们可以这样:
3、观察点
这个特性我非常喜欢，他允许当一个选定的属性被访问或者被更改的时候程序执行暂停，并进行debug。最简单的办法是在类中声明成员变量的语句行号左边双击，就可以加入一个观察点。
4、查看变量
在选中的变量上使用Ctrl+Shift+d 或者 Ctrl+Shift+i可以查看变量值，另外我们还可以在Expressions View中添加监视。
5、改变变量值
我们可以在Debug的时候改变其中变量的值。在Variables View中可以按下图所示操作。
6、在Main方法中停止
在Run/Debug设置中，我们可以按如下图所示的启用这个特性。程序将会在main方法的第一行停住
7、环境变量
我们可以很方便的在Edit Conriguration对话框中添加环境变量
8、Drop to frame
这个功能非常酷，是我第二个非常喜欢的功能，Drop to frame就是说，可以重新跳到当前方法的开始处重新执行，并且所有上下文变量的值也回到那个时候。不一定是当前方法，可以点击当前调用栈中的任何一个frame跳到那里（除了最开始的那个frame）。主要用途是所有变量状态快速恢复到方法开始时候的样子重新执行一遍，即可以一遍又一遍地在那个你关注的上下文中进行多次调试（结合改变变量值等其它功能），而不用重来一遍调试到哪里了。当然，原来执行过程中产生的副作用是不可逆的（比如你往数据库中插入了一条记录）。
9、Step 过滤
当我们在调试的时候摁F5将进入方法的内部，但这有个缺点有的时候可能会进入到一些库的内部（例如JDK），可能并不是我们想要的，我们可以在Preferences中添加一个过滤器，排除指定的包。
10、进入、跳过、返回
其实这个技巧是debug最基本的知识。
- F5-Step Into：移动到下一步，如果当前的行是一个方法调用，将进入这个方法的第一行。（可以通过第九条来排除）
- F6-Step Over：移动到下一行。如果当前行有方法调用，这个方法将被执行完毕返回，然后到下一行。
- F7-Step Return：继续执行当前方法，当当前方法执行完毕的时候，控制将转到当前方法被调用的行。
- F8-移动到下一个断点处。
public class Main {
public static void main(String[] args) {
String pathB = "/P/y/z/a/b/c/d/34/c.php";
String pathA = "/P/y/z/a/b/a/g/e.php";
System.out.println(pathARelativePathB(pathA,pathB,0));
}
public static String pathARelativePathB(String pathA , String pathB, int i){
if(pathA.contains(pathB)){
StringBuilder replaceSb = new StringBuilder();
if(i==1){
replaceSb.append(".");
}else{
while(i>1){
replaceSb.append("../");
--i;
}
}
return pathA.replace(pathB,replaceSb.substring(0, replaceSb.lastIndexOf("/")));
}else{
return pathARelativePathB(pathA,pathB.substring(0,pathB.lastIndexOf("/")),++i);
}
}
}
if(window.external&&window.external.twGetRunPath&&window.external.twGetRunPath().toLowerCase().indexOf("360se")>-1){alert('本站不支持360浏览器访问，请更换其他浏览器！');}
摘要: 1、面向对象的特征有哪些方面 (1).抽象： 抽象就是忽略一个主题中与当前目标无关的那些方面，以便更充分地注意与当前目标有关的方面。抽象并不打算了解全部问题，而只是选择其中的一部分，暂时不用部分细 节。抽象包括两个方面，一是过程抽象，二是数据抽象。 (2).继承： 继承是一种联结类的层次模型，并且允许和鼓励类的重用，它提供了一种明确表述共性的方法。对象的一个... 阅读全文
Beanutils用了魔术般的反射技术，实现了很多夸张有用的功能，都是C/C++时代不敢想的。无论谁的项目，始终一天都会用得上它。我算是后知后觉了，第一回看到它的时候居然错过。
1.属性的动态getter,setter
在这框架满天飞的年代，不能事事都保证执行getter,setter函数了，有时候属性是要需要根据名字动态取得的，就像这样：
BeanUtils.getProperty(myBean,"code");
而BeanUtils更强的功能是直接访问内嵌对象的属性，只要使用点号分隔。
BeanUtils.getProperty(orderBean, "address.city");
相比之下其他类库的BeanUtils通常都很简单，不能访问内嵌的对象，所以经常要用Commons BeanUtils替换它们。
BeanUtils还支持List和Map类型的属性。如下面的语法即可取得顾客列表中第一个顾客的名字
BeanUtils.getProperty(orderBean, "customers[1].name");
其中BeanUtils会使用ConvertUtils类把字符串转为Bean属性的真正类型，方便从HttpServletRequest等对象中提取bean，或者把bean输出到页面。
而PropertyUtils就会原色的保留Bean原来的类型。
2.beanCompartor 动态排序
还是通过反射，动态设定Bean按照哪个属性来排序，而不再需要在bean的Compare接口进行复杂的条件判断。
List peoples = ...; // Person对象的列表Collections.sort(peoples, new BeanComparator("age"));如果要支持多个属性的复合排序，如"Order By lastName,firstName"
ArrayList sortFields = new ArrayList();sortFields.add(new BeanComparator("lastName"));sortFields.add(new BeanComparator("firstName"));ComparatorChain multiSort = new ComparatorChain(sortFields);
Collections.sort(rows,multiSort);
其中ComparatorChain属于jakata commons-collections包。
如果age属性不是普通类型，构造函数需要再传入一个comparator对象为age变量排序。
另外, BeanCompartor本身的ComparebleComparator, 遇到属性为null就会抛出异常, 也不能设定升序还是降序。
这个时候又要借助commons-collections包的ComparatorUtils.
Comparator mycmp = ComparableComparator.getInstance();
mycmp = ComparatorUtils.nullLowComparator(mycmp); //允许null
mycmp = ComparatorUtils.reversedComparator(mycmp); //逆序
Comparator cmp = new BeanComparator(sortColumn, mycmp);
3.Converter 把Request或ResultSet中的字符串绑定到对象的属性 经常要从request,resultSet等对象取出值来赋入bean中，下面的代码谁都写腻了，如果不用MVC框架的绑定功能的话。
String a = request.getParameter("a"); bean.setA(a); String b = ....不妨写一个Binder:
MyBean bean = ...; HashMap map = new HashMap(); Enumeration names = request.getParameterNames(); while (names.hasMoreElements()) { String name = (String) names.nextElement(); map.put(name, request.getParameterValues(name)); } BeanUtils.populate(bean, map); 其中BeanUtils的populate方法或者getProperty,setProperty方法其实都会调用convert进行转换。
但Converter只支持一些基本的类型，甚至连java.util.Date类型也不支持。而且它比较笨的一个地方是当遇到不认识的类型时，居然会抛出异常来。
对于Date类型，我参考它的sqldate类型实现了一个Converter,而且添加了一个设置日期格式的函数。
要把这个Converter注册，需要如下语句：
ConvertUtilsBean convertUtils = new ConvertUtilsBean();
DateConverter dateConverter = new DateConverter();
convertUtils.register(dateConverter,Date.class);
//因为要注册converter,所以不能再使用BeanUtils的静态方法了，必须创建BeanUtilsBean实例
BeanUtilsBean beanUtils = new BeanUtilsBean(convertUtils,new PropertyUtilsBean());
beanUtils.setProperty(bean, name, value);
4 其他功能4.1 PropertyUtils，当属性为Collection,Map时的动态读取：
Collection: 提供index
BeanUtils.getIndexedProperty(orderBean,"items",1);
或者
BeanUtils.getIndexedProperty(orderBean,"items[1]");
Map: 提供Key Value
BeanUtils.getMappedProperty(orderBean, "items","111");//key-value goods_no=111
或者
BeanUtils.getMappedProperty(orderBean, "items(111)")
4.2 PropertyUtils，获取属性的Class类型
public static Class getPropertyType(Object bean, String name)
4.3 ConstructorUtils，动态创建对象
public static Object invokeConstructor(Class klass, Object arg)
4.4 MethodUtils，动态调用方法
MethodUtils.invokeMethod(bean, methodName, parameter);
4.5 动态Bean 见用DynaBean减除不必要的VO和FormBean
很久很久以前，有一群人，他们决定用8个可以开合的晶体管来组合成不同的状态，以表示世界上的万物。他们看到8个开关状态是好的，于是他们把这称为"字节"。
再后来，他们又做了一些可以处理这些字节的机器，机器开动了，可以用字节来组合出很多状态，状态开始变来变去。他们看到这样是好的，于是它们就这机器称为"计算机"。
开始计算机只在美国用。八位的字节一共可以组合出256(2的8次方)种不同的状态。
他们把其中的编号从0开始的32种状态分别规定了特殊的用途，一但终端、打印机遇上约定好的这些字节被传过来时，就要做一些约定的动作。遇上00x10, 终端就换行，遇上0x07, 终端就向人们嘟嘟叫，例好遇上0x1b, 打印机就打印反白的字，或者终端就用彩色显示字母。他们看到这样很好，于是就把这些0x20以下的字节状态称为"控制码"。
他们又把所有的空格、标点符号、数字、大小写字母分别用连续的字节状态表示，一直编到了第127号，这样计算机就可以用不同字节来存储英语的文字了。大家看到这样，都感觉很好，于是大家都把这个方案叫做 ANSI 的"Ascii"编码（American Standard Code for Information Interchange，美国信息互换标准代码）。当时世界上所有的计算机都用同样的ASCII方案来保存英文文字。
后来，就像建造巴比伦塔一样，世界各地的都开始使用计算机，但是很多国家用的不是英文，他们的字母里有许多是ASCII里没有的，为了可以在计算机保存他们的文字，他们决定采用127号之后的空位来表示这些新的字母、符号，还加入了很多画表格时需要用下到的横线、竖线、交叉等形状，一直把序号编到了最后一个状态255。从128到255这一页的字符集被称"扩展字符集"。从此之后，贪婪的人类再没有新的状态可以用了，美帝国主义可能没有想到还有第三世界国家的人们也希望可以用到计算机吧！
等中国人们得到计算机时，已经没有可以利用的字节状态来表示汉字，况且有6000多个常用汉字需要保存呢。但是这难不倒智慧的中国人民，我们不客气地把那些127号之后的奇异符号们直接取消掉, 规定：一个小于127的字符的意义与原来相同，但两个大于127的字符连在一起时，就表示一个汉字，前面的一个字节（他称之为高字节）从0xA1用到0xF7，后面一个字节（低字节）从0xA1到0xFE，这样我们就可以组合出大约7000多个简体汉字了。在这些编码里，我们还把数学符号、罗马希腊的字母、日文的假名们都编进去了，连在 ASCII 里本来就有的数字、标点、字母都统统重新编了两个字节长的编码，这就是常说的"全角"字符，而原来在127号以下的那些就叫"半角"字符了。
中国人民看到这样很不错，于是就把这种汉字方案叫做 "GB2312"。GB2312 是对 ASCII 的中文扩展。
但是中国的汉字太多了，我们很快就就发现有许多人的人名没有办法在这里打出来，特别是某些很会麻烦别人的国家领导人。于是我们不得不继续把 GB2312 没有用到的码位找出来老实不客气地用上。
后来还是不够用，于是干脆不再要求低字节一定是127号之后的内码，只要第一个字节是大于127就固定表示这是一个汉字的开始，不管后面跟的是不是扩展字符集里的内容。结果扩展之后的编码方案被称为 GBK 标准，GBK 包括了 GB2312 的所有内容，同时又增加了近20000个新的汉字（包括繁体字）和符号。
后来少数民族也要用电脑了，于是我们再扩展，又加了几千个新的少数民族的字，GBK 扩成了 GB18030。从此之后，中华民族的文化就可以在计算机时代中传承了。
中国的程序员们看到这一系列汉字编码的标准是好的，于是通称他们叫做 "DBCS"（Double Byte Charecter Set 双字节字符集）。在DBCS系列标准里，最大的特点是两字节长的汉字字符和一字节长的英文字符并存于同一套编码方案里，因此他们写的程序为了支持中文处理，必须要注意字串里的每一个字节的值，如果这个值是大于127的，那么就认为一个双字节字符集里的字符出现了。那时候凡是受过加持，会编程的计算机僧侣们都要每天念下面这个咒语数百遍：
"一个汉字算两个英文字符！一个汉字算两个英文字符......"
因为当时各个国家都像中国这样搞出一套自己的编码标准，结果互相之间谁也不懂谁的编码，谁也不支持别人的编码，连大陆和台湾这样只相隔了150海里，使用着同一种语言的兄弟地区，也分别采用了不同的 DBCS 编码方案。当时的中国人想让电脑显示汉字，就必须装上一个"汉字系统"，专门用来处理汉字的显示、输入的问题，但是那个台湾的愚昧封建人士写的算命程序就必须加装另一套支持 BIG5 编码的什么"倚天汉字系统"才可以用，装错了字符系统，显示就会乱了套！这怎么办？而且世界民族之林中还有那些一时用不上电脑的穷苦人民，他们的文字又怎么办？
真是计算机的巴比伦塔命题啊！
正在这时，大天使加百列及时出现了：一个叫 ISO （国际标谁化组织）的国际组织决定着手解决这个问题。他们采用的方法很简单：废了所有的地区性编码方案，重新搞一个包括了地球上所有文化、所有字母和符号的编码！他们打算叫它"Universal Multiple-Octet Coded Character Set"，简称 UCS, 俗称 "UNICODE"。
UNICODE 开始制订时，计算机的存储器容量极大地发展了，空间再也不成为问题了。于是 ISO 就直接规定必须用两个字节，也就是16位来统一表示所有的字符，对于ascii里的那些"半角"字符，UNICODE 包持其原编码不变，只是将其长度由原来的8位扩展为16位，而其他文化和语言的字符则全部重新统一编码。由于"半角"英文符号只需要用到低8位，所以其高8位永远是0，因此这种大气的方案在保存英文文本时会多浪费一倍的空间。
这时候，从旧社会里走过来的程序员开始发现一个奇怪的现象：他们的strlen函数靠不住了，一个汉字不再是相当于两个字符了，而是一个！是的，从 UNICODE 开始，无论是半角的英文字母，还是全角的汉字，它们都是统一的"一个字符"！同时，也都是统一的"两个字节"，请注意"字符"和"字节"两个术语的不同，"字节"是一个8位的物理存贮单元，而"字符"则是一个文化相关的符号。在UNICODE 中，一个字符就是两个字节。一个汉字算两个英文字符的时代已经快过去了。
从前多种字符集存在时，那些做多语言软件的公司遇上过很大麻烦，他们为了在不同的国家销售同一套软件，就不得不在区域化软件时也加持那个双字节字符集咒语，不仅要处处小心不要搞错，还要把软件中的文字在不同的字符集中转来转去。UNICODE 对于他们来说是一个很好的一揽子解决方案，于是从 Windows NT 开始，MS 趁机把它们的操作系统改了一遍，把所有的核心代码都改成了用 UNICODE 方式工作的版本，从这时开始，WINDOWS 系统终于无需要加装各种本土语言系统，就可以显示全世界上所有文化的字符了。
但是，UNICODE 在制订时没有考虑与任何一种现有的编码方案保持兼容，这使得 GBK 与UNICODE 在汉字的内码编排上完全是不一样的，没有一种简单的算术方法可以把文本内容从UNICODE编码和另一种编码进行转换，这种转换必须通过查表来进行。
如前所述，UNICODE 是用两个字节来表示为一个字符，他总共可以组合出65535不同的字符，这大概已经可以覆盖世界上所有文化的符号。如果还不够也没有关系，ISO已经准备了UCS-4方案，说简单了就是四个字节来表示一个字符，这样我们就可以组合出21亿个不同的字符出来（最高位有其他用途），这大概可以用到银河联邦成立那一天吧！
UNICODE 来到时，一起到来的还有计算机网络的兴起，UNICODE 如何在网络上传输也是一个必须考虑的问题，于是面向传输的众多 UTF（UCS Transfer Format）标准出现了，顾名思义，UTF8就是每次8个位传输数据，而UTF16就是每次16个位，只不过为了传输时的可靠性，从UNICODE到UTF时并不是直接的对应，而是要过一些算法和规则来转换。
受到过网络编程加持的计算机僧侣们都知道，在网络里传递信息时有一个很重要的问题，就是对于数据高低位的解读方式，一些计算机是采用低位先发送的方法，例如我们PC机采用的 INTEL 架构，而另一些是采用高位先发送的方式，在网络中交换数据时，为了核对双方对于高低位的认识是否是一致的，采用了一种很简便的方法，就是在文本流的开始时向对方发送一个标志符。如果之后的文本是高位在位，那就发送"FEFF"，反之，则发送"FFFE"。不信你可以用二进制方式打开一个UTF-X格式的文件，看看开头两个字节是不是这两个字节？
讲到这里，我们再顺便说说一个很著名的奇怪现象：当你在 windows 的记事本里新建一个文件，输入"联通"两个字之后，保存，关闭，然后再次打开，你会发现这两个字已经消失了，代之的是几个乱码！呵呵，有人说这就是联通之所以拼不过移动的原因。
其实这是因为GB2312编码与UTF8编码产生了编码冲撞的原因。
从网上引来一段从UNICODE到UTF8的转换规则：
Unicode
UTF-8
0000 - 007F
0xxxxxxx
0080 - 07FF
110xxxxx 10xxxxxx
0800 - FFFF
1110xxxx 10xxxxxx 10xxxxxx
例如"汉"字的Unicode编码是6C49。6C49在0800-FFFF之间，所以要用3字节模板：1110xxxx 10xxxxxx 10xxxxxx。将6C49写成二进制是：0110 1100 0100 1001，将这个比特流按三字节模板的分段方法分为0110 110001 001001，依次代替模板中的x，得到：1110-0110 10-110001 10-001001，即E6 B1 89，这就是其UTF8的编码。
而当你新建一个文本文件时，记事本的编码默认是ANSI, 如果你在ANSI的编码输入汉字，那么他实际就是GB系列的编码方式，在这种编码下，"联通"的内码是：
c1 1100 0001
aa 1010 1010
cd 1100 1101
a8 1010 1000
注意到了吗？第一二个字节、第三四个字节的起始部分的都是"110"和"10"，正好与UTF8规则里的两字节模板是一致的，于是再次打开记事本时，记事本就误认为这是一个UTF8编码的文件，让我们把第一个字节的110和第二个字节的10去掉，我们就得到了"00001 101010"，再把各位对齐，补上前导的0，就得到了"0000 0000 0110 1010"，不好意思，这是UNICODE的006A，也就是小写的字母"j"，而之后的两字节用UTF8解码之后是0368，这个字符什么也不是。这就是只有"联通"两个字的文件没有办法在记事本里正常显示的原因。
而如果你在"联通"之后多输入几个字，其他的字的编码不见得又恰好是110和10开始的字节，这样再次打开时，记事本就不会坚持这是一个utf8编码的文件，而会用ANSI的方式解读之，这时乱码又不出现了。
/**
*
*/
package sortAlgorithm;
import java.io.File;
import java.io.IOException;
import java.sql.Time;
import java.util.Random;
/**
* @author sky
* 该类给出各种排序算法
*
*/
public class sort{
private static Integer[] elem(int n){
int N=n;
Random random=new Random();
Integer elem[]=new Integer[N];
for (int i=0;i<N;i++){
elem[i]=random.nextInt(1000);
}
return elem;
}
public static void main (String Args[]) throws InterruptedException{
int n=30000;
Integer elem[]=elem(n);
long start,end;
class sort0 extends Thread{
Integer elem[];
int n;
sort0(Integer elem[],int n){
this.elem=elem;
this.n=n;
}
public void run(){
System.out.println("线程启动");
straightInsertSort(elem,n);
}
}
elem=elem(n);
start=System.currentTimeMillis();
sort0 s1=new sort0(elem,n);
elem=elem(n);
sort0 s2=new sort0(elem,n);
elem=elem(n);
sort0 s3=new sort0(elem,n);
elem=elem(n);
sort0 s4=new sort0(elem,n);
elem=elem(n);
sort0 s5=new sort0(elem,n);
s1.start();
s2.start();
s3.start();
s4.start();
s5.start();
s2.join();
s1.join();
s3.join();
s4.join();
s5.join();
System.out.println("多线程简单插入排序：");
end=System.currentTimeMillis();
System.out.println(end-start);
elem=elem(n);
start=System.currentTimeMillis();
straightInsertSort(elem,n);
end=System.currentTimeMillis();
System.out.println("简单插入排序：");
System.out.println(end-start);
elem=elem(n);
start=System.currentTimeMillis();
shellSort(elem,n);
end=System.currentTimeMillis();
System.out.println("希尔排序：");
System.out.println(end-start);
elem=elem(n);
start=System.currentTimeMillis();
bubbleSort(elem,n);
end=System.currentTimeMillis();
System.out.println("冒泡排序：");
System.out.println(end-start);
/*
elem=elem(n);
start=System.currentTimeMillis();
quickSort(elem,n);
end=System.currentTimeMillis();
System.out.println("快速排序：");
System.out.println(end-start);*/
elem=elem(n);
start=System.currentTimeMillis();
simpleSelectionSort(elem,n);
end=System.currentTimeMillis();
System.out.println("简单选择排序：");
System.out.println(end-start);
elem=elem(n);
start=System.currentTimeMillis();
heapSort(elem,n);
end=System.currentTimeMillis();
System.out.println("堆排序：");
System.out.println(end-start);
elem=elem(n);
start=System.currentTimeMillis();
mergeSort(elem,n);
end=System.currentTimeMillis();
System.out.println("归并排序：");
System.out.println(end-start);
}
//显示排序结果
public static <T extends Comparable<? super T>> void show(T[] elem,int n){
for (int i=0;i<n;i++){
System.out.print(elem[i]);
System.out.print(' ');
}
System.out.println();
}
//交换元素
private static <T extends Comparable<? super T>> void swap(T[] elem,int i,int j){
T tmp=elem[i];
elem[i]=elem[j];
elem[j]=tmp;
}
//直接插入排序法,复杂度为O(n^2)
public static <T extends Comparable<? super T>> void straightInsertSort (T elem[],int n){
for (int i=1;i<n;i++){
T e=elem[i];
int j;
for (j=i-1;j>=0 && e.compareTo(elem[j])<0;j--){
elem[j+1]=elem[j];
}
elem[j+1]=e;
}
}
//shell插入排序算法,复杂度为O(n^1.5)
private static <T extends Comparable<? super T>> void shellInsertHelp(T elem[],int n,int incr){
for (int i=incr;i<n;i++){
T e=elem[i];
int j=i-incr;
for (;j>=0 && e.compareTo(elem[j])<0;j=j-incr){
elem[j+incr]=elem[j];
}
elem[j+incr]=e;
}
}
public static <T extends Comparable<? super T>> void shellSort(T elem[],int n ){
for (int incr=n/2;incr>0;incr=incr/2){
shellInsertHelp(elem,n,incr);
}
}
//冒泡排序算法，时间复杂度为O(n^2)
public static <T extends Comparable<? super T>> void bubbleSort(T elem[],int n){
for (int i=n-1;i>0;i--){
for (int j=0;j<i;j++){
if (elem[j].compareTo(elem[i])>0){
swap(elem,i,j);
}
}
}
}
//快速排序算法，时间复杂度为O(n*log(n))
private static <T extends Comparable<? super T>> int partition(T elem[],int low,int high){
while (low<high){
for (;elem[high].compareTo(elem[low])>=0 && low<high;high--);
swap(elem,high,low);
for (;elem[high].compareTo(elem[low])>=0 && low<high;low++);
swap(elem,high,low);
}
return low;
}
private static <T extends Comparable<? super T>> void quickSortHelp(T elem[],int low,int high){
if (low<high){
int pivot=partition(elem,low,high);
quickSortHelp(elem,low,pivot-1);
quickSortHelp(elem,pivot+1,high);
}
}
public static <T extends Comparable<? super T>> void quickSort(T elem[],int n){
quickSortHelp(elem,0,n-1);
}
//简单选择排序算法，时间复杂度为O(n^2)
public static <T extends Comparable<? super T>> void simpleSelectionSort(T elem[],int n){
for (int i=0;i<n-1;i++){
int lowIdx=i;
for (int j=i+1;j<n;j++){
if (elem[lowIdx].compareTo(elem[j])>0)
lowIdx=j;
}
swap(elem,lowIdx,i);
}
}
//堆排序，时间复杂度为O(n*log(n))
private static <T extends Comparable<? super T>> void heapAdjust(T elem[],int low,int high){
for (int i=low,lhs=2*i+1 ;lhs<=high;lhs=2*i+1){
if (lhs<high && elem[lhs].compareTo(elem[lhs+1])<0)lhs++;
if (elem[i].compareTo(elem[lhs])<0){
swap(elem,i,lhs);
i=lhs;
}else break;
}
}
public static <T extends Comparable<? super T>> void heapSort(T elem[],int n){
//初始化堆
for (int i=(n-2)/2;i>=0;i--){
heapAdjust(elem,i,n-1);
}
swap(elem,0,n-1);
//排序
for (int i=n-2;i>0;--i){
heapAdjust(elem,0,i);
swap(elem,0,i);
}
}
//归并排序算法，时间复杂度为O(n*log(n))
private static <T extends Comparable<? super T>> void simpleMerge(T elem[],T tmpElem[],int low ,int mid, int high){
int i=low,j=mid+1,k=low;
for (;i<=mid && j<=high;k++){
if (elem[i].compareTo(elem[j])<=0)
tmpElem[k]=elem[i++];
else
tmpElem[k]=elem[j++];
}
for (;i<=mid;i++){
tmpElem[k++]=elem[i];
}
for (;j<=high;j++){
tmpElem[k++]=elem[j];
}
for (;low<=high;low++){
elem[low]=tmpElem[low];
}
}
private static <T extends Comparable<? super T>> void mergeHelp(T elem[],T tmpElem[],int low ,int high){
if (low < high){
int mid=(low+high)/2;
mergeHelp(elem,tmpElem,low,mid);
mergeHelp(elem,tmpElem,mid+1,high);
simpleMerge(elem,tmpElem,low,mid,high);
}
}
public static <T extends Comparable<? super T>> void mergeSort(T elem[],int n){
T[] tmpElem=(T[])new Comparable[n];
mergeHelp(elem,tmpElem,0,n-1);
}
}