java常用算法代码,java常见的算法

如何用70行Java代码实现深度神经网络算法

import java.util.Random;

成都创新互联于2013年开始，是专业互联网技术服务公司，拥有项目网站设计制作、做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元祥云做网站,已为上家服务,为祥云各地企业和个人服务,联系电话:18982081108

public class BpDeep{

public double[][] layer;//神经网络各层节点

public double[][] layerErr;//神经网络各节点误差

public double[][][] layer_weight;//各层节点权重

public double[][][] layer_weight_delta;//各层节点权重动量

public double mobp;//动量系数

public double rate;//学习系数

public BpDeep(int[] layernum, double rate, double mobp){

this.mobp = mobp;

this.rate = rate;

layer = new double[layernum.length][];

layerErr = new double[layernum.length][];

layer_weight = new double[layernum.length][][];

layer_weight_delta = new double[layernum.length][][];

Random random = new Random();

for(int l=0;llayernum.length;l++){

layer[l]=new double[layernum[l]];

layerErr[l]=new double[layernum[l]];

if(l+1layernum.length){

layer_weight[l]=new double[layernum[l]+1][layernum[l+1]];

layer_weight_delta[l]=new double[layernum[l]+1][layernum[l+1]];

for(int j=0;jlayernum[l]+1;j++)

for(int i=0;ilayernum[l+1];i++)

layer_weight[l][j][i]=random.nextDouble();//随机初始化权重

}

}

}

//逐层向前计算输出

public double[] computeOut(double[] in){

for(int l=1;llayer.length;l++){

for(int j=0;jlayer[l].length;j++){

double z=layer_weight[l-1][layer[l-1].length][j];

for(int i=0;ilayer[l-1].length;i++){

layer[l-1][i]=l==1?in[i]:layer[l-1][i];

z+=layer_weight[l-1][i][j]*layer[l-1][i];

}

layer[l][j]=1/(1+Math.exp(-z));

}

}

return layer[layer.length-1];

}

//逐层反向计算误差并修改权重

public void updateWeight(double[] tar){

int l=layer.length-1;

for(int j=0;jlayerErr[l].length;j++)

layerErr[l][j]=layer[l][j]*(1-layer[l][j])*(tar[j]-layer[l][j]);

while(l--0){

for(int j=0;jlayerErr[l].length;j++){

double z = 0.0;

for(int i=0;ilayerErr[l+1].length;i++){

z=z+l0?layerErr[l+1][i]*layer_weight[l][j][i]:0;

layer_weight_delta[l][j][i]= mobp*layer_weight_delta[l][j][i]+rate*layerErr[l+1][i]*layer[l][j];//隐含层动量调整

layer_weight[l][j][i]+=layer_weight_delta[l][j][i];//隐含层权重调整

if(j==layerErr[l].length-1){

layer_weight_delta[l][j+1][i]= mobp*layer_weight_delta[l][j+1][i]+rate*layerErr[l+1][i];//截距动量调整

layer_weight[l][j+1][i]+=layer_weight_delta[l][j+1][i];//截距权重调整

}

}

layerErr[l][j]=z*layer[l][j]*(1-layer[l][j]);//记录误差

}

}

}

public void train(double[] in, double[] tar){

double[] out = computeOut(in);

updateWeight(tar);

}

}

参考资料

java中基数排序算法代码

/**  

* 冒泡法排序br/  

* li比较相邻的元素。如果第一个比第二个大，就交换他们两个。/li  

* li对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。/li  

* li针对所有的元素重复以上的步骤，除了最后一个。/li  

* li持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。/li  

*   

* @param numbers  

*            需要排序的整型数组  

*/  

public static void bubbleSort(int[] numbers) {   

int temp; // 记录临时中间值   

int size = numbers.length; // 数组大小   

for (int i = 0; i  size - 1; i++) {   

for (int j = i + 1; j  size; j++) {   

if (numbers[i]  numbers[j]) { // 交换两数的位置   

temp = numbers[i];   

numbers[i] = numbers[j];   

numbers[j] = temp;   

}   

}   

}   

}

java的md5的加密算法代码

import java.lang.reflect.*;

