之前我们介绍过图的邻接矩阵存储法，它的空间和时间复杂度都是 N2，现在我来介绍另外一种存储图的方法：邻接表，这样空间和时间复杂度就都是 M。对于稀疏图来说，M 要远远小于 N2。先上数据，如下。 4 5 1 4 9 4 3 8 1 2 5 2 4 6 1 3 7第一行两个整数 n m。n 表示顶点个数（顶点编号为 1~n），m 表示边的条数。
上周我们介绍了神奇的只有五行的 Floyd 最短路算法，它可以方便的求得任意两点的最短路径，这称为“多源最短路”。本周来来介绍指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。与 Floyd-Warshall 算法一样这里仍然使用二维数组 e 来存储顶点之间边的关系，初始值如下。
暑假，小哼准备去一些城市旅游。有些城市之间有公路，有些城市之间则没有，如下图。为了节省经费以及方便计划旅程，小哼希望在出发之前知道任意两个城市之前的最短路程。上图中有 4 个城市 8 条公路，公路上的数字表示这条公路的长短。请注意这些公路是单向的。我们现在需要求任意两个城市之间的最短路程，也就是求任意两个点之间的最短路径。
上一节中我们学习了队列，它是一种先进先出的数据结构。还有一种是后进先出的数据结构它叫做栈。栈限定只能在一端进行插入和删除操作。比如说有一个小桶，小桶的直径只能放一个小球，我们现在向小桶内依次放入 2 号、1 号、3 号小球。假如你现在需要拿出 2 号小球，那就必须先将 3 号小球拿出，再拿出 1 号小球，最后才能将 2 号小球拿出来。
新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问 QQ 号，小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时小哈也告诉了小哼解密规则。规则是这样的：首先将第 1 个数删除，紧接着将第 2 个数放到这串数的末尾，再将第 3个数删除并将第 4 个数再放到这串数的末尾，再将第 5 个数删除……
之前讲了三种常用的经典排序。排序算法还有很多，例如选择排序、计数排序、基数排序、插入排序、归并排序和堆排序等等。堆排序是基于二叉树的排序，以后再说吧。先分享一个超酷的排序算法的视频。再来看一个具体的例子《小哼买书》来看看三个排序在应用上的区别和局限性。 小哼的学校要建立一个图书角，老师派小哼去找一些同学做调查，看看同学们都喜欢读哪些书。
上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了 O(N2)。假如我们的计算机每秒钟可以运行 10 亿次，那么对 1 亿个数进行排序，桶排序则只需要 0.1 秒，而冒泡排序则需要 1 千万秒，达到 115 天之久，是不是很吓人。那有没有既不浪费空间又可以快一点的排序算法呢？
简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是 0~2100000000 之间，那你则需要申请 2100000001 个变量，也就是说要写成 int a[2100000001]。因为我们需要用 2100000001 个“桶”来存储 0~2100000000 之间每一个数出现的次数。
在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序，考试的名次需要按照分数排序，网上购物的时候会按照价格排序，电子邮箱中的邮件按照时间排序……总之很多东西都需要排序，可以说排序是无处不在。现在我们举个具体的例子来介绍一下排序算法。首先出场的我们的主人公小哼，上面这个可爱的娃就是啦。期末考试完了老师要将同学们的分数按照从高到低排序。
在各种算法流行的今天，小编为大家汇总了坐在马桶上看算法系列文章，文章图文并茂，风趣易懂，每天一算法让你轻松走进算法的世界，欢迎大家来学习。适用人群本书将繁琐难懂的算法问题，用风趣易懂的方式写出，适合初学者学习学习前提在你开始做本文提供的各种类型例子练习之前，你需要对 C++ 语言有一定的了解致谢：http://blog.51cto.
入门的最好办法就是学习 Android 自带的例子， 这里就通过学习 Android 的 NDK 自带的 demo 程序：hello-jni来达到这个目的。开发环境的搭建android 的 NDK 开发需要在 linux 下进行： 因为需要把 C/C++ 编写的代码生成能在 arm 上运行的.so文件，这就需要用到交叉编译环境，而交叉编译需要在 linux 系统下才能完成。
NDK 开发环境的搭建下载安装 Android NDK 地址：http://blog.sina.com.cn/s/blog_718f290a01012ch0.html下载安装 cygwin由于 NDK 编译代码时必须要用到 make 和 gcc，所以你必须先搭建一个 linux 环境， cygwin 是一个在windows 平台上运行的 unix 模拟环境,它对于学习 unix/linux 操作环境，或者从 unix 到 Windows 的应用程序移植，非常有用。
NDK 产生的背景Android 平台从诞生起，就已经支持 C、C++ 开发。众所周知，Android 的 SDK 基于 Java 实现，这意味着基于Android SDK 进行开发的第三方应用都必须使用 Java 语言。但这并不等同于“第三方应用只能使用 Java”。
这篇文章比较偏理论，详细介绍了在编写本地代码时三种引用的使用场景和注意事项。可能看起来有点枯燥，但引用是在 JNI 中最容易出错的一个点，如果使用不当，容易使程序造成内存溢出，程序崩溃等现象。《Android JNI局部引用表溢出》这篇文章是一个 JNI 引用使用不当造成引用表溢出，最终导致程序崩溃的例子。建议看完这篇文章之后，再去看。
在前面几章我们学习到了，在 Java 中声明一个 native 方法，然后生成本地接口的函数原型声明，再用 C/C++ 实现这些函数，并生成对应平台的动态共享库放到 Java 程序的类路径下，最后在 Java 程序中调用声明的 native 方法就间接的调用到了 C/C++ 编写的函数了，在 C/C++ 中写的程序可以避开 JVM 的内存开销过大的限制、处理高性能的计算、调用系统服务等功能。
在前面我们学习到了在 Native 层如何调用 Java 静态方法和实例方法，其中调用实例方法的示例代码中也提到了调用构造函数来实始化一个对象，但没有详细介绍，一带而过了。还没有阅读过的同学请移步《JNI——C/C++ 访问 Java 实例方法和静态方法》阅读。这章详细来介绍下初始一个对象的两种方式，以及如何调用子类对象重写的父类实例方法。
实例变量和静态变量在上一章中我们学习到了如何在本地代码中访问任意 Java 类中的静态方法和实例方法，本章我们也通过一个示例来学习 Java 中的实例变量和静态变量，在本地代码中如何来访问和修改。静态变量也称为类变量（属性），在所有实例对象中共享同一份数据，可以直接通过【类名.变量名】来访问。
通过前面 5 章的学习，我们知道了如何通过 JNI 函数来访问 JVM 中的基本数据类型、字符串和数组这些数据类型。下一步我们来学习本地代码如何与 JVM 中任意对象的属性和方法进行交互。比如本地代码调用 Java 层某个对象的方法或属性，也就是通常我们所说的来自 C/C++层本地函数的 callback（回调）。
JNI 中的数组分为基本类型数组和对象数组，它们的处理方式是不一样的，基本类型数组中的所有元素都是 JNI 的基本数据类型，可以直接访问。而对象数组中的所有元素是一个类的实例或其它数组的引用，和字符串操作一样，不能直接访问 Java 传递给 JNI 层的数组，必须选择合适的 JNI 函数来访问和设置 Java 层的数组对象。
处理字符串从第三章中可以看出 JNI 中的基本类型和 Java 中的基本类型都是一一对应的，接下来先看一下 JNI 的基本类型定义：typedef unsigned char jboolean; typedef unsigned short jchar; typedef short jshort; typedef float jfloat; typedef double jdouble; typedef int jint;
关注时代Java
