说说IO（一）- IO的分层

IO性能对于一个系统的影响是至关重要的。一个系统经过多项优化以后，瓶颈往往落在数据库；而数据库经过多种优化以后，瓶颈最终会落到IO。而IO性能的发展，明显落后于CPU的发展。Memchached也好，NoSql也好，这些流行技术的背后都在直接或者间接地回避IO瓶颈，从而提高系统性能。

IO**系统的分层：**

1. 三层结构

上图层次比较多，但总的就是三部分。磁盘（存储）、VM（卷管理）和文件系统。专有名词不好理解，打个比方说：磁盘就相当于一块待用的空地；LVM相当于空地上的围墙（把空地划分成多个部分）；文件系统则相当于每块空地上建的楼房（决定了有多少房间、房屋编号如何，能容纳多少人住）；而房子里面住的人，则相当于系统里面存的数据。

• 文件系统—数据如何存放？

对应了上图的File System和Buffer Cache。

File System**（文件系统）：解决了空间管理的问题**，即：数据如何存放、读取。

Buffer Cache：解决数据缓冲的问题。对读，进行cache，即：缓存经常要用到的数据；对写，进行buffer，缓冲一定数据以后，一次性进行写入。

• VM—磁盘空间不足了怎么办？

对应上图的Vol Mgmt。

VM其实跟IO没有必然联系。他是处于文件系统和磁盘（存储）中间的一层。VM**屏蔽了底层磁盘对上层文件系统的影响**。当没有VM的时候，文件系统直接使用存储上的地址空间，因此文件系统直接受限于物理硬盘，这时如果发生磁盘空间不足的情况，对应用而言将是一场噩梦，不得不新增硬盘，然后重新进行数据复制。而VM则可以实现动态扩展，而对文件系统没有影响。另外，VM也可以把多个磁盘合并成一个磁盘，对文件系统呈现统一的地址空间，这个特性的杀伤力不言而喻。

• 存储—数据放在哪儿？如何访问？如何提高IO速度？

对应上图的Device Driver、IO Channel和Disk Device

数据最终会放在这里，因此，效率、数据安全、容灾是这里需要考虑的问题。而提高存储的性能，则可以直接提高物理IO的性能

2. Logical IO vs Physical IO

逻辑IO是操作系统发起的IO，这个数据可能会放在磁盘上，也可能会放在内存（文件系统的Cache）里。

物理IO是设备驱动发起的IO，这个数据最终会落在磁盘上。

  逻辑IO和物理IO不是一一对应的。

Java使用”指针”快速比较字节

如何才能快速比较两个字节数组呢?我将问题描述成下面的接口：

public int compareTo(byte[] b1, int s1, int l1, byte[] b2, int s2,int l2);

最直观的做法是同时遍历两个数组，两两比较。

public int compareTo(byte[] buffer1, int offset1, int length1, byte[] buffer2, int offset2, int length2) {

// Short circuit equal case
if (buffer1 == buffer2 && offset1 == offset2

    && length1 == length2) {
    return 0;

}
// Bring WritableComparator code local

int end1 = offset1 + length1;
int end2 = offset2 + length2;

for (int i = offset1, j = offset2; i < end1 && j < end2; i++, j++) {
    int a = (buffer1[i] & 0xff);

    int b = (buffer2[j] & 0xff);
    if (a != b) {

return a - b; }

}
return length1 - length2;

}

如果事情这么简单就结束了，就没有意思了。

如果要提升性能，可以做循环展开等等优化，但这些优化应该依赖JVM来做，新的JVM可以做的很好。那还有什么办法可以提高性能呢？ 可以将字节数组合并!!上面的例子中，每个byte被迫转型成了int，再比较。其实我们可以将8个byte转换成一个long，在比较long，这样效果会不会好些？用什么方法转换才是最优的？

long sun.misc.Unsafe.getLong(Object o,int offset)

Java提供了一个本地方法，可以最快最好转换byte与long。该函数是直接访问一个对象的内存，内存地址是对象指针加偏移量，返回该地址指向的值。有人说Java很安全，不可以操作指针，所以有的时候性能也不高。其实不对，有了这个Unsafe类，Java一样也不安全。所以Unsafe类中的方法都不是public的，不过没关系，我们有反射。言归正传，下面是使用这种技术手段的实现代码。