/*******************************************************************************

* keyBean 类实现了RSA Data Security, Inc.在提交给IETF 的RFC1321中的keyBean message-digest

* 算法。

******************************************************************************/

public class keyBean {

/*

* 下面这些S11-S44实际上是一个4*4的矩阵，在原始的C实现中是用#define 实现的， 这里把它们实现成为static

* final是表示了只读，切能在同一个进程空间内的多个 Instance间共享

*/

static final int S11 = 7;

static final int S12 = 12;

static final int S13 = 17;

static final int S14 = 22;

static final int S21 = 5;

static final int S22 = 9;

static final int S23 = 14;

static final int S24 = 20;

static final int S31 = 4;

static final int S32 = 11;

static final int S33 = 16;

static final int S34 = 23;

static final int S41 = 6;

static final int S42 = 10;

static final int S43 = 15;

static final int S44 = 21;

static final byte[] PADDING = { -128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0, 0 };

/*

* 下面的三个成员是keyBean计算过程中用到的3个核心数据，在原始的C实现中 被定义到keyBean_CTX结构中

*/

private long[] state = new long[4]; // state (ABCD)

private long[] count = new long[2]; // number of bits, modulo 2^64 (lsb

// first)

private byte[] buffer = new byte[64]; // input buffer

/*

* digestHexStr是keyBean的唯一一个公共成员，是最新一次计算结果的 16进制ASCII表示.

*/

public String digestHexStr;

/*

* digest,是最新一次计算结果的2进制内部表示，表示128bit的keyBean值.

*/

private byte[] digest = new byte[16];

/*

* getkeyBeanofStr是类keyBean最主要的公共方法，入口参数是你想要进行keyBean变换的字符串

* 返回的是变换完的结果，这个结果是从公共成员digestHexStr取得的．

*/

public String getkeyBeanofStr(String inbuf) {

keyBeanInit();

keyBeanUpdate(inbuf.getBytes(), inbuf.length());

keyBeanFinal();

digestHexStr = "";

for (int i = 0; i 16; i++) {

digestHexStr += byteHEX(digest[i]);

}

return digestHexStr;

}

// 这是keyBean这个类的标准构造函数，JavaBean要求有一个public的并且没有参数的构造函数

public keyBean() {

keyBeanInit();

return;

}

/* keyBeanInit是一个初始化函数，初始化核心变量，装入标准的幻数 */

private void keyBeanInit() {

count[0] = 0L;

count[1] = 0L;

// /* Load magic initialization constants.

state[0] = 0x67452301L;

state[1] = 0xefcdab89L;

state[2] = 0x98badcfeL;

state[3] = 0x10325476L;

return;

}

/*

* F, G, H ,I 是4个基本的keyBean函数，在原始的keyBean的C实现中，由于它们是

* 简单的位运算，可能出于效率的考虑把它们实现成了宏，在java中，我们把它们 实现成了private方法，名字保持了原来C中的。

*/

private long F(long x, long y, long z) {

return (x y) | ((~x) z);

}

private long G(long x, long y, long z) {

return (x z) | (y (~z));

}

private long H(long x, long y, long z) {

return x ^ y ^ z;

}

private long I(long x, long y, long z) {

return y ^ (x | (~z));

}

/*

* FF,GG,HH和II将调用F,G,H,I进行近一步变换 FF, GG, HH, and II transformations for

* rounds 1, 2, 3, and 4. Rotation is separate from addition to prevent

* recomputation.

*/

private long FF(long a, long b, long c, long d, long x, long s, long ac) {

a += F(b, c, d) + x + ac;

a = ((int) a s) | ((int) a (32 - s));

a += b;

return a;

}

private long GG(long a, long b, long c, long d, long x, long s, long ac) {

a += G(b, c, d) + x + ac;

a = ((int) a s) | ((int) a (32 - s));

a += b;

return a;

}

private long HH(long a, long b, long c, long d, long x, long s, long ac) {

a += H(b, c, d) + x + ac;

a = ((int) a s) | ((int) a (32 - s));

a += b;

return a;

}

private long II(long a, long b, long c, long d, long x, long s, long ac) {

a += I(b, c, d) + x + ac;

a = ((int) a s) | ((int) a (32 - s));

a += b;

return a;

}

/*

* keyBeanUpdate是keyBean的主计算过程，inbuf是要变换的字节串，inputlen是长度，这个

* 函数由getkeyBeanofStr调用，调用之前需要调用keyBeaninit，因此把它设计成private的

*/

private void keyBeanUpdate(byte[] inbuf, int inputLen) {

int i, index, partLen;

byte[] block = new byte[64];

index = (int) (count[0] 3) 0x3F;

// /* Update number of bits */

if ((count[0] += (inputLen 3)) (inputLen 3))

count[1]++;

count[1] += (inputLen 29);

partLen = 64 - index;

// Transform as many times as possible.

if (inputLen = partLen) {

keyBeanMemcpy(buffer, inbuf, index, 0, partLen);

keyBeanTransform(buffer);

for (i = partLen; i + 63 inputLen; i += 64) {

keyBeanMemcpy(block, inbuf, 0, i, 64);

keyBeanTransform(block);

}

index = 0;

} else

i = 0;

// /* Buffer remaining input */

keyBeanMemcpy(buffer, inbuf, index, i, inputLen - i);

}

/*

* keyBeanFinal整理和填写输出结果

*/

private void keyBeanFinal() {

byte[] bits = new byte[8];

int index, padLen;

// /* Save number of bits */

Encode(bits, count, 8);

// /* Pad out to 56 mod 64.

index = (int) (count[0] 3) 0x3f;

padLen = (index 56) ? (56 - index) : (120 - index);

keyBeanUpdate(PADDING, padLen);

// /* Append length (before padding) */

keyBeanUpdate(bits, 8);

// /* Store state in digest */

Encode(digest, state, 16);

}

/*

* keyBeanMemcpy是一个内部使用的byte数组的块拷贝函数，从input的inpos开始把len长度的

* 字节拷贝到output的outpos位置开始

*/

private void keyBeanMemcpy(byte[] output, byte[] input, int outpos,

int inpos, int len) {

int i;

for (i = 0; i len; i++)

output[outpos + i] = input[inpos + i];

}

/*

* keyBeanTransform是keyBean核心变换程序，有keyBeanUpdate调用，block是分块的原始字节

*/

private void keyBeanTransform(byte block[]) {

long a = state[0], b = state[1], c = state[2], d = state[3];

long[] x = new long[16];

Decode(x, block, 64);

/* Round 1 */

a = FF(a, b, c, d, x[0], S11, 0xd76aa478L); /* 1 */

d = FF(d, a, b, c, x[1], S12, 0xe8c7b756L); /* 2 */

c = FF(c, d, a, b, x[2], S13, 0x242070dbL); /* 3 */

b = FF(b, c, d, a, x[3], S14, 0xc1bdceeeL); /* 4 */

a = FF(a, b, c, d, x[4], S11, 0xf57c0fafL); /* 5 */

d = FF(d, a, b, c, x[5], S12, 0x4787c62aL); /* 6 */

c = FF(c, d, a, b, x[6], S13, 0xa8304613L); /* 7 */

b = FF(b, c, d, a, x[7], S14, 0xfd469501L); /* 8 */

a = FF(a, b, c, d, x[8], S11, 0x698098d8L); /* 9 */

d = FF(d, a, b, c, x[9], S12, 0x8b44f7afL); /* 10 */

c = FF(c, d, a, b, x[10], S13, 0xffff5bb1L); /* 11 */

b = FF(b, c, d, a, x[11], S14, 0x895cd7beL); /* 12 */

a = FF(a, b, c, d, x[12], S11, 0x6b901122L); /* 13 */

d = FF(d, a, b, c, x[13], S12, 0xfd987193L); /* 14 */

c = FF(c, d, a, b, x[14], S13, 0xa679438eL); /* 15 */

b = FF(b, c, d, a, x[15], S14, 0x49b40821L); /* 16 */

/* Round 2 */

a = GG(a, b, c, d, x[1], S21, 0xf61e2562L); /* 17 */

d = GG(d, a, b, c, x[6], S22, 0xc040b340L); /* 18 */

c = GG(c, d, a, b, x[11], S23, 0x265e5a51L); /* 19 */

b = GG(b, c, d, a, x[0], S24, 0xe9b6c7aaL); /* 20 */

a = GG(a, b, c, d, x[5], S21, 0xd62f105dL); /* 21 */

d = GG(d, a, b, c, x[10], S22, 0x2441453L); /* 22 */

c = GG(c, d, a, b, x[15], S23, 0xd8a1e681L); /* 23 */

b = GG(b, c, d, a, x[4], S24, 0xe7d3fbc8L); /* 24 */

a = GG(a, b, c, d, x[9], S21, 0x21e1cde6L); /* 25 */

d = GG(d, a, b, c, x[14], S22, 0xc33707d6L); /* 26 */

c = GG(c, d, a, b, x[3], S23, 0xf4d50d87L); /* 27 */

b = GG(b, c, d, a, x[8], S24, 0x455a14edL); /* 28 */

a = GG(a, b, c, d, x[13], S21, 0xa9e3e905L); /* 29 */

d = GG(d, a, b, c, x[2], S22, 0xfcefa3f8L); /* 30 */

c = GG(c, d, a, b, x[7], S23, 0x676f02d9L); /* 31 */

b = GG(b, c, d, a, x[12], S24, 0x8d2a4c8aL); /* 32 */

/* Round 3 */

a = HH(a, b, c, d, x[5], S31, 0xfffa3942L); /* 33 */

d = HH(d, a, b, c, x[8], S32, 0x8771f681L); /* 34 */

c = HH(c, d, a, b, x[11], S33, 0x6d9d6122L); /* 35 */

b = HH(b, c, d, a, x[14], S34, 0xfde5380cL); /* 36 */

a = HH(a, b, c, d, x[1], S31, 0xa4beea44L); /* 37 */

d = HH(d, a, b, c, x[4], S32, 0x4bdecfa9L); /* 38 */

c = HH(c, d, a, b, x[7], S33, 0xf6bb4b60L); /* 39 */

b = HH(b, c, d, a, x[10], S34, 0xbebfbc70L); /* 40 */

a = HH(a, b, c, d, x[13], S31, 0x289b7ec6L); /* 41 */

d = HH(d, a, b, c, x[0], S32, 0xeaa127faL); /* 42 */

c = HH(c, d, a, b, x[3], S33, 0xd4ef3085L); /* 43 */

b = HH(b, c, d, a, x[6], S34, 0x4881d05L); /* 44 */

a = HH(a, b, c, d, x[9], S31, 0xd9d4d039L); /* 45 */

d = HH(d, a, b, c, x[12], S32, 0xe6db99e5L); /* 46 */

c = HH(c, d, a, b, x[15], S33, 0x1fa27cf8L); /* 47 */

b = HH(b, c, d, a, x[2], S34, 0xc4ac5665L); /* 48 */

/* Round 4 */

a = II(a, b, c, d, x[0], S41, 0xf4292244L); /* 49 */

d = II(d, a, b, c, x[7], S42, 0x432aff97L); /* 50 */

c = II(c, d, a, b, x[14], S43, 0xab9423a7L); /* 51 */

b = II(b, c, d, a, x[5], S44, 0xfc93a039L); /* 52 */

a = II(a, b, c, d, x[12], S41, 0x655b59c3L); /* 53 */

d = II(d, a, b, c, x[3], S42, 0x8f0ccc92L); /* 54 */

c = II(c, d, a, b, x[10], S43, 0xffeff47dL); /* 55 */

b = II(b, c, d, a, x[1], S44, 0x85845dd1L); /* 56 */

a = II(a, b, c, d, x[8], S41, 0x6fa87e4fL); /* 57 */

d = II(d, a, b, c, x[15], S42, 0xfe2ce6e0L); /* 58 */

c = II(c, d, a, b, x[6], S43, 0xa3014314L); /* 59 */

b = II(b, c, d, a, x[13], S44, 0x4e0811a1L); /* 60 */

a = II(a, b, c, d, x[4], S41, 0xf7537e82L); /* 61 */

d = II(d, a, b, c, x[11], S42, 0xbd3af235L); /* 62 */

c = II(c, d, a, b, x[2], S43, 0x2ad7d2bbL); /* 63 */

b = II(b, c, d, a, x[9], S44, 0xeb86d391L); /* 64 */

state[0] += a;

state[1] += b;

state[2] += c;

state[3] += d;

}

/*

* Encode把long数组按顺序拆成byte数组，因为java的long类型是64bit的， 只拆低32bit，以适应原始C实现的用途

*/

private void Encode(byte[] output, long[] input, int len) {

int i, j;

for (i = 0, j = 0; j len; i++, j += 4) {

output[j] = (byte) (input[i] 0xffL);

output[j + 1] = (byte) ((input[i] 8) 0xffL);

output[j + 2] = (byte) ((input[i] 16) 0xffL);

output[j + 3] = (byte) ((input[i] 24) 0xffL);

}

}

/*

* Decode把byte数组按顺序合成成long数组，因为java的long类型是64bit的，

* 只合成低32bit，高32bit清零，以适应原始C实现的用途

*/

private void Decode(long[] output, byte[] input, int len) {

int i, j;

for (i = 0, j = 0; j len; i++, j += 4)

output[i] = b2iu(input[j]) | (b2iu(input[j + 1]) 8)

| (b2iu(input[j + 2]) 16) | (b2iu(input[j + 3]) 24);

return;

}

/*

* b2iu是我写的一个把byte按照不考虑正负号的原则的”升位”程序，因为java没有unsigned运算

*/

public static long b2iu(byte b) {

return b 0 ? b 0x7F + 128 : b;

}

/*

* byteHEX()，用来把一个byte类型的数转换成十六进制的ASCII表示，

* 因为java中的byte的toString无法实现这一点，我们又没有C语言中的 sprintf(outbuf,"%02X",ib)

*/

public static String byteHEX(byte ib) {

char[] Digit = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A',

'B', 'C', 'D', 'E', 'F' };

char[] ob = new char[2];

ob[0] = Digit[(ib 4) 0X0F];

ob[1] = Digit[ib 0X0F];

String s = new String(ob);

return s;

}

