排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。


常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。


本文将依次介绍上述八大排序算法
算法一

插入排序



插入排序示意图

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。


算法步骤：


1）将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。


2）从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
算法二

希尔排序



希尔排序示意图
 
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。


希尔排序是基于插入排序的以下两点性质而提出改进方法的：


• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率

• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位




希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。


算法步骤：


1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；


2）按增量序列个数k，对序列进行k 趟排序；


3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。


算法三

选择排序

选择排序示意图

选择排序(Selection sort)也是一种简单直观的排序算法。


算法步骤：


1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置


2）再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。


3）重复第二步，直到所有元素均排序完毕。

算法四

冒泡排序

冒泡排序示意图

 冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。


算法步骤：


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


2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。


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


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

算法五

归并排序

归并排序示意图

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。


算法步骤：


1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。


2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置。


3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。


4. 重复步骤3直到某一指针达到序列尾。


5. 将另一序列剩下的所有元素直接复制到合并序列尾。

算法六

快速排序

快速排序示意图

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。


快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

算法步骤：


1 从数列中挑出一个元素，称为 “基准”（pivot）。


2 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。


3 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。


递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

算法七

堆排序

堆排序示意图

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。


堆排序的平均时间复杂度为Ο(nlogn) 。


算法步骤：


1）创建一个堆H[0..n-1]。


2）把堆首（最大值）和堆尾互换。


3）把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置。


4） 重复步骤2，直到堆的尺寸为1。

算法八

基数排序



基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。


说基数排序之前，我们简单介绍桶排序：


算法思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。


例如要对大小为[1..1000]范围内的n个整数A[1..n]排序：


首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储   (10..20]的整数，……集合B[i]存储(   (i-1)10,   i10]的整数，i   =   1,2,..100。总共有  100个桶。


然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任  何排序法都可以。


最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这  样就得到所有数字排好序的一个序列了。


假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果


对每个桶中的数字采用快速排序，那么整个算法的复杂度是：


O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   –   nlogm)


从上式看出，当m接近n的时候，桶排序复杂度接近O(n)。


当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。


前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：


1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。


2）其次待排序的元素都要在一定的范围内等等。

总结



各种排序的稳定性，时间复杂度、空间复杂度、稳定性总结如下图：





关于时间复杂度：


(1)平方阶(O(n2))排序各类简单排序：直接插入、直接选择和冒泡排序；


(2)线性对数阶(O(nlog2n))排序：快速排序、堆排序和归并排序；


(3)O(n1+§))排序,§是介于0和1之间的常数：希尔排序；


(4)线性阶(O(n))排序：基数排序，此外还有桶、箱排序。
 
关于稳定性：


稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序


不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序 


第一种方法：

在tomcat中的conf目录中，在server.xml中的host 节点下添加：

1
2
3
4

<host>
	<Context path="/hello" docBase="D:\eclipse3.2.2forwebtools\workspace\hello\WebRoot" debug="0" privileged="true"> 
	</Context> 
</host>

至于Context 节点属性，可详细见相关文档。   

第二种方法：

将web项目文件件拷贝到webapps 目录中。   

第三种方法：

很灵活，在conf目录中，新建 Catalina（注意大小写）＼localhost目录，在该目录中新建一个xml文件，名字可以随意取，只要和当前文件中的文件名不重复就行了，该xml文件的内容为：

1
2

<Context path="/hello" docBase="D:\eclipse3.2.2forwebtools\workspace\hello\WebRoot" debug="0" privileged="true"> 
</Context> 

第3个方法有个优点，可以定义别名。服务器端运行的项目名称为path，外部访问的URL则使用XML的文件名。这个方法很方便的隐藏了项目的名称，对一些项目名称被固定不能更换，但外部访问时又想换个路径，非常有效。 
 
第2、3还有优点，可以定义一些个性配置，如数据源的配置等。

Java 并发问题一直是各个大厂面试的重点之一。我在平时的面试中，也发现很多候选人对一些基本的并发概念表示没听过，或原理不理解，可能知道一些却又讲不清楚，最终导致面试失败。
本文会结合我实际中接触到的一些面试题，重点来聊一聊 Java 并发中的相关知识点。
我会通过面试题一问一答的方式来阐述，因为我觉得这是最容易理解和引发思考的方式，读者不妨在看答案之前先花 30 秒想一想，然后我们才能更好地一起探讨。
另外，鉴于时间和精力极其有限，虽然本文我考察了不少专业技术书籍和博客，但是错误在所难免，欢迎指正，期待共同进步。

Read More