public int compareTo(byte[] buffer1, int offset1, int length1, byte[] buffer2, int offset2, int length2) {

// Short circuit equal case
if (buffer1 == buffer2 && offset1 == offset2

        && length1 == length2) {
    return 0;

}
int minLength = Math.min(length1, length2);

int minWords = minLength / Longs.BYTES;
int offset1Adj = offset1 + BYTE_ARRAY_BASE_OFFSET;

int offset2Adj = offset2 + BYTE_ARRAY_BASE_OFFSET;


//*
 /* Compare 8 bytes at a time. Benchmarking shows comparing 8

 /* bytes at a time is no slower than comparing 4 bytes at a time
 /* even on 32-bit. On the other hand, it is substantially faster

 /* on 64-bit.
 /*/

for (int i = 0; i < minWords /* Longs.BYTES; i += Longs.BYTES) {
    long lw = theUnsafe.getLong(buffer1, offset1Adj + (long) i);

    long rw = theUnsafe.getLong(buffer2, offset2Adj + (long) i);
    long diff = lw ^ rw;


    if (diff != 0) {

        if (!littleEndian) {
            return (lw + Long.MIN_VALUE) < (rw + Long.MIN_VALUE) ? -1

                    : 1;
        }


        // Use binary search,一下省略若干代码

        .....
        return (int) (((lw >>> n) & 0xFFL) - ((rw >>> n) & 0xFFL));

    }
}


// The epilogue to cover the last (minLength % 8) elements.

for (int i = minWords /* Longs.BYTES; i < minLength; i++) {
    int result = UnsignedBytes.compare(buffer1[offset1 + i],

            buffer2[offset2 + i]);
    if (result != 0) {

        return result;
    }

}
return length1 - length2;

}

实现比原来复杂了一些。但这次一次可以比较8个字节了。这种getLong函数和系统的字节序是紧紧相关的，如果是小端序操作起来有点麻烦，代码先省略掉。这样操作实际效果如何？我们需要对比测试下。对比两个1M的字节数组，如果使用第一个版本，每次比较平均需要2.5499ms,如果使用第二个版本，需要0.8359ms,提升了3倍。对应这种CPU密集型的操作，这样的提升可是很可观的。

如果要提升性能，使用Unsafe直接访问内存也是不错的选择。 Share the post "Java使用"指针"快速比较字节"

JSTL EL 详解

概述**：** JavaWind.net Document 在JSP页面中，使用标签库代替传统的Java片段语言来实现页面的显示逻辑已经不是新技术了，然而，由自定义标签很容易造成重复定义和非标准的实现。鉴于此，出现了JSTL（JSP Standard Tag Library），为大多数JSP页面逻辑提供了实现的JSTL技术，该技术本身就是一个标签库。 Sun公司Java规范标准的JSTL由apache jakarta组织负责维护。作为开源的标准技术，它一直在不断地完善。JSTL的发布包有两个版本：Standard-1.0 Taglib、Standard-1.1 Taglib，它们在使用时是不同的。 Standard-1.0 Taglib（JSTL1.0）支持Servlet2.3和JSP1.2规范，Web应用服务器Tomcat4支持这些规范，而它的发布也在Tomcat 4.1.24测试通过了。 Standard-1.1 Taglib（JSTL1.1）支持Servlet2.4和JSP2.0规范，Web应用服务器Tomcat5支持这些规范，它的发布在Tomcat 5.0.3测试通过了。 在本章的介绍中，将以由Sun发布的Standard-1.1 Taglib标签库为主，而apache jakarta组织发布的开源标签库，可以从http://jakarta.apache.org/taglibs/找到所需要的帮助。Sun发布的标准JSTL1.1标签库有以下几个标签： 核心标签库：包含Web应用的常见工作，比如：循环、表达式赋值、基本输入输出等。 国际化标签库：用来格式化显示数据的工作，比如：对不同区域的日期格式化等。 数据库标签库：可以做访问数据库的工作。 XML标签库：用来访问XML文件的工作，这是JSTL标签库的一个特点。 函数标签库：用来读取已经定义的某个函数。

  此外，JSTL还提供了EL表达式语言（Expression Language）来进行辅助的工作。
  JSTL标签库由标签库和EL表达式语言两个部分组成。EL在JSTL 1.0规范中被引入，当时用来作为Java表达式来工作，而该表达式必须配合JSTL的标签库才能得到需要的结果。
  说明：在JSTL 1.1规范中，JSP2.0容器已经能够独立的理解任何EL表达式。EL可以独立出现在JSP页面的任何角落。本文随后的内容将以JSTL 1.1规范作为介绍的重点。

9.2.1 JSTL EL**表达式语言简介** JavaWind.net Document EL是从JavaScript脚本语言得到启发的一种表达式语言，它借鉴了JavaScript多类型转换无关性的特点。在使用EL从scope中得到参数时可以自动转换类型，因此对于类型的限制更加宽松。Web服务器对于request请求参数通常会以String类型来发送，在得到时使用的Java语言脚本就应该是request.getParameter(“XXX”)，这样的话，对于实际应用还必须进行强制类型转换。而EL就将用户从这种类型转换的繁琐工作脱离出来，允许用户直接使用EL表达式取得的值，而不用关心它是什么类型。 下面的示例就是一个EL表达式，见例9.1。 例9.1：简单EL表达式

  <%@ page contentType="text/html; charset=UTF-8"%>
  <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
  <html>
   <body> ${sampleValue + 1} <br> </body>
  </html>

  这个示例将在JSP页面显示为“1”，EL表达式必须以“${XXX}”来表示，其中“XXX”部分就是具体表达式内容，“${}”将这个表达式内容包含在其中作为EL表达式的定义。本示例可以在满足JSP2.0规范的任何Web应用服务器中使用。

9.2.2 EL**表达式的默认变量** JavaWind.net Document 一个EL表达式包含变量和操作符两个内容。任何存在于JSP作用范围的JavaBean都可以被转化成EL表达式来使用，它所包含的默认变量如下：

1**．默认变量pageScope、requestScope、sessionScope、applicationScope** 这4个默认变量包含Scope作用范围的参数集合，相当于被保存在java.util.Map中的某个参数。下面看简单的示例9.2：

例9.2：使用sessionScope变量的EL表达式

<%request.getSession().setAttribute("sampleValue", new Integer(10));%> ${sessionScope.sampleValue}

取得保存在Session中参数的sessionScope变量的EL表达式，“.”是property访问操作符，在这里表示从Session中取得“键”为“sampleValue”的参数，并显示出来。显示结果为“10”。

2**．默认变量param、paramValues** 这两个默认变量包含请求参数的集合，param表明请求包含的参数为单一控件，paramValues表明请求包含的参数为控件数组。下面看一个简单示例9.3：

例9.3：提交请求的页面和接受的页面

\<%@ page contentType="text/html; charset=UTF-8"%> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

  在这个页面中定义了两组控件，控件名为“sampleValue”的是一套控件数组，控件名为“sampleSingleValue”的是单一控件，通过递交将请求参数传送到SampleJsp.jsp。

<%@ page contentType="text/html; charset=UTF-8"%> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

  这是请求转发到的页面，通过EL表达式的paramValues变量得到控件数组中最后一个控件的递交参数，通过EL表达式的param变量得到单一控件的递交参数。控件数组参数的EL表达式使用“[]”来指定数组下标。本示例将显示控件数组中最后一个控件的值“12”和单一控件的值“SingleValue”。

3**．默认变量header、headerValues** 这两个默认变量包含请求参数头部信息的集合，header变量表示单一头部信息，headerValues则表示数组型的头部信息。

4**．默认变量cookie** 包含所有请求的cookie集合，集合中的每个对象对应javax.servlet.http.Cookie。

5**．默认变量initParam** 包含所有应用程序初始化参数的集合。

6**．默认变量pageContext** 等价于page环境类javax.servlet.jsp.PageContext的实例，用来提供访问不同的请求参数。 11个默认变量几乎包含了Web应用的所有基本操作，若一个表达式不使用这些变量而直接使用参数名，那么就采用就近原则。该表达式将使用最近取得的参数值。

**标签库介绍** JavaWind.net Document

表达式的操作符 EL表达式中还有许多操作符可以帮助完成各种所需的操作，之前的示例中“.”、“[]”就是其中的两个，下面将用表9.1来展示所有操作符及它们各自的功能。

表9.1 EL表达式的操作符 操作符

功能和作用 .

访问一个bean属性或者Map entry []

访问一个数组或者链表元素 ()

对子表达式分组，用来改变赋值顺序 ? :

条件语句，比如：条件?ifTrue:ifFalse

如果条件为真，表达式值为前者，反之为后者 +

数学运算符，加操作 -

数学运算符，减操作或者对一个值取反 /*

数学运算符，乘操作 / 或div

数学运算符，除操作 % 或mod

数学运算符，模操作(取余) == 或eq

逻辑运算符，判断符号左右两端是否相等，如果相等返回true，否则返回false != 或ne

逻辑运算符，判断符号左右两端是否不相等，如果不相等返回true，否则返回false < 或lt

逻辑运算符，判断符号左边是否小于右边，如果小于返回true，否则返回false > 或gt

逻辑运算符，判断符号左边是否大于右边，如果大于返回true，否则返回false <= 或le

逻辑运算符，判断符号左边是否小于或者等于右边，如果小于或者等于返回true，否则返回false >= 或ge

逻辑运算符，判断符号左边是否大于或者等于右边，如果大于或者等于返回true，否则返回false && 或and

逻辑运算符，与操作赋。如果左右两边同为true返回true，否则返回false || 或or

逻辑运算符，或操作赋。如果左右两边有任何一边为true返回true，否则返回false ! 或not

逻辑运算符，非操作赋。如果对true取运算返回false，否则返回true empty

用来对一个空变量值进行判断: null、一个空String、空数组、空Map、没有条目的Collection集合 func(args)

调用方法, func是方法名，args是参数，可以没有，或者有一个、多个参数.参数间用逗号隔开

这些操作符都是极其有用的，下面通过几个示例来演示它们的使用方法：

例9.4：几组操作符的示例

${pageScope.sampleValue + 12}
//显示12 ${(pageScope.sampleValue + 12)/3}
//显示4.0 ${(pageScope.sampleValue + 12) /3==4}
//显示true ${(pageScope.sampleValue + 12) /3>=5}
//显示false

//显示值为10的Text控件

可以看到，对于这些示例，程序设计者完全无需管理它们的类型转换，在表达式内部都已经处理了。有了EL表达式，在JSP页面的编程变得更灵活，也更容易。

**标签库介绍** 在JSTL1.1中有以下这些标签库是被支持的：Core标签库、XML processing标签库、I18N formatting标签库、Database access标签库、Functions标签库。 对应的标识符见表9.2所示：

表9.2 标签库的标识符 标签库

URI

前缀 Core

http://java.sun.com/jsp/jstl/core

c XML processing

http://java.sun.com/jsp/jstl/xml

x I18N formatting

http://java.sun.com/jsp/jstl/fmt

fmt Database access

http://java.sun.com/jsp/jstl/sql

sql Functions

http://java.sun.com/jsp/jstl/functions

fn

下面看例9.5，简单使用标签库的示例。

例9.5：简单JSTL标签库示例

<%@ page contentType="text/html; charset=UTF-8"%> <%@ taglib prefix="c" uri="http://java.sun.com/jsp/jstl/core" %> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">

在该示例的JSP页面中声明了将使用Core标签库，它的URI为“http://java.sun.com/jsp/jstl/core”，前缀为“c”。之后，页面中标签就是使用了JSTL的标签进行了工作。对于该标签的功能，这里暂时不作具体讲解，只是让读者能够有个简单的概念，了解怎样定义和使用标签库。 标签库 Core标签库，又被称为核心标签库，该标签库的工作是对于JSP页面一般处理的封装。在该标签库中的标签一共有14个，被分为了四类，分别是：

     多用途核心标签：<c:out>、<c:set>、<c:remove>、<c:catch>。
     条件控制标签：<c:if>、<c:choose>、<c:when>、<c:otherwise>。
     循环控制标签：<c:forEach>、<c:forTokens>。
     URL相关标签：<c:import>、<c:url>、<c:redirect>、<c:param>。

以下是各个标签的用途和属性以及简单示例。

用于显示的****标签 JavaWind.net Document 标签是一个最常用的标签，用于在JSP中显示数据。它的属性和描述如表9.3所示：

表9.3　标签属性和说明 属性

描述 value

输出到页面的数据，可以是EL表达式或常量（必须） default

当value为null时显示的数据（可选） escapeXml

当设置为true时会主动更换特殊字符，比如“<,>,&”（可选，默认为true）

在JSTL1.0的时候，在页面显示数据必须使用来进行。然而，在JSTL1.1中，由于JSP2.0规范已经默认支持了EL表达式，因此可以直接在JSP页面使用表达式。下面看一个示例。

     <c:choose>标签没有属性，可以被认为是父标签，<c:when>、<c:otherwise>将作为其子标签来使用。
     <c:when>标签等价于“if”语句，它包含一个test属性，该属性表示需要判断的条件。
     <c:otherwise>标签没有属性，它等价于“else”语句。

     XML核心标签：<x:parse>、<x:out>、<x:set>。
     XML流控制标签：<x:if>、<x:choose>、<x:when>、<x:otherwise>、<x:forEach>。
     XML转换标签：<x:transform>、<x:param>。

    根据Locale环境的不同将查找不同后缀的资源配置文件，这点在国际化的任何技术上都是一致的，通常来说，这两种标签单独使用是没有意义的，它们都会与I18N formatting标签库中的其他标签配合使用。它们的属性和描述如表9.18所示：

   该示例使用了两种资源配置文件的绑定的做法，“ applicationMessage ”资源配置文件利用<fmt:setBundle>标签被赋于了变量“ applicationBundle ”，而作为<fmt:bundle>标签定义的“ applicationAllMessage ”资源配置文件作用于其标签体内的显示。

     第一个<fmt:message>标签将使用“ applicationAllMessage ”资源配置文件中“键”为“ userName ”的信息显示。
     第二个<fmt:message>标签虽然被定义在<fmt:bundle>标签体内，但是它使用了bundle属性，因此将指定之前由<fmt:setBundle>标签保存的“ applicationMessage ”资源配置文件，该“键”为“ passWord ”的信息显示。

   对于Database access标签库本书不作重点介绍，只给出几个简单示例让读者略微了解它们的功能。

   Database access标签库有以下6组标签来进行工作：<sql:setDataSource>、<sql:query>、<sql:update>、<sql:transaction>、<sql:setDataSource>、<sql:param>、<sql:dateParam>。

   长度函数：fn:length
   字符串处理函数：fn:contains、fn:containsIgnoreCase、fn:endsWith、fn:escapeXml、fn:indexOf、fn:join、fn:replace、fn:split、fn:startsWith、fn:substring、fn:substringAfter、fn:substringBefore、fn:toLowerCase、fn:toUpperCase、fn:trim

单向链表

单向链表**

博客分类：

• 数据结构 数据结构

【链表】 是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。 由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多， 但是查找一个节点或者访问特定编号的节点则需要O(n)的时间， 而顺序表相应的时间复杂度分别是O(㏒ n)和O(1)。 【单向链表】 是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始 一个节点包含两个域，一个信息域和一个指针域，指针域指向下一个节点，最后一个节点指向一个空值 单向链表有一个头节点，可以不存储任何信息，包含一个指向第一个节点的指针 特点: 1.访问节点速度慢，需要从头节点一次遍历链表 2.更新节点快，节点不需要移动，更改相应指针即可

单向链表节点类定义如下：

Java代码

1. public class Node{
3. AnyType element;
5. Node next;
7. }

要实现单向列表的相关操作，可定义类SingleLinkedList如下： Java代码

1. public class SingleLinkedList{
3. private static class Node{
5. AnyType element;
7. Node next;
9. public Node(AnyType element){
10. this.element = element;
11. }
13. }
15. private Node header = new Node(null);
17. private int size = 0;
19. public boolean isEmpty(){
20. return size==0;
21. }
23. public void makeEmpty(){
24. header = null;
25. }
27. public int size(){
28. return size;
29. }
31. ///
32. /* Get element by index
33. / //
34. public AnyType get(int index){
35. return getNode(index).element;
36. }
38. ///
39. /* Add the element to the end of this list
40. / //
41. public void add(AnyType element){
42. add(new Node(element));
43. }
45. ///
46. /* Inserts the specified element at the specified position in this list
47. /* 插入逻辑：
48. /* 1.创建一个新节点
49. /* 2.将原index节点的前一个节点的指针指向新节点
50. /* 3.将新节点的指针指向index节点
51. /* 4.插入后，新节点的位置为index
52. / //
53. public void add(int index,AnyType element){
54. Node newNode = new Node(element);
55. Node previous = getNode(index-1);
56. //index节点
57. Node node = previous.next;
58. //将原index节点的前一个节点的指针指向newNode
59. previous.next = newNode;
60. //将newNode的指针指向index节点
61. newNode.next = node;
62. size++;
63. }
65. ///
66. /* Inserts the specified element at the specified position in this list
67. /* 删除逻辑：
68. /* 1.获得index节点的前一个节点previousNode
69. /* 2.获得index节点的后一个节点nextNode
70. /* 3.将previousNode的指针指向nextNode
71. / //
72. public void remove(int index){
73. Node previous = getNode(index-1);
74. Node next = previous.next.next;
75. previous.next = next;
76. size--;
77. }
80. ///
81. /* 定义此方法是为了便于测试
82. / //
83. public List getElements(){
84. if(isEmpty()){
85. return null;
86. }else{
87. List elements = new ArrayList();
88. Node node = (Node) header;
89. while(node.next!=null){
90. node = node.next;
91. elements.add(((Element)node.element).getValue());
92. }
93. return elements;
94. }
95. }
98. //private methods
99. private Node getNode(int index){
100. if(isEmpty()){
101. throw new RuntimeException("List is empty");
102. }
103. int i = 0;
104. Node node = header;
105. while(i<=index){
106. node = node.next;
107. i++;
108. }
109. return node;
110. }
112. private void add(Node newNode){
113. Node node = header;
114. while(node.next!=null){
115. node = node.next;
116. }
117. node.next = newNode;
118. size++;
119. }
121. }

如何实现链表反向： Java代码

1. ///
2. /* 链表反向
3. / //
4. public void reverse(){
5. if(!isEmpty()){
6. reverse(header.next,header.next.next);
7. }
8. }

Java代码

1. private void reverse(Node node,Node nextNode){
2. if(nextNode.next!=null){
3. reverse(nextNode,nextNode.next);
4. }else{
5. //如果该节点是表尾，那么用头节点指向此节点
6. header.next = nextNode;
7. }
8. //该节点的指针指向前一个节点P，并将节点P的指针设置为空
9. nextNode.next = node;
10. node.next = null;
11. }

来源： [http://tangyanbo.iteye.com/blog/1472811](http://tangyanbo.iteye.com/blog/1472811)

常用排序算法分析与实现（一）（Java版） - 数据结构 - Tech - ITeye论坛

您还未登录 ! 登录 注册

论坛首页 → 综合技术论坛 →

常用排序算法分析与实现（一）（Java版）

全部 Linux 数据库 敏捷编程 数据结构 软件测试 项目管理 编程综合 Oracle Erlang 互联网 MySQL Java开发新方式：专注UI，快速开发

« 上一页 1 2 下一页 » 浏览 20153 次 锁定老帖子 主题：常用排序算法分析与实现（一）（Java版）

精华帖 (14) :: 良好帖 (6) :: 新手帖 (0) :: 隐藏帖 (0) 作者 正文 * junJZ_2008

• 等级:
• 
• 性别:
• 文章: 54
• 积分: 160
• 来自: 湖南澧縣
• 发表时间：2009-12-13 最后修改：2010-01-21

< > 猎头职位: 上海: Junior Product Manager

相关文章:

• 常用排序算法分析与实现（二）（Java版）
• 用JAVA实现的9种排序算法（二）
• java的8种排序 推荐群组: JAVA 3T 更多相关推荐 数据结构

这篇排序文章从思想 理解 到实现，然后到整理，花了我几天的时间，现把它记录于此，希望对大家有一定的帮助，写的不好的请不要见笑，写错了的，请指出来我更正。最后如果对你有一定的帮助，请回贴支持一下哦^_^ ！

申明： 排序算法思想来自互联网，代码自己实现，仅供参考。

• 插入排序

直接插入排序、希尔排序

• 选择排序

简单选择排序、堆排序

• 交换排序

冒泡排序、快速排序

• 归并排序

• 基数排序

排序基类

Java代码

1. package sort;
3. import java.util.Arrays;
4. import java.util.Comparator;
5. import java.util.Random;
7. ///
8. /* 排序接口，所有的排序算法都要继承该抽象类，并且要求数组中的
9. /* 元素要具有比较能力，即数组元素已实现了Comparable接口
10. /*
11. /* @author jzj
12. /* @date 2009-12-5
13. /*
14. /* @param
15. /*/
16. public abstract class Sort> {
18. public final Comparator DEFAULT_ORDER = new DefaultComparator();
19. public final Comparator REVERSE_ORDER = new ReverseComparator();
21. ///
22. /* 排序算法，需实现，对数组中指定的元素进行排序
23. /* @param array 待排序数组
24. /* @param from 从哪里
25. /* @param end 排到哪里
26. /* @param c
27. /*/
28. public abstract void sort(E[] array, int from, int end, Comparator c);
30. ///
31. /* 对数组中指定部分进行排序
32. /* @param from 从哪里
33. /* @param len 排到哪里
34. /* @param array 待排序数组
35. /* @param c 比较器
36. /*/
37. public void sort(int from, int len, E[] array, Comparator c) {
38. sort(array, 0, array.length - 1, c);
39. }
41. ///
42. /* 对整个数组进行排序，可以使用自己的排序比较器，也可使用该类提供的两个比较器
43. /* @param array 待排序数组
44. /* @param c 比较器
45. /*/
46. public final void sort(E[] array, Comparator c) {
47. sort(0, array.length, array, c);
48. }
50. ///
51. /* 对整个数组进行排序，采用默认排序比较器
52. /* @param array 待排序数组
53. /*/
54. public final void sort(E[] array) {
55. sort(0, array.length, array, this.DEFAULT_ORDER);
56. }
58. //默认比较器（一般为升序，但是否真真是升序还得看E是怎样实现Comparable接口的）
59. private class DefaultComparator implements Comparator {
60. public int compare(E o1, E o2) {
61. return o1.compareTo(o2);
62. }
63. }
65. //反序比较器，排序刚好与默认比较器相反
66. private class ReverseComparator implements Comparator {
67. public int compare(E o1, E o2) {
68. return o2.compareTo(o1);
69. }
70. }
72. ///
73. /* 交换数组中的两个元素的位置
74. /* @param array 待交换的数组
75. /* @param i 第一个元素
76. /* @param j 第二个元素
77. /*/
78. protected final void swap(E[] array, int i, int j) {
79. if (i != j) {//只有不是同一位置时才需交换
80. E tmp = array[i];
81. array[i] = array[j];
82. array[j] = tmp;
83. }
84. }
86. ///
87. /* 数组元素后移
88. /* @param array 待移动的数组
89. /* @param startIndex 从哪个开始移
90. /* @param endIndex 到哪个元素止
91. /*/
92. protected final void move(E[] array, int startIndex, int endIndex) {
93. for (int i = endIndex; i >= startIndex; i--) {
94. array[i + 1] = array[i];
95. }
96. }
98. ///
99. /* 以指定的步长将数组元素后移，步长指定每个元素间的间隔
100. /* @param array 待排序数组
101. /* @param startIndex 从哪里开始移
102. /* @param endIndex 到哪个元素止
103. /* @param step 步长
104. /*/
105. protected final void move(E[] array, int startIndex, int endIndex, int step) {
106. for (int i = endIndex; i >= startIndex; i -= step) {
107. array[i + step] = array[i];
108. }
109. }
111. //测试方法
112. @SuppressWarnings("unchecked")
113. public static final > void testSort(Sort sorter, E[] array) {
115. if (array == null) {
116. array = randomArray();
117. }
118. //为了第二次排序，需拷贝一份
119. E[] tmpArr = (E[]) new Comparable[array.length];
120. System.arraycopy(array, 0, tmpArr, 0, array.length);
122. System.out.println("源 - " + Arrays.toString(tmpArr));
124. sorter.sort(array, sorter.REVERSE_ORDER);
125. System.out.println("降 - " + Arrays.toString(array));
127. sorter.sort(tmpArr, sorter.DEFAULT_ORDER);
128. System.out.println("升 - " + Arrays.toString(tmpArr));
129. }
131. //生成随机数组
132. @SuppressWarnings("unchecked")
133. private static > E[] randomArray() {
134. Random r = new Random(System.currentTimeMillis());
135. Integer[] a = new Integer[r.nextInt(30)];
136. for (int i = 0; i < a.length; i++) {
137. a[i] = new Integer(r.nextInt(100));
138. }
139. return (E[]) a;
140. }
141. }
     package sort; import java.util.Arrays; import java.util.Comparator; import java.util.Random; /// / 排序接口，所有的排序算法都要继承该抽象类，并且要求数组中的 / 元素要具有比较能力，即数组元素已实现了Comparable接口 / / @author jzj / @date 2009-12-5 / / @param // public abstract class Sort> { public final Comparator DEFAULT_ORDER = new DefaultComparator(); public final Comparator REVERSE_ORDER = new ReverseComparator(); /// / 排序算法，需实现，对数组中指定的元素进行排序 / @param array 待排序数组 / @param from 从哪里 / @param end 排到哪里 / @param c // public abstract void sort(E[] array, int from, int end, Comparator c); /// / 对数组中指定部分进行排序 / @param from 从哪里 / @param len 排到哪里 / @param array 待排序数组 / @param c 比较器 // public void sort(int from, int len, E[] array, Comparator c) { sort(array, 0, array.length - 1, c); } /// / 对整个数组进行排序，可以使用自己的排序比较器，也可使用该类提供的两个比较器 / @param array 待排序数组 / @param c 比较器 // public final void sort(E[] array, Comparator c) { sort(0, array.length, array, c); } /// / 对整个数组进行排序，采用默认排序比较器 / @param array 待排序数组 // public final void sort(E[] array) { sort(0, array.length, array, this.DEFAULT_ORDER); } //默认比较器（一般为升序，但是否真真是升序还得看E是怎样实现Comparable接口的） private class DefaultComparator implements Comparator { public int compare(E o1, E o2) { return o1.compareTo(o2); } } //反序比较器，排序刚好与默认比较器相反 private class ReverseComparator implements Comparator { public int compare(E o1, E o2) { return o2.compareTo(o1); } } /// / 交换数组中的两个元素的位置 / @param array 待交换的数组 / @param i 第一个元素 / @param j 第二个元素 // protected final void swap(E[] array, int i, int j) { if (i != j) {//只有不是同一位置时才需交换 E tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } /// / 数组元素后移 / @param array 待移动的数组 / @param startIndex 从哪个开始移 / @param endIndex 到哪个元素止 // protected final void move(E[] array, int startIndex, int endIndex) { for (int i = endIndex; i >= startIndex; i--) { array[i + 1] = array[i]; } } /// / 以指定的步长将数组元素后移，步长指定每个元素间的间隔 / @param array 待排序数组 / @param startIndex 从哪里开始移 / @param endIndex 到哪个元素止 / @param step 步长 /*/ protected final void move(E[] array, int startIndex, int endIndex, int step) { for (int i = endIndex; i >= startIndex; i -= step) { array[i + step] = array[i]; } } //测试方法 @SuppressWarnings("unchecked") public static final > void testSort(Sort sorter, E[] array) { if (array == null) { array = randomArray(); } //为了第二次排序，需拷贝一份 E[] tmpArr = (E[]) new Comparable[array.length]; System.arraycopy(array, 0, tmpArr, 0, array.length); System.out.println("源 - " + Arrays.toString(tmpArr)); sorter.sort(array, sorter.REVERSE_ORDER); System.out.println("降 - " + Arrays.toString(array)); sorter.sort(tmpArr, sorter.DEFAULT_ORDER); System.out.println("升 - " + Arrays.toString(tmpArr)); } //生成随机数组 @SuppressWarnings("unchecked") private static > E[] randomArray() { Random r = new Random(System.currentTimeMillis()); Integer[] a = new Integer[r.nextInt(30)]; for (int i = 0; i < a.length; i++) { a[i] = new Integer(r.nextInt(100)); } return (E[]) a; } }

插入排序

直接插入排序

一般直接插入排序的时间复杂度为O ( n^2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n )，另外，因直接插入排序算法简单，如果待排序列规模不很大时效率也较高。

在已经排好序的序列中查找待插入的元素的插入位置，并将待插入元素插入到有序列表中的过程。

将数组分成两部分，初始化时，前部分数组为只有第一个元素，用来存储已排序元素，我们这里叫 arr1 ；后部分数组的元素为除第一个元素的所有元素，为待排序或待插入元素，我们这里叫 arr2 。 排序时使用二层循环：第一层对 arr2 进行循环，每次取后部分数组（待排序数组）里的第一个元素（我们称为待排序元素或称待插入元素） e1 ，然后在第二层循环中对 arr1 （已排好序的数组）从第一个元素往后进行循环，查到第一个大于待插入元素（如果是升序排列）或第一个小于待插入元素（如果是降序排列） e2 ，然后对 arr1 从 e2 元素开始往后的所有元素向后移，最后把 e1 插入到原来 e2 所在的位置。这样反复地对 arr2 进行循环，直到 arr2 中所有的待插入的元素都插入到 arr1 中。 Java代码

1. package sort;
3. import java.util.Comparator;
5. ///
6. /* 直接插入排序算法
7. /* @author jzj
8. /* @date 2009-12-5
9. /*
10. /* @param
11. /*/
12. public class InsertSort> extends Sort {
14. ///
15. /* 排序算法的实现，对数组中指定的元素进行排序
16. /* @param array 待排序的数组
17. /* @param from 从哪里开始排序
18. /* @param end 排到哪里
19. /* @param c 比较器
20. /*/
21. public void sort(E[] array, int from, int end, Comparator c) {
23. //*
24. /* 第一层循环：对待插入（排序）的元素进行循环
25. /* 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止
26. /*/
27. for (int i = from + 1; i <= end; i++) {
28. //*
29. /* 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环
30. /* 找到第一个大于待插入的元素
31. /* 有序数组初始元素只有一个，且为源数组的第一个元素，一个元素数组总是有序的
32. /*/
33. for (int j = 0; j < i; j++) {
34. E insertedElem = array[i];//待插入到有序数组的元素
35. //从有序数组中最一个元素开始查找第一个大于待插入的元素
36. if (c.compare(array[j], insertedElem) > 0) {
37. //找到插入点后，从插入点开始向后所有元素后移一位
38. move(array, j, i - 1);
39. //将待排序元素插入到有序数组中
40. array[j] = insertedElem;
41. break;
42. }
43. }
44. }
46. //=======以下是java.util.Arrays的插入排序算法的实现
47. //*
48. /* 该算法看起来比较简洁一j点，有点像冒泡算法。
49. /* 将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的元素，而后面集合为待排序的
50. /* 集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，从前面集合最后一个元素开
51. /* 始往前比较，如果发现前面元素大于后面元素，则交换，否则循环退出
52. /*
53. /* 总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入点，而后再将待排序的元素插
54. /* 入到的插入点上，那么其他元素就必然向后移，感觉算法与排序名称不匹，但返过来与上面实
55. /* 现比，其实是一样的，只是上面先找插入点，待找到后一次性将大的元素向后移，而该算法却
56. /* 是走一步看一步，一步一步将待排序元素往前移
57. /*/
58. //*
59. for (int i = from; i <= end; i++) {
60. for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; j--) {
61. swap(array, j, j - 1);
62. }
63. }
64. /*/
65. }
67. ///
68. /* 测试
69. /* @param args
70. /*/
71. public static void main(String[] args) {
72. Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };
73. InsertSort insertSort = new InsertSort();
74. Sort.testSort(insertSort, intgArr);
75. Sort.testSort(insertSort, null);
76. }
77. }
    package sort; import java.util.Comparator; /// / 直接插入排序算法 / @author jzj / @date 2009-12-5 / / @param // public class InsertSort> extends Sort { /// / 排序算法的实现，对数组中指定的元素进行排序 / @param array 待排序的数组 / @param from 从哪里开始排序 / @param end 排到哪里 / @param c 比较器 // public void sort(E[] array, int from, int end, Comparator c) { // / 第一层循环：对待插入（排序）的元素进行循环 / 从待排序数组断的第二个元素开始循环，到最后一个元素（包括）止 // for (int i = from + 1; i <= end; i++) { // / 第二层循环：对有序数组进行循环，且从有序数组最第一个元素开始向后循环 / 找到第一个大于待插入的元素 / 有序数组初始元素只有一个，且为源数组的第一个元素，一个元素数组总是有序的 // for (int j = 0; j < i; j++) { E insertedElem = array[i];//待插入到有序数组的元素 //从有序数组中最一个元素开始查找第一个大于待插入的元素 if (c.compare(array[j], insertedElem) > 0) { //找到插入点后，从插入点开始向后所有元素后移一位 move(array, j, i - 1); //将待排序元素插入到有序数组中 array[j] = insertedElem; break; } } } //=======以下是java.util.Arrays的插入排序算法的实现 // / 该算法看起来比较简洁一j点，有点像冒泡算法。 / 将数组逻辑上分成前后两个集合，前面的集合是已经排序好序的元素，而后面集合为待排序的 / 集合，每次内层循从后面集合中拿出一个元素，通过冒泡的形式，从前面集合最后一个元素开 / 始往前比较，如果发现前面元素大于后面元素，则交换，否则循环退出 / / 总感觉这种算术有点怪怪，既然是插入排序，应该是先找到插入点，而后再将待排序的元素插 / 入到的插入点上，那么其他元素就必然向后移，感觉算法与排序名称不匹，但返过来与上面实 / 现比，其实是一样的，只是上面先找插入点，待找到后一次性将大的元素向后移，而该算法却 / 是走一步看一步，一步一步将待排序元素往前移 // // for (int i = from; i <= end; i++) { for (int j = i; j > from && c.compare(array[j - 1], array[j]) > 0; j--) { swap(array, j, j - 1); } } // } /// / 测试 / @param args /*/ public static void main(String[] args) { Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 }; InsertSort insertSort = new InsertSort(); Sort.testSort(insertSort, intgArr); Sort.testSort(insertSort, null); } }

插入排序算法对于大数组，这种算法非常慢。但是对于小数组，它比其他算法快。其他算法因为待的数组元素很少，反而使得效率降低。在Java集合框架中，排序都是借助于java.util.Arrays来完成的，其中排序算法用到了插入排序、快速排序、归并排序。插入排序用于元素个数小于7的子数组排序，通常比插入排序快的其他排序方法，由于它们强大的算法是针对大数量数组设计的，所以元素个数少时速度反而慢。

希尔排序

希尔思想介绍

希尔算法的本质是缩小增量排序，是对直接插入排序算法的改进。一般直接插入排序的时间复杂度为O ( n^2 ) ，但是当数列基本有序时，如果按照有数列顺序排时，时间复杂度将改善到O( n )，另外,因直接插入排序算法简单,如果待排序列规模不很大时效率也较高，Shell 根据这两点分析结果进行了改进，将待排记录序列以一定的增量间隔h 分割成多个子序列，对每个子序列分别进行一趟直接插入排序, 然后逐步减小分组的步长h ，对于每一个步长h 下的各个子序列进行同样方法的排序,直到步长为1 时再进行一次整体排序。 因为不管记录序列多么庞大,关键字多么混乱,在先前较大的分组步长h 下每个子序列的规模都不大，用直接插入排序效率都较高。 尽管在随后的步长h 递减分组中子序列越来越大，但由于整个序列的有序性也越来越明显，则排序效率依然较高。这种改进抓住了直接插入排序的两点本质，大大提高了它的时间效率。

希尔增量研究

综上所述：

(1) 希尔排序的核心是以某个增量h 为步长跳跃分组进行插入排序，由于分组的步长h 逐步缩小，所以也叫“缩小增量排序”插入排序。其关键是如何选取分组的步长序列ht ,. . . , hk ,. . . , h1 , h0 才能使得希尔方法的时间效率最高；

(2) 待排序列记录的个数n 、跳跃分组步长逐步减小直到为1时所进行的扫描次数T、增量的和、记录关键字比较的次数以及记录移动的次数或各子序列中的反序数等因素都影响希尔算法的时间复杂度：其中记录关键字比较的次数是重要因素，它主要取决于分组步长序列的选择；

(3) 希尔方法是一种不稳定排序算法，因为其排序过程中各趟的步长不同，在第k 遍用hk作为步长排序之后，第k +1 遍排序时可能会遇到多个逆序存在，影响排序的稳定性。

试验结果表明,SHELL 算法的时间复杂度受增量序列的影响明显大于其他因素，选取恰当的增量序列能明显提高排序的时间效率，我们认为第k 趟排序扫描的增量步长为 2^k - 1 ,即增量序列为. . . 2^k - 1 ,. . . ,15 ,7 ,3 ,1时较为理想，但它并不是唯一的最佳增量序列，这与其关联函数目前尚无确定解的理论结果是一致的。

Java代码

1. package sort;
3. import java.util.Comparator;
5. ///
6. /* 希尔排序算法
7. /* @author jzj
8. /* @date 2009-12-5
9. /*
10. /* @param
11. /*/
12. public class ShelltSort> extends Sort {
14. ///
15. /* 排序算法的实现，对数组中指定的元素进行排序
16. /* @param array 待排序的数组
17. /* @param from 从哪里开始排序
18. /* @param end 排到哪里
19. /* @param c 比较器
20. /*/
21. public void sort(E[] array, int from, int end, Comparator c) {
22. //初始步长，实质为每轮的分组数
23. int step = initialStep(end - from + 1);
25. //第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值
26. for (; step >= 1; step = (step + 1) / 2 - 1) {
27. //对每轮里的每个分组进行循环
28. for (int groupIndex = 0; groupIndex < step; groupIndex++) {
30. //对每组进行直接插入排序
31. insertSort(array, groupIndex, step, end, c);
32. }
33. }
34. }
36. ///
37. /* 直接插入排序实现
38. /* @param array 待排序数组
39. /* @param groupIndex 对每轮的哪一组进行排序
40. /* @param step 步长
41. /* @param end 整个数组要排哪个元素止
42. /* @param c 比较器
43. /*/
44. private void insertSort(E[] array, int groupIndex, int step, int end, Comparator c) {
45. int startIndex = groupIndex;//从哪里开始排序
46. int endIndex = startIndex;//排到哪里
47. //*
48. /* 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内，
49. /* 如果在数组范围内，则继续循环，直到索引超现数组范围
50. /*/
51. while ((endIndex + step) <= end) {
52. endIndex += step;
53. }
55. // i为每小组里的第二个元素开始
56. for (int i = groupIndex + step; i <= end; i += step) {
57. for (int j = groupIndex; j < i; j += step) {
58. E insertedElem = array[i];
59. //从有序数组中最一个元素开始查找第一个大于待插入的元素
60. if (c.compare(array[j], insertedElem) >= 0) {
61. //找到插入点后，从插入点开始向后所有元素后移一位
62. move(array, j, i - step, step);
63. array[j] = insertedElem;
64. break;
65. }
66. }
67. }
68. }
70. ///
71. /* 根据数组长度求初始步长
72. /*
73. /* 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k
74. /* 为排序轮次
75. /*
76. /* 初始步长：step = 2^k-1
77. /* 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值（因
78. /* 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4）
79. /*
80. /* 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把 2^k 表 达式
81. / 转换成 step 表达式，则 2^k-1 可使用 (step + 1)/2-1 替换（因为 step+1 相当于第k-1
82. /* 轮的步长，所以在 step+1 基础上乘以 2 就相当于 2^k 了），即步长与数组长度的关系不等式为
83. / (step + 1)/2 - 1 < len -1
84. /*
85. /* @param len 数组长度
86. /* @return
87. /*/
88. private static int initialStep(int len) {
89. //*
90. /* 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推:
91. /* 1,3,7,15,...,2^(k-1)-1,2^k-1
92. /* 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不且分组，此时直接退化为直接插
93. /* 入排序
94. /*/
95. int step = 1;
97. //试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长
98. while ((step + 1) /* 2 - 1 < len - 1) {
99. step = (step + 1) /* 2 - 1;
100. }
102. System.out.println("初始步长 - " + step);
103. return step;
104. }
106. ///
107. /* 测试
108. /* @param args
109. /*/
110. public static void main(String[] args) {
111. Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 10 };
112. ShelltSort shellSort = new ShelltSort();
113. Sort.testSort(shellSort, intgArr);
114. Sort.testSort(shellSort, null);
115. }
116. }
     package sort; import java.util.Comparator; /// / 希尔排序算法 / @author jzj / @date 2009-12-5 / / @param // public class ShelltSort> extends Sort { /// / 排序算法的实现，对数组中指定的元素进行排序 / @param array 待排序的数组 / @param from 从哪里开始排序 / @param end 排到哪里 / @param c 比较器 // public void sort(E[] array, int from, int end, Comparator c) { //初始步长，实质为每轮的分组数 int step = initialStep(end - from + 1); //第一层循环是对排序轮次进行循环。(step + 1) / 2 - 1 为下一轮步长值 for (; step >= 1; step = (step + 1) / 2 - 1) { //对每轮里的每个分组进行循环 for (int groupIndex = 0; groupIndex < step; groupIndex++) { //对每组进行直接插入排序 insertSort(array, groupIndex, step, end, c); } } } /// / 直接插入排序实现 / @param array 待排序数组 / @param groupIndex 对每轮的哪一组进行排序 / @param step 步长 / @param end 整个数组要排哪个元素止 / @param c 比较器 // private void insertSort(E[] array, int groupIndex, int step, int end, Comparator c) { int startIndex = groupIndex;//从哪里开始排序 int endIndex = startIndex;//排到哪里 // / 排到哪里需要计算得到，从开始排序元素开始，以step步长，可求得下元素是否在数组范围内， / 如果在数组范围内，则继续循环，直到索引超现数组范围 // while ((endIndex + step) <= end) { endIndex += step; } // i为每小组里的第二个元素开始 for (int i = groupIndex + step; i <= end; i += step) { for (int j = groupIndex; j < i; j += step) { E insertedElem = array[i]; //从有序数组中最一个元素开始查找第一个大于待插入的元素 if (c.compare(array[j], insertedElem) >= 0) { //找到插入点后，从插入点开始向后所有元素后移一位 move(array, j, i - step, step); array[j] = insertedElem; break; } } } } /// / 根据数组长度求初始步长 / / 我们选择步长的公式为：2^k-1,2^(k-1)-1,...,15,7,3,1 ，其中2^k 减一即为该步长序列，k / 为排序轮次 / / 初始步长：step = 2^k-1 / 初始步长约束条件：step < len - 1 初始步长的值要小于数组长度还要减一的值（因 / 为第一轮分组时尽量不要分为一组，除非数组本身的长度就小于等于4） / / 由上面两个关系试可以得知：2^k - 1 < len - 1 关系式，其中k为轮次，如果把 2^k 表 达式 / 转换成 step 表达式，则 2^k-1 可使用 (step + 1)/2-1 替换（因为 step+1 相当于第k-1 / 轮的步长，所以在 step+1 基础上乘以 2 就相当于 2^k 了），即步长与数组长度的关系不等式为 / (step + 1)/2 - 1 < len -1 / / @param len 数组长度 / @return // private static int initialStep(int len) { // / 初始值设置为步长公式中的最小步长，从最小步长推导出最长初始步长值，即按照以下公式来推: / 1,3,7,15,...,2^(k-1)-1,2^k-1 / 如果数组长度小于等于4时，步长为1，即长度小于等于4的数组不且分组，此时直接退化为直接插 / 入排序 // int step = 1; //试探下一个步长是否满足条件，如果满足条件，则步长置为下一步长 while ((step + 1) / 2 - 1 < len - 1) { step = (step + 1) / 2 - 1; } System.out.println("初始步长 - " + step); return step; } /// / 测试 / @param args /*/ public static void main(String[] args) { Integer[] intgArr = { 5, 9, 1, 4, 8, 2, 6, 3, 7, 10 }; ShelltSort shellSort = new ShelltSort(); Sort.testSort(shellSort, intgArr); Sort.testSort(shellSort, null); } }

选择排序

简单选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序不像冒泡排序算法那样先并不急于调换位置，第一轮（k=1）先从array[k]开始逐个检查，看哪个数最小就记下该数所在的位置于minlIndex中，等一轮扫描完毕，如果找到比array[k-1]更小的元素，则把array[minlIndex]和a[k-1]对调，这时array[k]到最后一个元素中最小的元素就换到了array[k-1]的位置。 如此反复进行第二轮、第三轮…直到循环至最后一元素 Java代码

1. package sort;
3. import java.util.Comparator;
5. ///
6. /* 简单选择排序算法
7. /* @author jzj
8. /* @date 2009-12-5
9. /*
10. /* @param
11. /*/
12. public class SelectSort> extends Sort {
14. ///
15. /* 排序算法的实现，对数组中指定的元素进行排序
16. /* @param array 待排序的数组
17. /* @param from 从哪里开始排序
18. /* @param end 排到哪里
19. /* @param c 比较器
20. /*/
21. public void sort(E[] array, int from, int end, Comparator c) {
22. int minlIndex;//最小索引
23. //*
24. /* 循环整个数组（其实这里的上界为 array.length - 1 即可，因为当 i= array.length-1
25. /* 时，最后一个元素就已是最大的了，如果为array.length时，内层循环将不再循环），每轮假设
26. /* 第一个元素为最小元素，如果从第一元素后能选出比第一个元素更小元素，则让让最小元素与第一
27. /* 个元素交换
28. /*/
29. for (int i = from; i <= end; i++) {
30. minlIndex = i;//假设每轮第一个元素为最小元素
31. //从假设的最小元素的下一元素开始循环
32. for (int j = i + 1; j <= end; j++) {
33. //如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于smallIndex中
34. if (c.compare(array[j], array[minlIndex]) < 0) {
35. minlIndex = j;
36. }
37. }
39. //先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一个元素交换
40. swap(array, i, minlIndex);
41. }
42. }
44. ///
45. /* 测试
46. /* @param args
47. /*/
48. public static void main(String[] args) {
49. Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 };
50. SelectSort insertSort = new SelectSort();
51. Sort.testSort(insertSort, intgArr);
52. Sort.testSort(insertSort, null);
53. }
54. }
    package sort; import java.util.Comparator; /// / 简单选择排序算法 / @author jzj / @date 2009-12-5 / / @param // public class SelectSort> extends Sort { /// / 排序算法的实现，对数组中指定的元素进行排序 / @param array 待排序的数组 / @param from 从哪里开始排序 / @param end 排到哪里 / @param c 比较器 // public void sort(E[] array, int from, int end, Comparator c) { int minlIndex;//最小索引 // / 循环整个数组（其实这里的上界为 array.length - 1 即可，因为当 i= array.length-1 / 时，最后一个元素就已是最大的了，如果为array.length时，内层循环将不再循环），每轮假设 / 第一个元素为最小元素，如果从第一元素后能选出比第一个元素更小元素，则让让最小元素与第一 / 个元素交换 // for (int i = from; i <= end; i++) { minlIndex = i;//假设每轮第一个元素为最小元素 //从假设的最小元素的下一元素开始循环 for (int j = i + 1; j <= end; j++) { //如果发现有比当前array[smallIndex]更小元素，则记下该元素的索引于smallIndex中 if (c.compare(array[j], array[minlIndex]) < 0) { minlIndex = j; } } //先前只是记录最小元素索引，当最小元素索引确定后，再与每轮的第一个元素交换 swap(array, i, minlIndex); } } /// / 测试 / @param args /*/ public static void main(String[] args) { Integer[] intgArr = { 5, 9, 1, 4, 1, 2, 6, 3, 8, 0, 7 }; SelectSort insertSort = new SelectSort(); Sort.testSort(insertSort, intgArr); Sort.testSort(insertSort, null); } }

堆排序

堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示：

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。

堆是一种完全二叉树，一般使用数组来实现。堆排序也是一种选择性的排序，每次选择第i大的元素。

另外排序过程中借助了堆结构，堆就是一种完全二叉树，所以这里先要熟悉要用的二叉树几个性质：

N（N>1）个节点的的完全二叉树从层次从左自右编号，最后一个分枝节点（非叶子节点）的编号为 N/2 取整。

且对于编号 i（1<=i<=N）有：父节点为 i/2 向下取整；若2i>N，则节点i没有左孩子，否则其左孩子为2i；若2i+1>N，则没有右孩子，否则其右孩子为2i+1。

注，这里使用完全二叉树只是为了好描述算法，它只是一种逻辑结构，真真在实现时我们还是使用数组来存储这棵二叉树的，因为完全二叉树完全可以使用数组来存储。

算法描述：

堆排序其实最主要的两个过程：第一步，创建初始堆；第二步，交换根节点与最后一个非叶子节

第一步实现 ：从最后一个非叶子节点为开始向前循环每个会支节点，比较每个分支节点与他左右子节点，如果其中某个子节点比父节点大，则与父节点交换，交换后原父节点可能还小于原子节点的子节点，所以还需对原父节点进行调整，使用原父节点继续下沉，直到没有子节点或比左右子节点都大为止，调用过程可通过递归完成。当某个非叶子节点调整完毕后，再处理下一个非叶子节点，直到根节点也调整完成，这里初始堆就创建好了，这里我们创建的是大顶堆，即大的元素向树的根浮，这样排序最后得到的结果为升序，因为最大的从树中去掉，并从数组最后往前存放。

第二步实现 ：将树中的最后一个元素与堆顶元素进行交换，并从树中去掉最后叶子节点。交换后再按创建初始堆的算法调整根节点，如此下去直到树中只有一个节点为止。

Java代码

1. package sort;
3. import java.util.Comparator;
5. public class HeapSort> extends Sort {
7. ///
8. /* 排序算法的实现，对数组中指定的元素进行排序
9. /* @param array 待排序的数组
10. /* @param from 从哪里开始排序
11. /* @param end 排到哪里
12. /* @param c 比较器
13. /*/
14. public void sort(E[] array, int from, int end, Comparator c) {
15. //创建初始堆
16. initialHeap(array, from, end, c);
18. //*
19. /* 对初始堆进行循环，且从最后一个节点开始，直接树只有两个节点止
20. /* 每轮循环后丢弃最后一个叶子节点，再看作一个新的树
21. /*/
22. for (int i = end - from + 1; i >= 2; i--) {
23. //根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一个元素互换
24. swap(array, from, i - 1);
25. //交换后需要重新调整堆
26. adjustNote(array, 1, i - 1, c);
27. }
29. }
31. ///
32. /* 初始化堆
33. /* 比如原序列为：7,2,4,3,12,1,9,6,8,5,10,11
34. /* 则初始堆为：1,2,4,3,5,7,9,6,8,12,10,11
35. /* @param arr 排序数组
36. /* @param from 从哪
37. /* @param end 到哪
38. /* @param c 比较器
39. /*/
40. private void initialHeap(E[] arr, int from, int end, Comparator c) {
41. int lastBranchIndex = (end - from + 1) / 2;//最后一个非叶子节点
42. //对所有的非叶子节点进行循环 ，且从最一个非叶子节点开始
43. for (int i = lastBranchIndex; i >= 1; i--) {
44. adjustNote(arr, i, end - from + 1, c);
45. }
46. }
48. ///
49. /* 调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与父节点转换
50. /* @param arr 待排序数组
51. /* @param parentNodeIndex 要调整的节点，与它的子节点一起进行调整
52. /* @param len 树的节点数
53. /* @param c 比较器
54. /*/
55. private void adjustNote(E[] arr, int parentNodeIndex, int len, Comparator c) {
56. int minNodeIndex = parentNodeIndex;
57. //如果有左子树，i /* 2为左子节点索引
58. if (parentNodeIndex /* 2 <= len) {
59. //如果父节点小于左子树时
60. if (c.compare(arr[parentNodeIndex - 1], arr[parentNodeIndex /* 2 - 1]) < 0) {
61. minNodeIndex = parentNodeIndex /* 2;//记录最大索引为左子节点索引
62. }
64. // 只有在有或子树的前提下才可能有右子树，再进一步断判是否有右子树
65. if (parentNodeIndex /* 2 + 1 <= len) {
66. //如果右子树比最大节点更大
67. if (c.compare(arr[minNodeIndex - 1], arr[(parentNodeIndex /* 2 + 1) - 1]) < 0) {
68. minNodeIndex = parentNodeIndex /* 2 + 1;//记录最大索引为右子节点索引
69. }
70. }
71. }
73. //如果在父节点、左、右子节点三都中，最大节点不是父节点时需交换，把最大的与父节点交换，创建大顶堆
74. if (minNodeIndex != parentNodeIndex) {
75. swap(arr, parentNodeIndex - 1, minNodeIndex - 1);
76. //交换后可能需要重建堆，原父节点可能需要继续下沉
77. if (minNodeIndex /* 2 <= len) {//是否有子节点，注，只需判断是否有左子树即可知道
78. adjustNote(arr, minNodeIndex, len, c);
79. }
80. }
81. }
83. ///
84. /* 测试
85. /* @param args
86. /*/
87. public static void main(String[] args) {
88. Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 10, 11 };
89. HeapSort sort = new HeapSort();
90. HeapSort.testSort(sort, intgArr);
91. HeapSort.testSort(sort, null);
92. }
94. }
    package sort; import java.util.Comparator; public class HeapSort> extends Sort { /// / 排序算法的实现，对数组中指定的元素进行排序 / @param array 待排序的数组 / @param from 从哪里开始排序 / @param end 排到哪里 / @param c 比较器 // public void sort(E[] array, int from, int end, Comparator c) { //创建初始堆 initialHeap(array, from, end, c); // / 对初始堆进行循环，且从最后一个节点开始，直接树只有两个节点止 / 每轮循环后丢弃最后一个叶子节点，再看作一个新的树 // for (int i = end - from + 1; i >= 2; i--) { //根节点与最后一个叶子节点交换位置，即数组中的第一个元素与最后一个元素互换 swap(array, from, i - 1); //交换后需要重新调整堆 adjustNote(array, 1, i - 1, c); } } /// / 初始化堆 / 比如原序列为：7,2,4,3,12,1,9,6,8,5,10,11 / 则初始堆为：1,2,4,3,5,7,9,6,8,12,10,11 / @param arr 排序数组 / @param from 从哪 / @param end 到哪 / @param c 比较器 // private void initialHeap(E[] arr, int from, int end, Comparator c) { int lastBranchIndex = (end - from + 1) / 2;//最后一个非叶子节点 //对所有的非叶子节点进行循环 ，且从最一个非叶子节点开始 for (int i = lastBranchIndex; i >= 1; i--) { adjustNote(arr, i, end - from + 1, c); } } /// / 调整节点顺序，从父、左右子节点三个节点中选择一个最大节点与父节点转换 / @param arr 待排序数组 / @param parentNodeIndex 要调整的节点，与它的子节点一起进行调整 / @param len 树的节点数 / @param c 比较器 // private void adjustNote(E[] arr, int parentNodeIndex, int len, Comparator c) { int minNodeIndex = parentNodeIndex; //如果有左子树，i / 2为左子节点索引 if (parentNodeIndex / 2 <= len) { //如果父节点小于左子树时 if (c.compare(arr[parentNodeIndex - 1], arr[parentNodeIndex / 2 - 1]) < 0) { minNodeIndex = parentNodeIndex / 2;//记录最大索引为左子节点索引 } // 只有在有或子树的前提下才可能有右子树，再进一步断判是否有右子树 if (parentNodeIndex / 2 + 1 <= len) { //如果右子树比最大节点更大 if (c.compare(arr[minNodeIndex - 1], arr[(parentNodeIndex / 2 + 1) - 1]) < 0) { minNodeIndex = parentNodeIndex / 2 + 1;//记录最大索引为右子节点索引 } } } //如果在父节点、左、右子节点三都中，最大节点不是父节点时需交换，把最大的与父节点交换，创建大顶堆 if (minNodeIndex != parentNodeIndex) { swap(arr, parentNodeIndex - 1, minNodeIndex - 1); //交换后可能需要重建堆，原父节点可能需要继续下沉 if (minNodeIndex / 2 <= len) {//是否有子节点，注，只需判断是否有左子树即可知道 adjustNote(arr, minNodeIndex, len, c); } } } /// / 测试 / @param args /*/ public static void main(String[] args) { Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 10, 11 }; HeapSort sort = new HeapSort(); HeapSort.testSort(sort, intgArr); HeapSort.testSort(sort, null); } }

• 

• 大小: 32.8 KB

• 

• 大小: 81.4 KB

• 

• 大小: 35 KB

• 

• 大小: 14.9 KB

• 

• 大小: 139.3 KB

• 查看图片附件

声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。 推荐链接

• Java开发新方式：专注UI，快速开发！ 返回顶楼 * topcode
• 等级: 初级会员
• 
• 性别:
• 文章: 142
• 积分: 0
• 来自: 飙车之都
• 发表时间：2009-12-18

不错,挺详细的.只是有点老生常谈了 返回顶楼 回帖地址

0 0 请登录后投票 * junJZ_2008

• 等级:
• 
• 性别:
• 文章: 54
• 积分: 160
• 来自: 湖南澧縣
• 发表时间：2009-12-18

呵呵，以前只是知道这些理论知识罢了，从大学里就开始学这些理论，一直没有去实现它，直到现在才下点狠心看能否实现！@ 返回顶楼 回帖地址

0 0 请登录后投票 * aixinnature

• 等级: 初级会员
• 
• 性别:
• 文章: 55
• 积分: 40
• 来自: 北京
• 发表时间：2009-12-23

写的非常好，原理说的很清楚了，代码也注释的详尽! 返回顶楼 回帖地址

0 0 请登录后投票 * dapp66

• 等级: 初级会员
• 
• 性别:
• 文章: 6
• 积分: 40
• 来自: 深圳
• 发表时间：2010-01-04

真是不错，正好看看。写的很详细的 返回顶楼 回帖地址

0 0 请登录后投票 * JavaLet

• 等级: 初级会员
• 
• 文章: 6
• 积分: 62
• 发表时间：2010-03-17

我认为这是我看到的最详细的文章，有图有代码 返回顶楼 回帖地址

0 0 请登录后投票 * 我不说话

• 等级: 初级会员
• 
• 性别:
• 文章: 13
• 积分: 30
• 来自: 深圳
• 发表时间：2010-04-27

没久没看这些东西了，都忘了（当然当初也没啃透，不然怎么会忘了 ） 返回顶楼 回帖地址

0 0 请登录后投票 * Heart.X.Raid

• 等级:
• 
• 性别:
• 文章: 72
• 积分: 530
• 来自: 武汉
• 发表时间：2010-04-28

算法不要用Java写，不能自由的控制内存，有的时候很难在效率上改进。 返回顶楼 回帖地址

0 0 请登录后投票 * lixia0417

• 等级: 初级会员
• 
• 性别:
• 文章: 24
• 积分: 30
• 来自: 广州
• 发表时间：2010-07-03

楼主，写得实在是太详细了，对我这种数据结构知识不好的人帮助很大，呵呵 返回顶楼 回帖地址

0 0 请登录后投票 * rmn190

• 等级:
• 
• 性别:
• 文章: 354
• 积分: 120
• 来自: 北京
• 发表时间：2010-08-22

楼主写的很详细啊， 谢谢分享！ 返回顶楼 回帖地址

0 0 请登录后投票

« 上一页 1 2 下一页 » 论坛首页 → 综合技术版 跳转论坛:移动开发技术 Web前端技术 Java企业应用 编程语言技术 综合技术 入门技术 招聘求职 海阔天空

• 首页
• 资讯
• 精华
• 论坛
• 问答
• 博客
• 专栏
• 群组
• 招聘
• 搜索
• 广告服务
• ITeye黑板报
• 联系我们
• 友情链接

© 2003-2012 ITeye.com. [ 京ICP证110151号 京公网安备110105010620 ] 百联优力(北京)投资有限公司 版权所有