public static void main(String args[]) {

keyBean m = new keyBean();

if (Array.getLength(args) == 0) { // 如果没有参数，执行标准的Test Suite

System.out.println("keyBean Test suite:");

System.out.println("keyBean(\"):" + m.getkeyBeanofStr(""));

System.out.println("keyBean(\"a\"):" + m.getkeyBeanofStr("a"));

System.out.println("keyBean(\"abc\"):" + m.getkeyBeanofStr("abc"));

System.out.println("keyBean(\"message digest\"):"

+ m.getkeyBeanofStr("message digest"));

System.out.println("keyBean(\"abcdefghijklmnopqrstuvwxyz\"):"

+ m.getkeyBeanofStr("abcdefghijklmnopqrstuvwxyz"));

System.out

.println("keyBean(\"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789\"):"

+ m

.getkeyBeanofStr("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"));

} else

System.out.println("keyBean(" + args[0] + ")="

+ m.getkeyBeanofStr(args[0]));

}

}

求ECDSA的Java代码

【方案1】

package ECDSA;

import com.sun.org.apache.xerces.internal.impl.dv.util.HexBin;

import java.security.*;

import java.security.interfaces.ECPrivateKey;

import java.security.interfaces.ECPublicKey;

import java.security.spec.PKCS8EncodedKeySpec;

