java分組演算法
名稱 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 介紹(Introction)
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維護，有關評論意見請發至[email protected]
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)：
http://java.sun.com/javadoc/writingdoccomments/index.html
若想了解更多有關文檔注釋和javadoc的詳細資料，參見javadoc的主頁：
http://java.sun.com/javadoc/index.html
文檔注釋描述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，e，gov，mil，net，org，或1981年ISO 3166標准所指定的標識國家的英文雙字元代碼。包名的後續部分根據不同機構各自內部的命名規范而不盡相同。這類命名規范可能以特定目錄名的組成來區分部門(department)，項目(project)，機器(machine)，或注冊名(login names)。 com.sun.eng
com.apple.quicktime.v2
e.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支持結構的話)，那麼把類的實例變數聲明為公有是合適的。
2. java怎麼實現排序
Java實現幾種常見排序方法
日常操作中常見的排序方法有：冒泡排序、快速排序、選擇排序、插入排序、希爾排序，甚至還有基數排序、雞尾酒排序、桶排序、鴿巢排序、歸並排序等。
以下常見演算法的定義
1. 插入排序：插入排序基本操作就是將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序，時間復雜度為O(n^2)。是穩定的排序方法。插入排序的基本思想是：每步將一個待排序的紀錄，按其關鍵碼值的大小插入前面已經排序的文件中適當位置上，直到全部插入完為止。
2. 選擇排序：選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法。
3. 冒泡排序：冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序演算法。它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演算法的名字由來是因為越大的元素會經由交換慢慢「浮」到數列的頂端。
4. 快速排序：快速排序（Quicksort）是對冒泡排序的一種改進。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
5. 歸並排序：歸並排序是建立在歸並操作上的一種有效的排序演算法,該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合並，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合並成一個有序表，稱為二路歸並。
6. 希爾排序：希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。希爾排序是非穩定排序演算法。希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。
https://www.cnblogs.com/wangmingshun/p/5635292.html
3. 求資料庫應用題
資料庫語言的目標
要說清這個目標，先要理解資料庫是做什麼的。
資料庫這個軟體，名字中有個「庫」字，會讓人覺得它主要是為了存儲的。其實不然，資料庫實現的重要功能有兩條：計算、事務！也就是我們常說的 OLAP 和 OLTP，資料庫的存儲都是為這兩件事服務的，單純的存儲並不是資料庫的目標。
我們知道，SQL 是目前資料庫的主流語言。那麼，用 SQL 做這兩件事是不是很方便呢？
事務類功能主要解決數據在寫入和讀出時要保持的一致性，實現這件事的難度並不小，但對於應用程序的介面卻非常簡單，用於操縱資料庫讀寫的代碼也很簡單。如果假定目前關系資料庫的邏輯存儲模式是合理的（也就是用數據表和記錄來存儲數據，其合理性與否是另一個復雜問題，不在這里展開了），那麼 SQL 在描述事務類功能時沒什麼大問題，因為並不需要描述多復雜的動作，復雜性都在資料庫內部解決了。
但計算類功能卻不一樣了。
這里說的計算是個更廣泛的概念，並不只是簡單的加加減減，查找、關聯都可以看成是某種計算。
什麼樣的計算體系才算好呢？
還是兩條：寫著簡單、跑得快。
寫著簡單，很好理解，就是讓程序員很快能寫出來代碼來，這樣單位時間內可以完成更多的工作；跑得快就更容易理解，我們當然希望更短時間內獲得計算結果。
其實 SQL 中的 Q 就是查詢的意思，發明它的初衷主要是為了做查詢（也就是計算），這才是 SQL 的主要目標。然而，SQL 在描述計算任務時，卻很難說是很勝任的。
SQL為什麼不行
先看寫著簡單的問題。
SQL 寫出來很象英語，有些查詢可以當英語來讀和寫（網上多得很，就不舉例了），這應當算是滿足寫著簡單這一條了吧。
且慢！我們在教科書上看到的 SQL 經常只有兩三行，這些 SQL 確實算是寫著簡單的，但如果我們嘗試一些稍復雜化的問題呢？
這是一個其實還不算很復雜的例子：計算一支股票最長連續上漲了多少天？用 SQL 寫出來是這樣的：
- selectmax(consecutive_day)from(selectcount(*) (consecutive_dayfrom(selectsum(rise_mark) over(orderbytrade_date) days_no_gainfrom(selecttrade_date,case when closing_price>lag(closing_price) over(order by trade_date)then 0 else 1 END rise_markfrom stock_price ) )group by days\_no\_gain)
- SELECTTOP 10x FROMT ORDERBYx DESC
- stock_price.sort(trade_date).group@o(closing_price
- T.groups(;top(-10,x))
這個語句的工作原理就不解釋了，反正有點繞，同學們可以自己嘗試一下。
這是潤乾公司的招聘考題，通過率不足 20%；因為太難，後來被改成另一種方式：把 SQL 語句寫出來讓應聘者解釋它在算什麼，通過率依然不高。
這說明什麼？說明情況稍有復雜，SQL 就變得即難懂又難寫！
再看跑得快的問題，還是一個經常拿出來的簡單例子：1 億條數據中取前 10 名。這個任務用 SQL 寫出來並不復雜：
但是，這個語句對應的執行邏輯是先對所有數據進行大排序，然後再取出前 10 個，後面的不要了。大家知道，排序是一個很慢的動作，會多次遍歷數據，如果數據量大到內存裝不下，那還需要外存做緩存，性能還會進一步急劇下降。如果嚴格按這句 SQL 體現的邏輯去執行，這個運算無論如何是跑不快的。然而，很多程序員都知道這個運算並不需要大排序，也用不著外存緩存，一次遍歷用一點點內存就可以完成，也就是存在更高性能的演算法。可惜的是，用 SQL 卻寫不出這樣的演算法，只能寄希望於資料庫的優化器足夠聰明，能把這句 SQL 轉換成高性能演算法執行，但情況復雜時資料庫的優化器也未必靠譜。
看樣子，SQL 在這兩方面做得都不夠好。這兩個並不復雜的問題都是這樣，現實中數千行的 SQL 代碼中，這種難寫且跑不快的情況比比皆是。
為什麼 SQL 不行呢？
要回答這個問題，我們要分析一下用程序代碼實現計算到底是在干什麼。
本質上講，編寫程序的過程，就是把解決問題的思路翻譯成計算機可執行的精確化形式語言的過程。舉例來說，就象小學生解應用題，分析問題想出解法之後，還要列出四則運算表達式。用程序計算也是一樣，不僅要想出解決問題的方法，還要把解法翻譯成計算機能理解執行的動作才算完成。
用於描述計算方法的形式語言，其核心在於所採用的代數體系。所謂代數體系，簡單說就是一些數據類型和其上的運算規則，比如小學學到的算術，就是整數和加減乘除運算。有了這套東西，我們就能把想做的運算用這個代數體系約定的符號寫出來，也就是代碼，然後計算機就可以執行了。
如果這個代數體系設計時考慮不周到，提供的數據類型和運算不方便，那就會導致描述演算法非常困難。這時候會發生一個怪現象：翻譯解法到代碼的難度遠遠超過解決問題本身。
舉個例子，我們從小學慣用阿拉伯數字做日常計算，做加減乘除都很方便，所有人都天經地義認為數值運算就該是這樣的。其實未必！估計很多人都知道還有一種叫做羅馬數字的東西，你知道用羅馬數字該怎麼做加減乘除嗎？古羅馬人又是如何上街買菜的？
代碼難寫很大程度是代數的問題。
再看跑不快的原因。
軟體沒辦法改變硬體的性能，CPU 和硬碟該多快就是多快。不過，我們可以設計出低復雜度的演算法，也就是計算量更小的演算法，這樣計算機執行的動作變少，自然也就會快了。但是，光想出演算法還不夠，還要把這個演算法用某種形式語言寫得出來才行，否則計算機不會執行。而且，寫起來還要比較簡單，都要寫很長很麻煩，也沒有人會去用。所以呢，對於程序來講，跑得快和寫著簡單其實是同一個問題，背後還是這個形式語言採用的代數的問題。如果這個代數不好，就會導致高性能演算法很難實現甚至實現不了，也就沒辦法跑得快了。就象上面說的，用 SQL 寫不出我們期望的小內存單次遍歷演算法，能不能跑得快就只能寄希望於優化器。
我們再做個類比：
上過小學的同學大概都知道高斯計算 1+2+3+…+100 的小故事。普通人就是一步步地硬加 100 次，高斯小朋友很聰明，發現 1+100=101、2+99=101、…、50+51=101，結果是 50 乘 101，很快算完回家午飯了。
聽過這個故事，我們都會感慨高斯很聰明，能想到這么巧妙的辦法，即簡單又迅速。這沒有錯，但是，大家容易忽略一點：在高斯的時代，人類的算術體系（也是一個代數）中已經有了乘法！象前面所說，我們從小學習四則運算，會覺得乘法是理所當然的，然而並不是！乘法是後於加法被發明出來的。如果高斯的年代還沒有乘法，即使有聰明的高斯，也沒辦法快速解決這個問題。
目前主流資料庫是關系資料庫，之所以這么叫，是因為它的數學基礎被稱為關系代數，SQL 也就是關系代數理論上發展出來的形式語言。
現在我們能回答，為什麼 SQL 在期望的兩個方面做得不夠好？問題出在關系代數上，關系代數就像一個只有加法還沒發明乘法的算術體系，很多事做不好是必然的。
關系代數已經發明五十年了，五十年前的應用需求以及硬體環境，和今天比的差異是很巨大了，繼續延用五十年前的理論來解決今天的問題，聽著就感覺太陳舊了？然而現實就是這樣，由於存量用戶太多，而且也還沒有成熟的新技術出現，基於關系代數的 SQL，今天仍然是最重要的資料庫語言。雖然這幾十年來也有一些改進完善，但根子並沒有變，面對當代的復雜需求和硬體環境，SQL 不勝任也是情理之中的事。
而且，不幸的是，這個問題是理論上的，在工程上無論如何優化也無濟於事，只能有限改善，不能根除。不過，絕大部分的資料庫開發者並不會想到這一層，或者說為了照顧存量用戶的兼容性，也沒打算想到這一層。於是，主流資料庫界一直在這個圈圈裡打轉轉。
SPL為什麼能行
那麼該怎樣讓計算寫著更簡單、跑得更快呢？
發明新的代數！有「乘法」的代數。在其基礎上再設計新的語言。
這就是 SPL 的由來。它的理論基礎不再是關系代數，稱為離散數據集。基於這個新代數設計的形式語言，起名為SPL（Structured Process Language)。
SPL 針對 SQL 的不足（更確切地說法是，離散數據集針對關系代數的各種缺陷）進行了革新。SPL 重新定義了並擴展許多結構化數據中的運算，增加了離散性、強化了有序計算、實現了徹底的集合化、支持對象引用、提倡分步運算。
限於篇幅，這里不能介紹 SPL（離散數據集）的全貌。我們在這里列舉 SPL（離散數據集）針對 SQL（關系代數）的部分差異化改進：
游離記錄
離散數據集中的記錄是一種基本數據類型，它可以不依賴於數據表而獨立存在。數據表是記錄構成的集合，而構成某個數據表的記錄還可以用於構成其它數據表。比如過濾運算就是用原數據表中滿足條件的記錄構成新數據表，這樣，無論空間佔用還是運算性能都更有優勢。
關系代數沒有可運算的數據類型來表示記錄，單記錄實際上是只有一行的數據表，不同數據表中的記錄也不能共享。比如，過濾運算時會復制出新記錄來構成新數據表，空間和時間成本都變大。
特別地，因為有游離記錄，離散數據集允許記錄的欄位取值是某個記錄，這樣可以更方便地實現外鍵連接。
有序性
關系代數是基於無序集合設計的，集合成員沒有序號的概念，也沒有提供定位計算以及相鄰引用的機制。SQL 實踐時在工程上做了一些局部完善，使得現代 SQL 能方便地進行一部分有序運算。
離散數據集中的集合是有序的，集合成員都有序號的概念，可以用序號訪問成員，並定義了定位運算以返回成員在集合中的序號。離散數據集提供了符號以在集合運算中實現相鄰引用，並支持針對集合中某個序號位置進行計算。
有序運算很常見，卻一直是 SQL 的困難問題，即使在有了窗口函數後仍然很繁瑣。SPL 則大大改善了這個局面，前面那個股票上漲的例子就能說明問題。
離散性與集合化
關系代數中定義了豐富的集合運算，即能將集合作為整體參加運算，比如聚合、分組等。這是 SQL 比 Java 等高級語言更為方便的地方。
但關系代數的離散性非常差，沒有游離記錄。而 Java 等高級語言在這方面則沒有問題。
離散數據集則相當於將離散性和集合化結合起來了，既有集合數據類型及相關的運算，也有集合成員游離在集合之外單獨運算或再組成其它集合。可以說 SPL 集中了 SQL 和 Java 兩者的優勢。
有序運算是典型的離散性與集合化的結合場景。次序的概念只有在集合中才有意義，單個成員無所謂次序，這里體現了集合化；而有序計算又需要針對某個成員及其相鄰成員進行計算，需要離散性。
在離散性的支持下才能獲得更徹底的集合化，才能解決諸如有序計算類型的問題。
離散數據集是即有離散性又有集合化的代數體系，關系代數只有集合化。
分組理解
分組運算的本意是將一個大集合按某種規則拆成若干個子集合，關系代數中沒有數據類型能夠表示集合的集合，於是強迫在分組後做聚合運算。
離散數據集中允許集合的集合，可以表示合理的分組運算結果，分組和分組後的聚合被拆分成相互獨立的兩步運算，這樣可以針對分組子集再進行更復雜的運算。
關系代數中只有一種等值分組，即按分組鍵值劃分集合，等值分組是個完全劃分。
離散數據集認為任何拆分大集合的方法都是分組運算，除了常規的等值分組外，還提供了與有序性結合的有序分組，以及可能得到不完全劃分結果的對位分組。
聚合理解
關系代數中沒有顯式的集合數據類型，聚合計算的結果都是單值，分組後的聚合運算也是這樣，只有 SUM、COUNT、MAX、MIN 等幾種。特別地，關系代數無法把 TOPN 運算看成是聚合，針對全集的 TOPN 只能在輸出結果集時排序後取前 N 條，而針對分組子集則很難做到 TOPN，需要轉變思路拼出序號才能完成。
離散數據集提倡普遍集合，聚合運算的結果不一定是單值，仍然可能是個集合。在離散數據集中，TOPN 運算和 SUM、COUNT 這些是地位等同的，即可以針對全集也可以針對分組子集。
SPL 把 TOPN 理解成聚合運算後，在工程實現時還可以避免全量數據的排序，從而獲得高性能。而 SQL 的 TOPN 總是伴隨 ORDER BY 動作，理論上需要大排序才能實現，需要寄希望於資料庫在工程實現時做優化。
有序支持的高性能
離散數據集特別強調有序集合，利用有序的特徵可以實施很多高性能演算法。這是基於無序集合的關系代數無能為力的，只能寄希望於工程上的優化。
下面是部分利用有序特徵後可以實施的低復雜度運算：
1) 數據表對主鍵有序，相當於天然有一個索引。對鍵欄位的過濾經常可以快速定位，以減少外存遍歷量。隨機按鍵值取數時也可以用二分法定位，在同時針對多個鍵值取數時還能重復利用索引信息。
2) 通常的分組運算是用 HASH 演算法實現的，如果我們確定地知道數據對分組鍵值有序，則可以只做相鄰對比，避免計算 HASH 值，也不會有 HASH 沖突的問題，而且非常容易並行。
3) 數據表對鍵有序，兩個大表之間對位連接可以執行更高性能的歸並演算法，只要對數據遍歷一次，不必緩存，對內存佔用很小；而傳統的 HASH 值分堆方法不僅比較復雜度高，需要較大內存並做外部緩存，還可能因 HASH 函數不當而造成二次 HASH 再緩存。
4) 大表作為外鍵表的連接。事實表小時，可以利用外鍵表有序，快速從中取出關聯鍵值對應的數據實現連接，不需要做 HASH 分堆動作。事實表也很大時，可以將外鍵表用分位點分成多個邏輯段，再將事實表按邏輯段進行分堆，這樣只需要對一個表做分堆，而且分堆過程中不會出現 HASH 分堆時的可能出現的二次分堆，計算復雜度能大幅下降。
其中 3 和 4 利用了離散數據集對連接運算的改造，如果仍然延用關系代數的定義（可能產生多對多），則很難實現這種低復雜的演算法。
除了理論上的差異， SPL 還有許多工程層面的優勢，比如更易於編寫並行代碼、大內存預關聯提高外鍵連接性能等、特有的列存機制以支持隨意分段並行等。
再把前面的問題用 SPL 重寫一遍有個直接感受。
一支股票最長連續上漲多少天：
計算思路和前面的 SQL 相同，但因為引入了有序性後，表達起來容易多了，不再繞了。
1 億條數據中取前 10 名：
SPL 有更豐富的集合數據類型，容易描述單次遍歷上實施簡單聚合的高效演算法，不涉及大排序動作。
這里還有更多 SPL 代碼以體現其思路及大數據演算法：
重磅！開源SPL交流群成立了
簡單好用的SPL開源啦！
為了給感興趣的小夥伴們提供一個相互交流的平台，
特地開通了交流群（群完全免費，不廣告不賣課）
需要進群的朋友，可長按掃描下方二維碼
4. 國密演算法
國密即國家密碼局認定的國產密碼演算法。主要有SM1，SM2，SM3，SM4。密鑰長度和分組長度均為128位。
SM1 為對稱加密。其加密強度與AES相當。該演算法不公開，調用該演算法時，需要通過加密晶元的介面進行調用。
SM2為非對稱加密，基於ECC。該演算法已公開。由於該演算法基於ECC，故其簽名速度與秘鑰生成速度都快於RSA。ECC 256位（SM2採用的就是ECC 256位的一種）安全強度比RSA 2048位高，但運算速度快於RSA。
國家密碼管理局公布的公鑰演算法，其加密強度為256位
SM3 消息摘要。可以用MD5作為對比理解。該演算法已公開。校驗結果為256位。
SM4 無線區域網標準的分組數據演算法。對稱加密，密鑰長度和分組長度均為128位。
由於SM1、SM4加解密的分組大小為128bit，故對消息進行加解密時，若消息長度過長，需要進行分組，要消息長度不足，則要進行填充。
分組密碼演算法(DES和SM4)、將明文數據按固定長度進行分組，然後在同一密鑰控制下逐組進行加密，
公鑰密碼演算法(RSA和SM2)、公開加密演算法本身和公開公鑰，保存私鑰
摘要演算法(SM3 md5) 這個都比較熟悉，用於數字簽名，消息認證，數據完整性，但是sm3安全度比md5高
總得來說國密演算法的安全度比較高，2010年12月推出，也是國家安全戰略，現在銀行都要要求國際演算法改造，要把國際演算法都給去掉
C 語言實現
https://github.com/guan/GmSSL/
Go 語言
https://github.com/tjfoc/gmsm
https://github.com/ZZMarquis/gm
Java 語言
https://github.com/PopezLotado/SM2Java
Go語言實現，調用 gmsm