Spring框架—控制反转（IOC）
1 Spring框架概述
1.1 什么是Spring
1.2 Spring的优点
1.3 Spring的体系结构
2 入门案例:（IoC）
2.1导入jar包
2.2目标类
2.3 配置文件
2.4测试
3 入门案例：DI
3.1 目标类
3.2 dao
3.3 service
3.4 配置文件
3.5 测试
4 依赖注入装配Bean 基于xml
4.1属性依赖注入
4.1.1 构造方法
4.1.2 setter方法
4.2 集合依赖注入
5 依赖注入装配Bean 基于注解
Spring框架—面向切面编程（AOP）
1 什么是AOP
2 AOP实现原理
3 AOP术语【掌握】
4 AOP实现方式
4.1手动方式
4.1.1JDK动态代理
4.1.2 CGLIB字节码增强
4.2半自动
4.2.1目标类
4.2.2切面类
4.2.3Spring 配置
4.2.4 测试
4.3全自动
4.3.1 Spring配置
4.3.2 测试

Read More

编程的关键在于选择数据结构和算法，数据结构用于描述问题，算法用于描述解决问题的方法和步骤。

描述问题的数据除了各数据元素本身，还要考虑各元素的逻辑关系，主要是一对一的线性关系，一对多的树型关系和多对多的图形关系。另外，内存中对各数据元素的存储只有顺序存储和链式存储两种方式，所以数据结构还要考虑数据的存储结构，并考虑逻辑结构与数据结构如何有效地结合到一起。

用算法描述问题，当问题比较复杂时，通常的思路是分而治之，并辅以适当的数据结构。

1 分治法Divide and Conquer

分治法通常描述为以下三步：

1. Divide the problem into more subproblems（分解问题为众多的子问题）;

2. Conuqe(solve) the subproblems（解决各子问题）;

3. Combine(merge) the solution of subproblems(if need)（合并各子问题的解（如果需要））.

如用分治法来计算2^10?

2^10＝2^5x^5=2^2x^3x^5=3232=1024

Read More

1. 为什么要使用数据库

▪	数据保存在内存
	优点：存取速度快
	缺点：数据不能永久保存
▪	数据保存在文件
	优点：数据永久保存
	缺点：
		1）速度比内存操作慢，频繁的IO操作。
		2）查询数据不方便
▪	数据保存在数据库
	1）数据永久保存
	2）使用SQL语句，查询方便效率高。
	3）管理数据方便
	

2. 什么是SQL？

结构化查询语言(Structured Query Language)简称SQL，是一种数据库查询语言。
作用：用于存取数据、查询、更新和管理关系数据库系统。

3. 什么是MySQL?

MySQL是一个关系型数据库管理系统，由瑞典MySQL AB 公司开发，属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一，在 WEB 应用方面，MySQL是最好的 RDBMS (Relational Database Management System，关系数据库管理系统) 应用软件之一。在Java企业级开发中非常常用，因为 MySQL 是开源免费的，并且方便扩展。

4. 数据库三大范式是什么

第一范式：每个列都不可以再拆分。
第二范式：在第一范式的基础上，非主键列完全依赖于主键，而不能是依赖于主键的一部分。
第三范式：在第二范式的基础上，非主键列只依赖于主键，不依赖于其他非主键。
在设计数据库结构的时候，要尽量遵守三范式，如果不遵守，必须有足够的理由。比如性能。事实上我们经常会为了性能而妥协数据库的设计。

5. mysql有关权限的表都有哪几个

MySQL服务器通过权限表来控制用户对数据库的访问，权限表存放在mysql数据库里，由mysql_install_db脚本初始化。这些权限表分别user，db，table_priv，columns_priv和host。下面分别介绍一下这些表的结构和内容：

•	user权限表：记录允许连接到服务器的用户帐号信息，里面的权限是全局级的。
•	db权限表：记录各个帐号在各个数据库上的操作权限。
•	table_priv权限表：记录数据表级的操作权限。
•	columns_priv权限表：记录数据列级的操作权限。
•	host权限表：配合db权限表对给定主机上数据库级操作权限作更细致的控制。这个权限表不受GRANT和REVOKE语句的影响。

6. MySQL的binlog有有几种录入格式？分别有什么区别？

有三种格式，statement，row和mixed。

•	statement模式下，每一条会修改数据的sql都会记录在binlog中。不需要记录每一行的变化，减少了binlog日志量，节约了IO，提高性能。由于sql的执行是有上下文的，因此在保存的时候需要保存相关的信息，同时还有一些使用了函数之类的语句无法被记录复制。
•	row级别下，不记录sql语句上下文相关信息，仅保存哪条记录被修改。记录单元为每一行的改动，基本是可以全部记下来但是由于很多操作，会导致大量行的改动(比如alter table)，因此这种模式的文件保存的信息太多，日志量太大。
•	mixed，一种折中的方案，普通操作使用statement记录，当无法使用statement的时候使用row。

此外，新版的MySQL中对row级别也做了一些优化，当表结构发生变化的时候，会记录语句而不是逐行记录。

Read More

当MySQL单表记录数过大时，增删改查性能都会急剧下降

单表优化

除非单表数据未来会一直不断上涨，否则不要一开始就考虑拆分，拆分会带来逻辑、部署、运维的各种复杂度，一般以整型值为主的表在千万级以下，字符串为主的表在五百万以下是没有太大问题的。
而事实上很多时候 MySQL 单表的性能依然有不少优化空间，甚至能正常支撑千万级以上的数据量。

字段