import java.security.spec.X509EncodedKeySpec;

public class Ecdsa {

private static String src = "hello berber" ;

public static void main(String []args){

  jdkECDSA();

}

public static void jdkECDSA(){

  // 1.初始化密钥

  try{

      KeyPairGenerator keyPairGenerator = KeyPairGenerator.getInstance("EC");

      keyPairGenerator.initialize(256);

      KeyPair keyPair = keyPairGenerator.generateKeyPair() ;

      ECPublicKey ecPublicKey = (ECPublicKey)keyPair.getPublic() ;

      ECPrivateKey ecPrivateKey = (ECPrivateKey)keyPair.getPrivate() ;

      // 执行签名

      PKCS8EncodedKeySpec pkcs8EncodedKeySpec = new PKCS8EncodedKeySpec(ecPrivateKey.getEncoded());

      KeyFactory keyFactory = KeyFactory.getInstance("EC") ;

      PrivateKey privateKey = keyFactory.generatePrivate(pkcs8EncodedKeySpec) ;

      Signature signature = Signature.getInstance("SHA1withECDSA");

      signature.initSign(privateKey);

      signature.update(src.getBytes());

      byte []arr = signature.sign();

      System.out.println("jdk ecdsa sign :"+ HexBin.encode(arr));

      // 验证签名

      X509EncodedKeySpec x509EncodedKeySpec = new X509EncodedKeySpec(ecPublicKey.getEncoded());

      keyFactory = KeyFactory.getInstance("EC");

      PublicKey publicKey = keyFactory.generatePublic(x509EncodedKeySpec);

      signature = Signature.getInstance("SHA1withECDSA");

      signature.initVerify(publicKey);

      signature.update(src.getBytes());

      boolean bool = signature.verify(arr);

      System.out.println("jdk ecdsa verify:"+bool);

  }catch(Exception e){

  }

}

}

