名称 Java语言编码规范(Java Code Conventions)
丰泽网站建设公司创新互联公司,丰泽网站设计制作，有大型网站制作公司丰富经验。已为丰泽超过千家提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱，请找那个售后服务好的丰泽做网站的公司定做！
简介 本文档讲述了Java语言的编码规范，较之陈世忠先生《c++编码规范》的浩繁详尽，此文当属短小精悍了。而其中所列之各项条款，从编码风格，到注意事项，不单只Java，对于其他语言，也都很有借鉴意义。因为简短，所以易记，大家不妨将此作为handbook，常备案头，逐一对验。
1 介绍
1.1 为什么要有编码规范
1.2 版权声明
2 文件名
2.1 文件后缀
2.2 常用文件名
3 文件组织
3.1 Java源文件
3.1.1 开头注释
3.1.2 包和引入语句
3.1.3 类和接口声明
4 缩进排版
4.1 行长度
4.2 换行
5 注释
5.1 实现注释的格式
5.1.1 块注释
5.1.2 单行注释
5.1.3 尾端注释
5.1.4 行末注释
5.2 文挡注释
6 声明
6.1 每行声明变量的数量
6.2 初始化
6.3 布局
6.4 类和接口的声明
7 语句
7.1 简单语句
7.2 复合语句
7.3 返回语句
7.4 if，if-else，if else-if else语句
7.5 for语句
7.6 while语句
7.7 do-while语句
7.8 switch语句
7.9 try-catch语句
8 空白
8.1 空行
8.2 空格
9 命名规范
10 编程惯例
10.1 提供对实例以及类变量的访问控制
10.2 引用类变量和类方法
10.3 常量
10.4 变量赋值
10.5 其它惯例
10.5.1 圆括号
10.5.2 返回值
10.5.3 条件运算符"?"前的表达式"?"前的表达式
10.5.4 特殊注释
11 代码范例
11.1 Java源文件范例
1 介绍(Introduction)
1.1 为什么要有编码规范(Why Have Code Conventions)
编码规范对于程序员而言尤为重要，有以下几个原因：
- 一个软件的生命周期中，80%的花费在于维护
- 几乎没有任何一个软件，在其整个生命周期中，均由最初的开发人员来维护
- 编码规范可以改善软件的可读性，可以让程序员尽快而彻底地理解新的代码
- 如果你将源码作为产品发布，就需要确任它是否被很好的打包并且清晰无误，一如你已构建的其它任何产品
为了执行规范，每个软件开发人员必须一致遵守编码规范。每个人。
1.2 版权声明(Acknowledgments)
本文档反映的是Sun MicroSystems公司，Java语言规范中的编码标准部分。主要贡献者包括：Peter King，Patrick Naughton，Mike DeMoney，Jonni Kanerva，Kathy Walrath以及Scott Hommel。
本文档现由Scott Hommel维护，有关评论意见请发至shommel@eng.sun.com
2 文件名(File Names)
这部分列出了常用的文件名及其后缀。
2.1 文件后缀(File Suffixes)
Java程序使用下列文件后缀：
文件类别 文件后缀
Java源文件 .java
Java字节码文件 .class
2.2 常用文件名(Common File Names)
常用的文件名包括：
文件名 用途
GNUmakefile makefiles的首选文件名。我们采用gnumake来创建（build）软件。
README 概述特定目录下所含内容的文件的首选文件名
3 文件组织(File Organization)
一个文件由被空行分割而成的段落以及标识每个段落的可选注释共同组成。超过2000行的程序难以阅读，应该尽量避免。"Java源文件范例"提供了一个布局合理的Java程序范例。
3.1 Java源文件(Java Source Files)
每个Java源文件都包含一个单一的公共类或接口。若私有类和接口与一个公共类相关联，可以将它们和公共类放入同一个源文件。公共类必须是这个文件中的第一个类或接口。
Java源文件还遵循以下规则：
- 开头注释（参见"开头注释"）
- 包和引入语句（参见"包和引入语句"）
- 类和接口声明（参见"类和接口声明"）
3.1.1 开头注释(Beginning Comments)
所有的源文件都应该在开头有一个C语言风格的注释，其中列出类名、版本信息、日期和版权声明：
/*
* Classname
*
* Version information
*
* Date
*
* Copyright notice
*/
3.1.2 包和引入语句(Package and Import Statements)
在多数Java源文件中，第一个非注释行是包语句。在它之后可以跟引入语句。例如：
package java.awt;
import java.awt.peer.CanvasPeer;
3.1.3 类和接口声明(Class and Interface Declarations)
下表描述了类和接口声明的各个部分以及它们出现的先后次序。参见"Java源文件范例"中一个包含注释的例子。
类/接口声明的各部分 注解
1 类/接口文档注释(/**……*/) 该注释中所需包含的信息，参见"文档注释"
2 类或接口的声明
3 类/接口实现的注释(/*……*/)如果有必要的话 该注释应包含任何有关整个类或接口的信息，而这些信息又不适合作为类/接口文档注释。
4 类的(静态)变量 首先是类的公共变量，随后是保护变量，再后是包一级别的变量(没有访问修饰符，access modifier)，最后是私有变量。
5 实例变量 首先是公共级别的，随后是保护级别的，再后是包一级别的(没有访问修饰符)，最后是私有级别的。
6 构造器
7 方法 这些方法应该按功能，而非作用域或访问权限，分组。例如，一个私有的类方法可以置于两个公有的实例方法之间。其目的是为了更便于阅读和理解代码。
4 缩进排版(Indentation)
4个空格常被作为缩进排版的一个单位。缩进的确切解释并未详细指定(空格 vs. 制表符)。一个制表符等于8个空格(而非4个)。
4.1 行长度(Line Length)
尽量避免一行的长度超过80个字符，因为很多终端和工具不能很好处理之。
注意：用于文档中的例子应该使用更短的行长，长度一般不超过70个字符。
4.2 换行(Wrapping Lines)
当一个表达式无法容纳在一行内时，可以依据如下一般规则断开之：
- 在一个逗号后面断开
- 在一个操作符前面断开
- 宁可选择较高级别(higher-level)的断开，而非较低级别(lower-level)的断开
- 新的一行应该与上一行同一级别表达式的开头处对齐
- 如果以上规则导致你的代码混乱或者使你的代码都堆挤在右边，那就代之以缩进8个空格。
以下是断开方法调用的一些例子：
someMethod(longExpression1, longExpression2, longExpression3,
longExpression4, longExpression5);
var = someMethod1(longExpression1,
someMethod2(longExpression2,
longExpression3));
以下是两个断开算术表达式的例子。前者更好，因为断开处位于括号表达式的外边，这是个较高级别的断开。
longName1 = longName2 * (longName3 + longName4 - longName5)
+ 4 * longname6; //PREFFER
longName1 = longName2 * (longName3 + longName4
- longName5) + 4 * longname6; //AVOID
以下是两个缩进方法声明的例子。前者是常规情形。后者若使用常规的缩进方式将会使第二行和第三行移得很靠右，所以代之以缩进8个空格
//CONVENTIONAL INDENTATION
someMethod(int anArg, Object anotherArg, String yetAnotherArg,
Object andStillAnother) {
...
}
//INDENT 8 SPACES TO AVOID VERY DEEP INDENTS
private static synchronized horkingLongMethodName(int anArg,
Object anotherArg, String yetAnotherArg,
Object andStillAnother) {
...
}
if语句的换行通常使用8个空格的规则，因为常规缩进(4个空格)会使语句体看起来比较费劲。比如：
//DON’T USE THIS INDENTATION
if ((condition1 condition2)
|| (condition3 condition4)
||!(condition5 condition6)) { //BAD WRAPS
doSomethingAboutIt(); //MAKE THIS LINE EASY TO MISS
}
//USE THIS INDENTATION INSTEAD
if ((condition1 condition2)
|| (condition3 condition4)
||!(condition5 condition6)) {
doSomethingAboutIt();
}
//OR USE THIS
if ((condition1 condition2) || (condition3 condition4)
||!(condition5 condition6)) {
doSomethingAboutIt();
}
这里有三种可行的方法用于处理三元运算表达式：
alpha = (aLongBooleanExpression) ? beta : gamma;
alpha = (aLongBooleanExpression) ? beta
: gamma;
alpha = (aLongBooleanExpression)
? beta
: gamma;
5 注释(Comments)
Java程序有两类注释：实现注释(implementation comments)和文档注释(document comments)。实现注释是那些在C++中见过的，使用/*...*/和//界定的注释。文档注释(被称为"doc comments")是Java独有的，并由/**...*/界定。文档注释可以通过javadoc工具转换成HTML文件。
实现注释用以注释代码或者实现细节。文档注释从实现自由(implementation-free)的角度描述代码的规范。它可以被那些手头没有源码的开发人员读懂。
注释应被用来给出代码的总括，并提供代码自身没有提供的附加信息。注释应该仅包含与阅读和理解程序有关的信息。例如，相应的包如何被建立或位于哪个目录下之类的信息不应包括在注释中。
在注释里，对设计决策中重要的或者不是显而易见的地方进行说明是可以的，但应避免提供代码中己清晰表达出来的重复信息。多余的的注释很容易过时。通常应避免那些代码更新就可能过时的注释。
注意：频繁的注释有时反映出代码的低质量。当你觉得被迫要加注释的时候，考虑一下重写代码使其更清晰。
注释不应写在用星号或其他字符画出来的大框里。注释不应包括诸如制表符和回退符之类的特殊字符。
5.1 实现注释的格式(Implementation Comment Formats)
程序可以有4种实现注释的风格：块(block)、单行(single-line)、尾端(trailing)和行末(end-of-line)。
5.1.1 块注释(Block Comments)
块注释通常用于提供对文件，方法，数据结构和算法的描述。块注释被置于每个文件的开始处以及每个方法之前。它们也可以被用于其他地方，比如方法内部。在功能和方法内部的块注释应该和它们所描述的代码具有一样的缩进格式。
块注释之首应该有一个空行，用于把块注释和代码分割开来，比如：
/*
* Here is a block comment.
*/
块注释可以以/*-开头，这样indent(1)就可以将之识别为一个代码块的开始，而不会重排它。
/*-
* Here is a block comment with some very special
* formatting that I want indent(1) to ignore.
*
* one
* two
* three
*/
注意：如果你不使用indent(1)，就不必在代码中使用/*-，或为他人可能对你的代码运行indent(1)作让步。
参见"文档注释"
5.1.2 单行注释(Single-Line Comments)
短注释可以显示在一行内，并与其后的代码具有一样的缩进层级。如果一个注释不能在一行内写完，就该采用块注释(参见"块注释")。单行注释之前应该有一个空行。以下是一个Java代码中单行注释的例子：
if (condition) {
/* Handle the condition. */
...
}
5.1.3 尾端注释(Trailing Comments)
极短的注释可以与它们所要描述的代码位于同一行，但是应该有足够的空白来分开代码和注释。若有多个短注释出现于大段代码中，它们应该具有相同的缩进。
以下是一个Java代码中尾端注释的例子：
if (a == 2) {
return TRUE; /* special case */
} else {
return isPrime(a); /* works only for odd a */
}
5.1.4 行末注释(End-Of-Line Comments)
注释界定符"//"，可以注释掉整行或者一行中的一部分。它一般不用于连续多行的注释文本；然而，它可以用来注释掉连续多行的代码段。以下是所有三种风格的例子：
if (foo 1) {
// Do a double-flip.
...
}
else {
return false; // Explain why here.
}
//if (bar 1) {
//
// // Do a triple-flip.
// ...
//}
//else {
// return false;
//}
5.2 文档注释(Documentation Comments)
注意：此处描述的注释格式之范例，参见"Java源文件范例"
若想了解更多，参见"How to Write Doc Comments for Javadoc"，其中包含了有关文档注释标记的信息(@return, @param, @see)：
若想了解更多有关文档注释和javadoc的详细资料，参见javadoc的主页：
文档注释描述Java的类、接口、构造器，方法，以及字段(field)。每个文档注释都会被置于注释定界符/**...*/之中，一个注释对应一个类、接口或成员。该注释应位于声明之前：
/**
* The Example class provides ...
*/
public class Example { ...
注意顶层(top-level)的类和接口是不缩进的，而其成员是缩进的。描述类和接口的文档注释的第一行(/**)不需缩进；随后的文档注释每行都缩进1格(使星号纵向对齐)。成员，包括构造函数在内，其文档注释的第一行缩进4格，随后每行都缩进5格。
若你想给出有关类、接口、变量或方法的信息，而这些信息又不适合写在文档中，则可使用实现块注释(见5.1.1)或紧跟在声明后面的单行注释(见5.1.2)。例如，有关一个类实现的细节，应放入紧跟在类声明后面的实现块注释中，而不是放在文档注释中。
文档注释不能放在一个方法或构造器的定义块中，因为Java会将位于文档注释之后的第一个声明与其相关联。
6 声明(Declarations)
6.1 每行声明变量的数量(Number Per Line)
推荐一行一个声明，因为这样以利于写注释。亦即，
int level; // indentation level
int size; // size of table
要优于，
int level, size;
不要将不同类型变量的声明放在同一行，例如：
int foo, fooarray[]; //WRONG!
注意：上面的例子中，在类型和标识符之间放了一个空格，另一种被允许的替代方式是使用制表符：
int level; // indentation level
int size; // size of table
Object currentEntry; // currently selected table entry
6.2 初始化(Initialization)
尽量在声明局部变量的同时初始化。唯一不这么做的理由是变量的初始值依赖于某些先前发生的计算。
6.3 布局(Placement)
只在代码块的开始处声明变量。（一个块是指任何被包含在大括号"{"和"}"中间的代码。）不要在首次用到该变量时才声明之。这会把注意力不集中的程序员搞糊涂，同时会妨碍代码在该作用域内的可移植性。
void myMethod() {
int int1 = 0; // beginning of method block
if (condition) {
int int2 = 0; // beginning of "if" block
...
}
}
该规则的一个例外是for循环的索引变量
for (int i = 0; i maxLoops; i++) { ... }
避免声明的局部变量覆盖上一级声明的变量。例如，不要在内部代码块中声明相同的变量名：
int count;
...
myMethod() {
if (condition) {
int count = 0; // AVOID!
...
}
...
}
6.4 类和接口的声明(Class and Interface Declarations)
当编写类和接口是，应该遵守以下格式规则：
- 在方法名与其参数列表之前的左括号"("间不要有空格
- 左大括号"{"位于声明语句同行的末尾
- 右大括号"}"另起一行，与相应的声明语句对齐，除非是一个空语句，"}"应紧跟在"{"之后
class Sample extends Object {
int ivar1;
int ivar2;
Sample(int i, int j) {
ivar1 = i;
ivar2 = j;
}
int emptyMethod() {}
...
}
- 方法与方法之间以空行分隔
7 语句(Statements)
7.1 简单语句(Simple Statements)
每行至多包含一条语句，例如：
argv++; // Correct
argc--; // Correct
argv++; argc--; // AVOID!
7.2 复合语句(Compound Statements)
复合语句是包含在大括号中的语句序列，形如"{ 语句 }"。例如下面各段。
- 被括其中的语句应该较之复合语句缩进一个层次
- 左大括号"{"应位于复合语句起始行的行尾；右大括号"}"应另起一行并与复合语句首行对齐。
- 大括号可以被用于所有语句，包括单个语句，只要这些语句是诸如if-else或for控制结构的一部分。这样便于添加语句而无需担心由于忘了加括号而引入bug。
7.3 返回语句(return Statements)
一个带返回值的return语句不使用小括号"()"，除非它们以某种方式使返回值更为显见。例如：
return;
return myDisk.size();
return (size ? size : defaultSize);
7.4 if，if-else，if else-if else语句(if, if-else, if else-if else Statements)
if-else语句应该具有如下格式：
if (condition) {
statements;
}
if (condition) {
statements;
} else {
statements;
}
if (condition) {
statements;
} else if (condition) {
statements;
} else{
statements;
}
注意：if语句总是用"{"和"}"括起来，避免使用如下容易引起错误的格式：
if (condition) //AVOID! THIS OMITS THE BRACES {}!
statement;
7.5 for语句(for Statements)
一个for语句应该具有如下格式：
for (initialization; condition; update) {
statements;
}
一个空的for语句(所有工作都在初始化，条件判断，更新子句中完成）应该具有如下格式：
for (initialization; condition; update);
当在for语句的初始化或更新子句中使用逗号时，避免因使用三个以上变量，而导致复杂度提高。若需要，可以在for循环之前(为初始化子句)或for循环末尾(为更新子句)使用单独的语句。
7.6 while语句(while Statements)
一个while语句应该具有如下格式
while (condition) {
statements;
}
一个空的while语句应该具有如下格式：
while (condition);
7.7 do-while语句(do-while Statements)
一个do-while语句应该具有如下格式：
do {
statements;
} while (condition);
7.8 switch语句(switch Statements)
一个switch语句应该具有如下格式：
switch (condition) {
case ABC:
statements;
/* falls through */
case DEF:
statements;
break;
case XYZ:
statements;
break;
default:
statements;
break;
}
每当一个case顺着往下执行时(因为没有break语句)，通常应在break语句的位置添加注释。上面的示例代码中就包含注释/* falls through */。
7.9 try-catch语句(try-catch Statements)
一个try-catch语句应该具有如下格式：
try {
statements;
} catch (ExceptionClass e) {
statements;
}
一个try-catch语句后面也可能跟着一个finally语句，不论try代码块是否顺利执行完，它都会被执行。
try {
statements;
} catch (ExceptionClass e) {
statements;
} finally {
statements;
}
8 空白(White Space)
8.1 空行(Blank Lines)
空行将逻辑相关的代码段分隔开，以提高可读性。
下列情况应该总是使用两个空行：
- 一个源文件的两个片段(section)之间
- 类声明和接口声明之间
下列情况应该总是使用一个空行：
- 两个方法之间
- 方法内的局部变量和方法的第一条语句之间
- 块注释（参见"5.1.1"）或单行注释（参见"5.1.2"）之前
- 一个方法内的两个逻辑段之间，用以提高可读性
8.2 空格(Blank Spaces)
下列情况应该使用空格：
- 一个紧跟着括号的关键字应该被空格分开，例如：
while (true) {
...
}
注意：空格不应该置于方法名与其左括号之间。这将有助于区分关键字和方法调用。
- 空白应该位于参数列表中逗号的后面
- 所有的二元运算符，除了"."，应该使用空格将之与操作数分开。一元操作符和操作数之间不因该加空格，比如：负号("-")、自增("++")和自减("--")。例如：
a += c + d;
a = (a + b) / (c * d);
while (d++ = s++) {
n++;
}
printSize("size is " + foo + "\n");
- for语句中的表达式应该被空格分开，例如：
for (expr1; expr2; expr3)
- 强制转型后应该跟一个空格，例如：
myMethod((byte) aNum, (Object) x);
myMethod((int) (cp + 5), ((int) (i + 3)) + 1);
9 命名规范(Naming Conventions)
命名规范使程序更易读，从而更易于理解。它们也可以提供一些有关标识符功能的信息，以助于理解代码，例如，不论它是一个常量，包，还是类。
标识符类型 命名规则 例子
包(Packages) 一个唯一包名的前缀总是全部小写的ASCII字母并且是一个顶级域名，通常是com，edu，gov，mil，net，org，或1981年ISO 3166标准所指定的标识国家的英文双字符代码。包名的后续部分根据不同机构各自内部的命名规范而不尽相同。这类命名规范可能以特定目录名的组成来区分部门(department)，项目(project)，机器(machine)，或注册名(login names)。 com.sun.eng
com.apple.quicktime.v2
edu.cmu.cs.bovik.cheese
类(Classes) 命名规则：类名是个一名词，采用大小写混合的方式，每个单词的首字母大写。尽量使你的类名简洁而富于描述。使用完整单词，避免缩写词(除非该缩写词被更广泛使用，像URL，HTML) class Raster;
class ImageSprite;
接口(Interfaces) 命名规则：大小写规则与类名相似 interface RasterDelegate;
interface Storing;
方法(Methods) 方法名是一个动词，采用大小写混合的方式，第一个单词的首字母小写，其后单词的首字母大写。 run();
runFast();
getBackground();
变量(Variables) 除了变量名外，所有实例，包括类，类常量，均采用大小写混合的方式，第一个单词的首字母小写，其后单词的首字母大写。变量名不应以下划线或美元符号开头，尽管这在语法上是允许的。
变量名应简短且富于描述。变量名的选用应该易于记忆，即，能够指出其用途。尽量避免单个字符的变量名，除非是一次性的临时变量。临时变量通常被取名为i，j，k，m和n，它们一般用于整型；c，d，e，它们一般用于字符型。 char c;
int i;
float myWidth;
实例变量(Instance Variables) 大小写规则和变量名相似，除了前面需要一个下划线 int _employeeId;
String _name;
Customer _customer;
常量(Constants) 类常量和ANSI常量的声明，应该全部大写，单词间用下划线隔开。(尽量避免ANSI常量，容易引起错误) static final int MIN_WIDTH = 4;
static final int MAX_WIDTH = 999;
static final int GET_THE_CPU = 1;
10 编程惯例(Programming Practices)
10.1 提供对实例以及类变量的访问控制(Providing Access to Instance and Class Variables)
若没有足够理由，不要把实例或类变量声明为公有。通常，实例变量无需显式的设置(set)和获取(gotten)，通常这作为方法调用的边缘效应 (side effect)而产生。
一个具有公有实例变量的恰当例子，是类仅作为数据结构，没有行为。亦即，若你要使用一个结构(struct)而非一个类(如果java支持结构的话)，那么把类的实例变量声明为公有是合适的。
importjava.awt.*;importjava.awt.event.*;classShopFrameextendsFrameimplementsActionListener{Labellabel1,label2,label3,label4;Buttonbutton1,button2,button3,button4,button5;TextAreatext;Panelpanel1,panel2;staticfloatsum=0.0f;ShopFrame(Strings){super(s);setLayout(newBorderLayout());label1=newLabel("面纸：3元",Label.LEFT);label2=newLabel("钢笔：5元",Label.LEFT);label3=newLabel("书：10元",Label.LEFT);label4=newLabel("袜子：8元",Label.LEFT);button1=newButton("加入购物车");button2=newButton("加入购物车");button3=newButton("加入购物车");button4=newButton("加入购物车");button5=newButton("查看购物车");text=newTextArea("商品有："+"\n",5,10);text.setEditable(false);addWindowListener(newWindowAdapter(){publicvoidwindowClosing(WindowEvente){System.exit(0);}});button1.addActionListener(this);button2.addActionListener(this);button3.addActionListener(this);button4.addActionListener(this);button5.addActionListener(this);panel1=newPanel();panel2=newPanel();panel1.add(label1);panel1.add(button1);panel1.add(label2);panel1.add(button2);panel1.add(label3);panel1.add(button3);panel1.add(label4);panel1.add(button4);panel2.setLayout(newBorderLayout());panel2.add(button5,BorderLayout.NORTH);panel2.add(text,BorderLayout.SOUTH);this.add(panel1,BorderLayout.CENTER);this.add(panel2,BorderLayout.SOUTH);setBounds(100,100,350,250);setVisible(true);validate();}publicvoidactionPerformed(ActionEvente){if(e.getSource()==button1){text.append("一个面纸、");sum=sum+3;}elseif(e.getSource()==button2){text.append("一只钢笔、");sum=sum+5;}elseif(e.getSource()==button3){text.append("一本书、");sum=sum+10;}elseif(e.getSource()==button4){text.append("一双袜子、");sum=sum+8;}elseif(e.getSource()==button5){text.append("\n"+"总价为："+"\n"+sum);}}}publicclassShopping{publicstaticvoidmain(String[]args){newShopFrame("购物车");}}我没用Swing可能显示不出来你的效果。不满意得话我在给你编一个。
最简单的写法：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] str = new String[5];
int i = 0;
while (istr.length) {
str[i] = in.next();
i++;
}
for (int j = str.length-1; j = 0; j--) {
System.out.println(str[j]);
}
}
Java排序算法
1）分类：
1）插入排序（直接插入排序、希尔排序）
2）交换排序（冒泡排序、快速排序）
3）选择排序（直接选择排序、堆排序）
4）归并排序
5）分配排序（箱排序、基数排序）
所需辅助空间最多：归并排序
所需辅助空间最少：堆排序
平均速度最快：快速排序
不稳定：快速排序，希尔排序，堆排序。
1）选择排序算法的时候
1.数据的规模 ； 2.数据的类型 ； 3.数据已有的顺序
一般来说，当数据规模较小时，应选择直接插入排序或冒泡排序。任何排序算法在数据量小时基本体现不出来差距。 考虑数据的类型，比如如果全部是正整数，那么考虑使用桶排序为最优。 考虑数据已有顺序，快排是一种不稳定的排序（当然可以改进），对于大部分排好的数据，快排会浪费大量不必要的步骤。数据量极小，而起已经基本排好序，冒泡是最佳选择。我们说快排好，是指大量随机数据下，快排效果最理想。而不是所有情况。
3）总结：
——按平均的时间性能来分：
1）时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
2）时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特 别是对那些对关键字近似有序的记录序列尤为如此；
3）时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
——按平均的空间性能来分（指的是排序过程中所需的辅助空间大小）：
1） 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2） 快速排序为O(logn )，为栈所需的辅助空间;
3） 归并排序所需辅助空间最多，其空间复杂度为O(n );
4）链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
——排序方法的稳定性能：
1） 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和 经过排序之后，没有改变。
2） 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3） 对于不稳定的排序方法，只要能举出一个实例说明即可。
4） 快速排序，希尔排序和堆排序是不稳定的排序方法。
4）插入排序：
包括直接插入排序，希尔插入排序。
直接插入排序： 将一个记录插入到已经排序好的有序表中。
1, sorted数组的第0个位置没有放数据。
2，从sorted第二个数据开始处理：
如果该数据比它前面的数据要小，说明该数据要往前面移动。
首先将该数据备份放到 sorted的第0位置当哨兵。
然后将该数据前面那个数据后移。
然后往前搜索，找插入位置。
找到插入位置之后讲 第0位置的那个数据插入对应位置。
O(n*n), 当待排记录序列为正序时，时间复杂度提高至O(n)。
希尔排序（缩小增量排序 diminishing increment sort）：先将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
面试穿什么，这里找答案！
插入排序Java代码：
public class InsertionSort {
// 插入排序：直接插入排序 ，希尔排序
public void straightInsertionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=2;jsortedLen;j++){
if(sorted[j]sorted[j-1]){
sorted[0]= sorted[j];//先保存一下后面的那个
sorted[j]=sorted[j-1];// 前面的那个后移。
int insertPos=0;
for(int k=j-2;k=0;k--){
if(sorted[k]sorted[0]){
sorted[k+1]=sorted[k];
}else{
insertPos=k+1;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
public void shellInertionSort(double [] sorted, int inc){
int sortedLen= sorted.length;
for(int j=inc+1;jsortedLen;j++ ){
if(sorted[j]sorted[j-inc]){
sorted[0]= sorted[j];//先保存一下后面的那个
int insertPos=j;
for(int k=j-inc;k=0;k-=inc){
if(sorted[k]sorted[0]){
sorted[k+inc]=sorted[k];
//数据结构课本上这个地方没有给出判读，出错：
if(k-inc=0){
insertPos = k;
}
}else{
insertPos=k+inc;
break;
}
}
sorted[insertPos]=sorted[0];
}
}
}
public void shellInsertionSort(double [] sorted){
int[] incs={7,5,3,1};
int num= incs.length;
int inc=0;
for(int j=0;jnum;j++){
inc= incs[j];
shellInertionSort(sorted,inc);
}
}
public static void main(String[] args) {
Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
InsertionSort sorter=new InsertionSort();
// sorter.straightInsertionSort(sorted);
sorter.shellInsertionSort(sorted);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
5）交换排序：
包括冒泡排序，快速排序。
冒泡排序法：该算法是专门针对已部分排序的数据进行排序的一种排序算法。如果在你的数据清单中只有一两个数据是乱序的话，用这种算法就是最快的排序算法。如果你的数据清单中的数据是随机排列的，那么这种方法就成了最慢的算法了。因此在使用这种算法之前一定要慎重。这种算法的核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。
快速排序：通过一趟排序，将待排序记录分割成独立的两个部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。具体做法是：使用两个指针low,high, 初值分别设置为序列的头，和序列的尾，设置pivotkey为第一个记录，首先从high开始向前搜索第一个小于pivotkey的记录和pivotkey所在位置进行交换，然后从low开始向后搜索第一个大于pivotkey的记录和此时pivotkey所在位置进行交换，重复知道low=high了为止。
交换排序Java代码：
public class ExchangeSort {
public void BubbleExchangeSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=sortedLen;j0;j--){
int end= j;
for(int k=1;kend-1;k++){
double tempB= sorted[k];
sorted[k]= sorted[k]sorted[k+1]?
sorted[k]:sorted[k+1];
if(Math.abs(sorted[k]-tempB)10e-6){
sorted[k+1]=tempB;
}
}
}
}
public void QuickExchangeSortBackTrack(double [] sorted,
int low,int high){
if(lowhigh){
int pivot= findPivot(sorted,low,high);
QuickExchangeSortBackTrack(sorted,low,pivot-1);
QuickExchangeSortBackTrack(sorted,pivot+1,high);
}
}
public int findPivot(double [] sorted, int low, int high){
sorted[0]= sorted[low];
while(lowhigh){
while(lowhigh sorted[high]= sorted[0])--high;
sorted[low]= sorted[high];
while(lowhigh sorted[low]=sorted[0])++low;
sorted[high]= sorted[low];
}
sorted[low]=sorted[0];
return low;
}
public static void main(String[] args) {
Random random= new Random(6);
int arraysize= 21;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
ExchangeSort sorter=new ExchangeSort();
// sorter.BubbleExchangeSort(sorted);
sorter.QuickExchangeSortBackTrack(sorted, 1, arraysize-1);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
6）选择排序：
分为直接选择排序， 堆排序
直接选择排序：第i次选取 i到array.Length-1中间最小的值放在i位置。
堆排序：首先，数组里面用层次遍历的顺序放一棵完全二叉树。从最后一个非终端结点往前面调整，直到到达根结点，这个时候除根节点以外的所有非终端节点都已经满足堆得条件了，于是需要调整根节点使得整个树满足堆得条件，于是从根节点开始，沿着它的儿子们往下面走（最大堆沿着最大的儿子走，最小堆沿着最小的儿子走）。 主程序里面，首先从最后一个非终端节点开始调整到根也调整完，形成一个heap， 然后将heap的根放到后面去（即：每次的树大小会变化，但是 root都是在1的位置，以方便计算儿子们的index，所以如果需要升序排列，则要逐步大顶堆。因为根节点被一个个放在后面去了。 降序排列则要建立小顶堆）
代码中的问题： 有时候第2个和第3个顺序不对（原因还没搞明白到底代码哪里有错）
选择排序Java代码：
public class SelectionSort {
public void straitSelectionSort(double [] sorted){
int sortedLen= sorted.length;
for(int j=1;jsortedLen;j++){
int jMin= getMinIndex(sorted,j);
exchange(sorted,j,jMin);
}
}
public void exchange(double [] sorted,int i,int j){
int sortedLen= sorted.length;
if(isortedLen jsortedLen ij i=0 j=0){
double temp= sorted[i];
sorted[i]=sorted[j];
sorted[j]=temp;
}
}
public int getMinIndex(double [] sorted, int i){
int sortedLen= sorted.length;
int minJ=1;
double min= Double.MAX_VALUE;
for(int j=i;jsortedLen;j++){
if(sorted[j]min){
min= sorted[j];
minJ= j;
}
}
return minJ;
}
public void heapAdjust(double [] sorted,int start,int end){
if(startend){
double temp= sorted;
// 这个地方jend与课本不同，j=end会报错：
for(int j=2*start;jend;j *=2){
if(j+1end sorted[j]-sorted[j+1]10e-6){
++j;
}
if(temp=sorted[j]){
break;
}
sorted=sorted[j];
start=j;
}
sorted=temp;
}
}
public void heapSelectionSort(double [] sorted){
int sortedLen = sorted.length;
for(int i=sortedLen/2;i0;i--){
heapAdjust(sorted,i,sortedLen);
}
for(int i=sortedLen;i1;--i){
exchange(sorted,1,i);
heapAdjust(sorted,1,i-1);
}
}
public static void main(String [] args){
Random random= new Random(6);
int arraysize=9;
double [] sorted=new double[arraysize];
System.out.print("Before Sort:");
for(int j=1;jarraysize;j++){
sorted[j]= (int)(random.nextDouble()* 100);
System.out.print((int)sorted[j]+" ");
}
System.out.println();
SelectionSort sorter=new SelectionSort();
// sorter.straitSelectionSort(sorted);
sorter.heapSelectionSort(sorted);
System.out.print("After Sort:");
for(int j=1;jsorted.length;j++){
System.out.print((int)sorted[j]+" ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
7）归并排序：
将两个或两个以上的有序表组合成一个新的有序表。归并排序要使用一个辅助数组，大小跟原数组相同，递归做法。每次将目标序列分解成两个序列，分别排序两个子序列之后，再将两个排序好的子序列merge到一起。
归并排序Java代码：
public class MergeSort {
private double[] bridge;//辅助数组
public void sort(double[] obj){
if (obj == null){
throw new NullPointerException("
The param can not be null!");
}
bridge = new double[obj.length]; // 初始化中间数组
mergeSort(obj, 0, obj.length - 1); // 归并排序
bridge = null;
}
private void mergeSort(double[] obj, int left, int right){
if (left right){
int center = (left + right) / 2;
mergeSort(obj, left, center);
mergeSort(obj, center + 1, right);
merge(obj, left, center, right);
}
}
private void merge(double[] obj, int left,
int center, int right){
int mid = center + 1;
int third = left;
int tmp = left;
while (left = center mid = right){
// 从两个数组中取出小的放入中间数组
if (obj[left]-obj[mid]=10e-6){
bridge[third++] = obj[left++];
} else{
bridge[third++] = obj[mid++];
}
}
// 剩余部分依次置入中间数组
while (mid = right){
bridge[third++] = obj[mid++];
}
while (left = center){
bridge[third++] = obj[left++];
}
// 将中间数组的内容拷贝回原数组
copy(obj, tmp, right);
}
private void copy(double[] obj, int left, int right)
{
while (left = right){
obj[left] = bridge[left];
left++;
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 10;
double[] sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
MergeSort sorter = new MergeSort();
sorter.sort(sorted);
System.out.print("After Sort:");
for (int j = 0; j sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
面试穿什么，这里找答案！
8）基数排序：
使用10个辅助队列，假设最大数的数字位数为 x， 则一共做 x次，从个位数开始往前，以第i位数字的大小为依据，将数据放进辅助队列，搞定之后回收。下次再以高一位开始的数字位为依据。
以Vector作辅助队列，基数排序的Java代码：
public class RadixSort {
private int keyNum=-1;
private VectorVectorDouble util;
public void distribute(double [] sorted, int nth){
if(nth=keyNum nth0){
util=new VectorVectorDouble();
for(int j=0;j10;j++){
Vector Double temp= new Vector Double();
util.add(temp);
}
for(int j=0;jsorted.length;j++){
int index= getNthDigit(sorted[j],nth);
util.get(index).add(sorted[j]);
}
}
}
public int getNthDigit(double num,int nth){
String nn= Integer.toString((int)num);
int len= nn.length();
if(len=nth){
return Character.getNumericValue(nn.charAt(len-nth));
}else{
return 0;
}
}
public void collect(double [] sorted){
int k=0;
for(int j=0;j10;j++){
int len= util.get(j).size();
if(len0){
for(int i=0;ilen;i++){
sorted[k++]= util.get(j).get(i);
}
}
}
util=null;
}
public int getKeyNum(double [] sorted){
double max= Double.MIN_VALUE;
for(int j=0;jsorted.length;j++){
if(sorted[j]max){
max= sorted[j];
}
}
return Integer.toString((int)max).length();
}
public void radixSort(double [] sorted){
if(keyNum==-1){
keyNum= getKeyNum(sorted);
}
for(int i=1;i=keyNum;i++){
distribute(sorted,i);
collect(sorted);
}
}
public static void main(String[] args) {
Random random = new Random(6);
int arraysize = 21;
double[] sorted = new double[arraysize];
System.out.print("Before Sort:");
for (int j = 0; j arraysize; j++) {
sorted[j] = (int) (random.nextDouble() * 100);
System.out.print((int) sorted[j] + " ");
}
System.out.println();
RadixSort sorter = new RadixSort();
sorter.radixSort(sorted);
System.out.print("After Sort:");
for (int j = 0; j sorted.length; j++) {
System.out.print((int) sorted[j] + " ");
}
System.out.println();
}
}
//copy而来