▪	尽量使用 TINYINT、 SMALLINT、 MEDIUM_INT 作为整数类型而非 INT，如果非负则加上 UNSIGNED
▪	VARCHAR 的长度只分配真正需要的空间
▪	使用枚举或整数代替字符串类型
▪	尽量使用 TIMESTAMP 而非 DATETIME
▪	单表不要有太多字段，建议在 20 以内
▪	避免使用 NULL 字段，很难查询优化且占用额外索引空间
▪	用整型来存 IP

Read More

连接与断开服务器

1
2
3
4

mysql -h 地址 -P 端口 -u 用户名 -p 密码

SHOW PROCESSLIST -- 显示哪些线程正在运行
SHOW VARIABLES -- 显示系统变量信息

数据库操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- 查看当前数据库
    SELECT DATABASE();
-- 显示当前时间、用户名、数据库版本
    SELECT now(), user(), version();
-- 创建库
    CREATE DATABASE[ IF NOT EXISTS] 数据库名 数据库选项
    数据库选项：
        CHARACTER SET charset_name
        COLLATE collation_name
-- 查看已有库
    SHOW DATABASES[ LIKE  PATTERN ]
-- 查看当前库信息
    SHOW CREATE DATABASE 数据库名
-- 修改库的选项信息
    ALTER DATABASE 库名 选项信息
-- 删除库
    DROP DATABASE[ IF EXISTS] 数据库名
        同时删除该数据库相关的目录及其目录内容

Read More

工作也有一段时间了，今天休息，正好有时间把最近所学的东西整理一下。
java是一门面向对象编程的语言，不仅吸收了c++语言的各种优点，还摒弃了c++中难以理解的多继承，指针等概念，作为静态面向对象语言编程代表，极好地实现了面向对象理论，让程序员以抽象的思维方式进行复杂的编程。
java语言的主要特点：
简单性
java不支持goto语句，代之以提供break和coninue语句以及异常处理，java还剔除了c++的操作符重载和多继承特征，java没有结构体，所有的数据都是对象，数组和字符串也是，所以不需要指针，java能够自动的处理对象的引用和间接引用，实现自动化的无用单元收集（自动垃圾回收GC），使程序不用为存储问题烦恼，把更多的时间和精力花在处理业务。
面向对象
封装，继承，多态，
在一个面向对象的系统中，类（class）是数据和操作数据的方法的集合，数据和方法一起描述对象（object）的状态和行为，每一个对象是其行为和状态的封装，类是按一定体系和层次来安排的，子类可以从父类中继承行为。java程序是用类和包来组织的。包是类的扩展集合，
分布性
java设计成支持在网络上应用，它是分布式语言，支持各种层次的网络连接，java的socket类支持可靠的流网络连接，所以用户可以生产分布式的客户机和服务器，网络变成类软件应用的分布运载工具，java只需编写一次，就可以到处运行。
编译和解释性
java编译程序生成字节码（bytecode）而不是通常的机器码，java字节码提供对体系结构中性的目标文件格式，java程序可以在任何实现了java解释程序和运行环境（JRE）的系统中运行。在java虚拟机环境中，程序开发的标准链接阶段，java只是把新类装进环境的过程，它是增量式，轻量级的过程。
稳健性
java原来是被用来编写嵌入式系统软件的强类型语言，它允许扩展编译时检查潜在的类型不匹配问题，java要求显式的类型声明，不支持c风格的隐式声明，这些严格的要求保证类编译程序能捕捉调用错误，
java的存储模型，java不支持指针，它消除了重写存储和覆盖数据的可能性，java的垃圾回收机制能有效预防内存泄漏和其他有关动态存储分配和内存释放的错误。java解释程序也只需许多运行时的检查，比如空指针，数组越界等异常。说到这，java的异常处理也使得java程序更稳健的，使用try/catch/finally 语句，程序很容易定位出错的代码，大大简化了错误的处理和恢复任务。
安全性
java的存储分配模型是预防恶意代码的主要方法之一
可移植性
java程序是运行在java虚拟机中或者JRE中，java的编译程序也是用java编写的，而java的运行环境是用ANSI C编写的。sun公司提供了不同的操作系统java虚拟机（java运行环境）

Read More

Markdown 语法和 MWeb 写作使用说明
Markdown 的设计哲学
本文约定
标题
第一级标题

第二级标题

第六级标题

强调
换行
列表
无序列表
有序列表
任务列表（Task lists）
图片
链接
区块引用
行内代码
多行或者一段代码
顺序图或流程图
表格
删除线
分隔线
MathJax
脚注（Footnote）
注释和阅读更多
TOC

Markdown 语法和 MWeb 写作使用说明

Markdown 的设计哲学

Markdown 的目標是實現「易讀易寫」。
不過最需要強調的便是它的可讀性。一份使用 Markdown 格式撰寫的文件應該可以直接以純文字發佈，並且看起來不會像是由許多標籤或是格式指令所構成。
Markdown 的語法有個主要的目的：用來作為一種網路內容的寫作用語言。

Read More