Java数字签名——ECDSA算法

【方案2】

public class MyTest {

/**

* @param args

*/

public static void main(String[] args) {

new MyTest().getSign();

}

void getSign() {

// Get the instance of the Key Generator with "EC" algorithm

try {

KeyPairGenerator g = KeyPairGenerator.getInstance("EC");

ECGenParameterSpec kpgparams = new ECGenParameterSpec("secp256r1");

g.initialize(kpgparams);

KeyPair pair = g.generateKeyPair();

// Instance of signature class with SHA256withECDSA algorithm

Signature ecdsaSign = Signature.getInstance("SHA256withECDSA");

ecdsaSign.initSign(pair.getPrivate());

System.out.println("Private Keys is::" + pair.getPrivate());

System.out.println("Public Keys is::" + pair.getPublic());

String msg = "text ecdsa with sha256";//getSHA256(msg)

ecdsaSign.update((msg + pair.getPrivate().toString())

.getBytes("UTF-8"));

byte[] signature = ecdsaSign.sign();

System.out.println("Signature is::"

+ new BigInteger(1, signature).toString(16));

// Validation

ecdsaSign.initVerify(pair.getPublic());

ecdsaSign.update(signature);

if (ecdsaSign.verify(signature))

System.out.println("valid");

else

System.out.println("invalid!!!!");

} catch (Exception e) {

// TODO: handle exception

e.printStackTrace();

}

}}

