现代的设计任务大多通过计算机编程来完成，而算法起到了至关重要的作用。可以毫不夸张地说，算法是一切程序设计的灵魂和基础。选择合理的算法，可以起到事半功倍的效果。 　　赵志云、衡友跃编著的《Java常用算法手册》分三篇，共13章，分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述，然后重点分析了数据结构和基本算法思想；接着，详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用；最后，列举了算法的一些常见面试题。 　　书中知识点覆盖全面，结构安排紧凑，讲解详细，实例丰富。全书对每一个知识点都给出了相应的算法及应用实例，虽然这些例子都是以Java语言来编写的，但是这些算法并不局限于Java语言。如果读者采用其他的编程语言，例如C++、C、C#等，只要根据其语法格式进行适当的修改便可以了。 　　《Java常用算法手册》旨在帮助Java语言初级程序员深入了解Java算法思想，提升其语言代码编程能力，还可以作为大中专院校学生学习数据结构和算法的参考书，也可为教师授课提供素材，同时还可以作为具有一定编程经验的程序员的参考用书。 第1篇 算法基础篇 1 第1章 算法概述 1 1.1 什么是算法 1 1.2 算法的 发展历史 2 1.3 算法的分类 3 1.4 算法相关概念的区别 3 1.4.1 算法与公式的关系 4 1.4.2 算法与程序的关系 4 1.4.3 算法与数据结构的关系 4 1.5 算法的表示 4 1.5.1 自然语言表示 5 1.5.2 流程图表示 5 1.5.3 N-S 图表示 6 1.5.4 伪代码表示 7 1.6 算法的性能评价 7 1.6.1 时间复杂度 8 1.6.2 空间复杂度 8 1.7 算法实例 8 1.7.1 查找数字 8 1.7.2 创建项目 10 1.7.3 编译执行 12 1.8 算法的新进展 13 1.9 小结 14 第2章 数据结构 15 2.1 数据结构概述 15 2.1.1 什么是数据结构 15 2.1.2 数据结构中的基本概念 16 2.1.3 数据结构的内容 16 2.1.4 数据结构的分类 18 2.1.5 数据结构的几种存储方式 18 2.1.6 数据类型 19 2.1.7 常用的数据结构 20 2.1.8 选择合适的数据结构解决实际问题 21 2.2 线性表 21 2.2.1 什么是线性表 21 2.2.2 线性表的基本运算 22 2.3 顺序表结构 23 2.3.1 准备数据 23 2.3.2 初始化顺序表 24 2.3.3 计算顺序表长度 24 2.3.4 插入结点 24 2.3.5 结点 25 2.3.6 删除结点 25 2.3.7 查找结点 25 2.3.8 显示所有结点 26 2.3.9 顺序表操作实例 26 2.4 链表结构 30 2.4.1 什么是链表结构 30 2.4.2 准备数据 31 2.4.3 追加结点 31 2.4.4 插入头结点 32 2.4.5 查找结点 33 2.4.6 插入结点 34 2.4.7 删除结点 35 2.4.8 计算链表长度 35 2.4.9 显示所有结点 36 2.4.10 链表操作实例 36 2.5 栈结构 41 2.5.1 什么是栈结构 41 2.5.2 准备数据 41 2.5.3 初始化栈结构 42 2.5.4 断空栈 42 2.5.5 判断满栈 43 2.5.6 清空栈 43 2.5.7 释放空间 43 2.5.8 入栈 43 2.5.9 出栈 44 2.5.10 读结点数据 44 2.5.11 栈结构操作实例 45 2.6 队列结构 47 2.6.1 什么是队列结构 48 2.6.2 准备数据 48 2.6.3 初始化队列结构 49 2.6.4 判断空队列 49 2.6.5 判断满队列 49 2.6.6 清空队列 50 2.6.7 释放空间 50 2.6.8 入队列 50 2.6.9 出队列 51 2.6.10 读结点数据 51 2.6.11 计算队列长度 52 2.6.12 队列结构操作实例 52 2.7 树结构 55 2.7.1 什么是树结构 56 2.7.2 树的基本概念 56 2.7.3 二叉树 57 2.7.4 准备数据 60 2.7.5 初始化二叉树 61 2.7.6 添加结点 61 2.7.7 查找结点 63 2.7.8 获取左子树 63 2.7.9 获取右子树 64 2.7.10 判断空树 64 2.7.11 计算二叉树深度 64 2.7.12 清空二叉树 65 2.7.13 显示结点数据 65 2.7.14 遍历二叉树 65 2.7.15 树结构操作实例 67 2.8 图结构 74 2.8.1 什么是图结构 74 2.8.2 图的基本概念 75 2.8.3 准备数据 79 2.8.4 创建图 81 2.8.5 清空图 82 2.8.6 显示图 82 2.8.7 遍历图 83 2.8.8 图结构操作实例 84 2.9 小结 87 第3章 基本算法思想 88 3.1 常用算法思想概述 88 3.2 穷举算法思想 88 3.2.1 穷举算法基本思想 89 3.2.2 穷举算法实例 89 3.3 递推算法思想 90 3.3.1 递推算法基本思想 91 3.3.2 递推算法实例 91 3.4 递归算法思想 92 3.4.1 递归算法基本思想 93 3.4.2 递归算法实例 93 3.5分 治算法思想 94 3.5.1分 治算法基本思想 94 3.5.2分 治算法实例 95 3.6 概率算法思想 98 3.6.1 概率算法基本思想 99 3.6.2 概率算法实例 99 3.7 小结 101 第2篇 算法应用篇 102 第4章 排序算法 102 4.1 排序算法概述 102 4.2 冒泡排序法 103 4.2.1 冒泡排序算法 103 4.2.2 冒泡排序算法实例 104 4.3 选择排序法 106 4.3.1 选择排序算法 106 4.3.2 选择排序算法实例 107 4.4 插入排序法 109 4.4.1 插入排序算法 109 4.4.2 插入排序算法实例 111 4.5 Shell 排序法 112 4.5.1 Shell 排序算法 112 4.5.2 Shell排序算法实例 113 4.6 快速排序法 115 4.6.1 快速排序算法 115 4.6.2 快速排序算法实例 117 4.7 堆排序法 119 4.7.1 堆排序算法 119 4.7.2 堆排序算法实例 123 4.8 合并排序法 125 4.8.1 合并排序算法 126 4.8.2 合并排序算法实例 128 4.9 排序算法的效率 131 4.10 排序算法的其他应用 132 4.10.1 反序排序 132 4.10.2 字符串数组的排序 134 4.10.3 字符串的排序 137 4.11 小结 139 第5章 查找算法 140 5.1 查找算法概述 140 5.2 顺序查找 141 5.2.1 顺序查找算法 141 5.2.2 顺序查找操作实例 141 5.3 折半查找 143 5.3.1 折半查找算法 143 5.3.2 折半查找操作实例 145 5.4 数据结构中的查找算法 147 5.4.1 顺序表结构中的查找算法 148 5.4.2 链表结构中的查找算法 151 5.4.3 树结构中的查找算法 154 5.4.4 图结构中的查找算法 155 5.5 小结 156 6.1 判断闰年 157 6.2 多项式计算 159 6.2.1 一维多项式求值 159 6.2.2 二维多项式求值 161 6.2.3 多项式乘法 163 6.2.4 多项式除法 164 6.3 随机数生成算法 167 6.3.1 Java语言中的随机方法 167 6.3.2 [0，1]之间均匀分布的随机数算法 169 6.3.3 产生任意范围的随机数 170 6.3.4 [m，n]之间均匀分布的随机整数算法 171 6.3.5 正态分布的随机数生成算法 173 6.4 复数运算 174 6.4.1 简单的复数运算 175 6.4.2 复数的赛运算 177 6.4.3 复指数运算 178 6.4.4 复对数运算 180 6.4.5 复正弦运算 181 6.4.6 复余弦运算 182 6.5 阶乘 183 6.5.1 使用循环来计算阶乘 183 6.5.2 使用递归来计算阶乘 184 6.6 计算n的近似值 185 6.6.1 割圆术 186 6.6.2 蒙特卡罗算法 189 6.6.3 级数公式 191 6.7 矩阵运算 193 6.7.1 矩阵加法 193 6.7.2 矩阵减法 195 6.7.3 矩阵乘法 196 6.8 方程求解 198 6.8.1 线性方程求解——高斯消元法 198 6.8.2 非线性方程求解——二分法 203 6.8.3 非线性方程求解——牛顿迭代法 205 6.9 小结 208 第7章 数据结构问题 209 7.1 动态数组排序 209 7.1.1 动态数组的存储和排序 209 7.1.2 动态数组排序实例 210 7.2 约瑟夫环 212 7.2.1 简单约瑟夫环算法 213 7.2.2 简单约瑟夫环求解 214 7.2.3 复杂约瑟夫环算法 216 7.2.4 复杂约瑟夫环求解 217 7.3 城市之间的最短总距离 220 7.3.1 最短总距离算法 220 7.3.2 最短总距离求解 222 7.4 最短路径 227 7.4.1 最短路径算法 227 7.4.2 最短路径求解 229 7.5 括号匹配 234 7.5.1 括号匹配算法 235 7.5.2 括号匹配求解 236 7.6 小结 239 第8章 数论问題 240 8.1 数论概述 240 8.1.1 数论概述 240 8.1.2 数论的分类 241 8.1.3 初等数论 242 8.1.4 本章用到的基本概念 242 8.2 完全数 243 8.2.1 什么是完全数 243 8.2.2 计算完全数算法 244 8.3 亲密数 246 8.3.1 什么是亲密数 246 8.3.2 计算亲密数算法 246 8.4 水仙花数 249 8.4.1 什么是水仙花数 249 8.4.2 计算水仙花数算法 250 8.5 自守数 252 8.5.1 什么是自守数 252 8.5.2 计算自守数算法 253 8.6 最大公约数 257 8.6.1 计算最大公约数算法——辗转相除法 257 8.6.2 计算最大公约数算法——Stein算法 258 8.6.3 计算最大公约数示例 259 8.7 最小公倍数 260 8.8 素数 262 8.8.1 什么是素数 262 8.8.2 计算素数算法 262 8.9 回文素数 264 8.9.1 什么是回文素数 264 8.9.2 计算回文素数算法 264 8.10 平方回文数 267 8.10.1 什么是平方回文数 267 8.10.2 计算平方回文数算法 267 8.11 分解质因数 269 8.12 小结 271 第9章 算法经典趣埋 272 9.1 百钱买百鸡 272 9.1.1 百钱买百鸡算法 272 9.1.2 百钱买百鸡求解 273 9.2 五家共井 274 9.2.1 五家共井算法 274 9.2.2 五家共井求解 275 9.3 鸡兔同笼 277 9.3.1 鸡兔同笼算法 277 9.3.2 鸡兔同笼求解 277 9.4 猴子吃桃 278 9.4.1 猴子吃桃算法 278 9.4.2 猴子吃桃求解 279 9.5 舍罕王赏麦 280 9.5.1 舍罕王赏麦问题 280 9.5.2 舍罕王赏麦求解 281 9.6 汉诺塔 282 9.6.1 汉诺塔算法 282 9.6.2 汉诺塔求解 284 9.7 窃贼问题 285 9.7.1 窃贼问题算法 285 9.7.2 窃贼问题求解 287 9.8 马踏棋盘 290 9.8.1 马踏棋盘算法 290 9.8.2 马踏棋盘求解 291 9.9 八皇后问题 294 9.9.1 八皇后问题算法 294 9.9.2 八皇后问题求解 295 9.10 寻找假银币 297 9.10.1 寻找假银币算法 297 9.10.2 寻找假银币求解 299 9.11 青蛙过河 301 9.11.1 青蛙过河算法 302 9.11.2 青蛙过河求解 303 9.12 三色旗 306 9.12.1 三色旗算法 306 9.12.2 三色旗求解 308 9.13 渔父捕鱼 310 9.13.1 渔父捕鱼算法 310 9.13.2 渔父捕鱼求解 310 9.14 爱因斯坦的阶梯 311 9.14.1 爱因斯坦的阶梯算法 312 9.14.2 爱因斯坦的阶梯求解 312 9.15 兔子产仔 313 9.15.1 兔子产仔算法 313 9.15.2 兔子产仔求解 314 9.16 常胜将军 315 9.16.1 常胜将军算法 315 9.16.2 常胜将军求解 316 9.17 新郎和新娘 318 9.17.1 新郎和新娘算法 318 9.17.2 新郎和新娘求解 319 9.18 三色球 320 9.18.1 三色球算法 320 9.18.2 三色球求解 321 9.19 小结 322 第10章 游戏中的算法 323 10.1 洗扑克牌算法 323 10.1.1 洗扑克牌算法 323 10.1.2 洗扑克牌实例 324 10.2 取火柴游戏算法 327 10.2.1 取火柴游戏算法 327 10.2.2 取火柴游戏实例 328 10.3 10点半算法 330 10.3.1 10点半算法 330 10.3.2 10点半游戏实例 335 10.4 生命游戏 342 10.4.1 生命游戏的原理 342 10.4.2 生命游戏的算法 343 10.4.3 生命游戏实例 344 10.5 小结 349 第11章 密码学概述 350 11.1 密码学概述 350 11.1.1 密码学的发展 350 11.1.2 密码学的基本概念 351 11.1.3 柯克霍夫斯原则 352 11.1.4 经典密码学算法 352 11.2 换位加密解密算法 353 11.2.1 换位加密解密算法 353 11.2.2 换位加密解密算法实例 356 11.3 替换加密解密算法 359 11.3.1 替换加密解密算法 359 11.3.2 替换加密解密算法实例 360 11.4 位加密解密算法 363 11.4.1 位加密解密算法 363 11.4.2 位加密解密算法实例 364 11.5 一次一密加密解密算法 366 11.5.1 一次一密加密解密算法 366 11.5.2 一次一密加密解密算法实例 367 11.6 小结 369 第12章 压缩与解压缩算法 370 12.1 压缩与解压缩概述 370 12.1.1 压缩与解压缩分类 370 12.1.2 典型的压缩解压缩算法 370 12.2 压缩算法 371 12.3 解压缩算法 374 12.4 压缩解压缩实例 376 12.5 小结 384 第3篇 算法面试篇 385 第13 章算法面试題 385 13.1 基础算法 385 13.1.1 字符串匹配 385 13.1.2 哥德巴赫猜想的近似证明 388 13.1.3 将一个正整数分解质因数 389 13.1.4 怎样实现金额转换 391 13.1.5 数字排列 396 13.1.6 数字拆解 398 13.1.7 数字组合 400 13.2 思维扩展算法 403 13.2.1 蛇形打印 403 13.2.2 24点算法 405 13.2.3 双色球随机摇号 409 13.2.4 巧女少过桥 412 13.2.5 猴子吃桃 415 13.2.6 天平称物 416 13.2.7 掷骰子游戏 418 13.3 小结 421