java – 使用secp256r1曲线和SHA256算法生

怎么验证生成的Ecdsa签名是正确的呢，可以看下这篇文章:RSA,ECC,Ecdsa,国密SM2的签名，验签，加密

请给出java几种排序方法

java常见的排序分为：

1 插入类排序

主要就是对于一个已经有序的序列中，插入一个新的记录。它包括：直接插入排序，折半插入排序和希尔排序

2 交换类排序

这类排序的核心就是每次比较都要“交换”，在每一趟排序都会两两发生一系列的“交换”排序，但是每一趟排序都会让一个记录排序到它的最终位置上。它包括：起泡排序，快速排序

3 选择类排序

每一趟排序都从一系列数据中选择一个最大或最小的记录，将它放置到第一个或最后一个为位置交换，只有在选择后才交换，比起交换类排序，减少了交换记录的时间。属于它的排序：简单选择排序，堆排序

4 归并类排序

将两个或两个以上的有序序列合并成一个新的序列

5 基数排序

主要基于多个关键字排序的。

下面针对上面所述的算法，讲解一些常用的java代码写的算法

二 插入类排序之直接插入排序

直接插入排序,一般对于已经有序的队列排序效果好。

基本思想：每趟将一个待排序的关键字按照大小插入到已经排序好的位置上。

算法思路，从后往前先找到要插入的位置，如果小于则就交换，将元素向后移动，将要插入数据插入该位置即可。时间复杂度为O(n2),空间复杂度为O(1)

package sort.algorithm;

public class DirectInsertSort {

public static void main(String[] args) {

// TODO Auto-generated method stub

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };

int temp, j;

for (int i = 1; i data.length; i++) {

temp = data[i];

j = i - 1;

// 每次比较都是对于已经有序的

while (j = 0 data[j] temp) {

data[j + 1] = data[j];

j--;

}

data[j + 1] = temp;

}

// 输出排序好的数据

for (int k = 0; k data.length; k++) {

System.out.print(data[k] + " ");

}

}

}

三 插入类排序之折半插入排序(二分法排序)

条件：在一个已经有序的队列中，插入一个新的元素

折半插入排序记录的比较次数与初始序列无关

思想：折半插入就是首先将队列中取最小位置low和最大位置high，然后算出中间位置mid

将中间位置mid与待插入的数据data进行比较，

如果mid大于data，则就表示插入的数据在mid的左边，high=mid-1;

如果mid小于data，则就表示插入的数据在mid的右边,low=mid+1

最后整体进行右移操作。

时间复杂度O(n2),空间复杂度O(1)

package sort.algorithm;

//折半插入排序

public class HalfInsertSort {

public static void main(String[] args) {

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 };

// 存放临时要插入的元素数据

int temp;

int low, mid, high;

for (int i = 1; i data.length; i++) {

temp = data[i];

// 在待插入排序的序号之前进行折半插入

low = 0;

high = i - 1;

while (low = high) {

mid = (low + high) / 2;

if (temp data[mid])

high = mid - 1;

else

// low=high的时候也就是找到了要插入的位置，

// 此时进入循环中，将low加1，则就是要插入的位置了

low = mid + 1;

}

// 找到了要插入的位置，从该位置一直到插入数据的位置之间数据向后移动

for (int j = i; j = low + 1; j--)

data[j] = data[j - 1];

// low已经代表了要插入的位置了

data[low] = temp;

}

for (int k = 0; k data.length; k++) {

System.out.print(data[k] + " ");

}

}

}

四 插入类排序之希尔排序

希尔排序，也叫缩小增量排序，目的就是尽可能的减少交换次数，每一个组内最后都是有序的。

将待续按照某一种规则分为几个子序列，不断缩小规则，最后用一个直接插入排序合成

空间复杂度为O(1)，时间复杂度为O(nlog2n)

算法先将要排序的一组数按某个增量d（n/2,n为要排序数的个数）分成若干组，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。

package sort.algorithm;

public class ShellSort {

public static void main(String[] args) {

int a[] = { 1, 54, 6, 3, 78, 34, 12, 45, 56, 100 };

double d1 = a.length;

int temp = 0;

while (true)

{

//利用这个在将组内倍数减小

//这里依次为5,3,2,1

d1 = Math.ceil(d1 / 2);

//d为增量每个分组之间索引的增量

int d = (int) d1;

//每个分组内部排序

for (int x = 0; x d; x++)

{

//组内利用直接插入排序

for (int i = x + d; i a.length; i += d) {

int j = i - d;

temp = a[i];

for (; j = 0 temp a[j]; j -= d) {

a[j + d] = a[j];

}

a[j + d] = temp;

}

}

if (d == 1)

break;

}

for (int i = 0; i a.length; i++)

System.out.print(a[i]+" ");

}

}

五 交换类排序之冒泡排序

交换类排序核心就是每次比较都要进行交换

冒泡排序：是一种交换排序

每一趟比较相邻的元素，较若大小不同则就会发生交换，每一趟排序都能将一个元素放到它最终的位置！每一趟就进行比较。

时间复杂度O(n2)，空间复杂度O(1)

package sort.algorithm;

//冒泡排序：是一种交换排序

public class BubbleSort {

// 按照递增顺序排序

public static void main(String[] args) {

// TODO Auto-generated method stub

int data[] = { 2, 6, 10, 3, 9, 80, 1, 16, 27, 20, 13, 100, 37, 16 };

int temp = 0;

// 排序的比较趟数,每一趟都会将剩余最大数放在最后面

for (int i = 0; i data.length - 1; i++) {

// 每一趟从开始进行比较，将该元素与其余的元素进行比较

for (int j = 0; j data.length - 1; j++) {

if (data[j] data[j + 1]) {

temp = data[j];

data[j] = data[j + 1];

data[j + 1] = temp;

}

}

}

for (int i = 0; i data.length; i++)

System.out.print(data[i] + " ");

}

}