问题背景

Android Studio对JNI的开发是越来越友好了，给Google老大哥大大的赞，AS升级到2.2以后就能通过CMake编译，十分方便，具体可参考官方网站https://developer.android.com/studio/projects/add-native-code，至于JNI编译的其他方式，比如ndk-build，可参考这个哥们的文章。好了说了这么多，并没有讲到今天文章的重点，哈哈，我们现在开始啦。
静态注册, 每个 class 都需要使用 javah 生成一个头文件，并且生成的名字很长书写不便；初次调用时需要依据名字搜索对应的JNI层函数来建立关联关系，会影响运行效率。所以这时候动态注册就登场了。

动态注册

一.入口函数

System.loadLibrary加载完 JNI 动态库之后，调用JNI_OnLoad函数，开始动态注册。这里就是登记注册的地方。注意：一个.so只能存在一个onload方法。

二.登记本地方法

登记本地方法，作用是将 c/c++ 的函数映射到 JAVA 中，而在这里面起到关键作用的是结构体 JNINativeMethod 。他再jni.h文件中

1
2
3
4
5

typedef struct { 
    const char* name; //Java中函数的名字
    const char* signature; //描述了函数的参数和返回值
    void* fnPtr; //函数指针，指向我们调用别人家c++的封装 JNI 函数方法
} JNINativeMethod;

基本思想

快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。
思想:
1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
3.对左右两个分区重复以上步骤直到所有元素都是有序的。
所以我是把快速排序联想成东拆西补或西拆东补，一边拆一边补，直到所有元素达到有序状态。

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
分而治之

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

预备知识

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是对直接选择排序的改进，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序，不适合待排序序列较少的情况。首先简单了解下堆结构。

堆

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

基本思想

希尔排序是直接插入排序的强化版，也称为缩小增量排序。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

冒泡排序

基本思想

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

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

Java实现

加入标记状态 flag 若在一次冒泡中，没有交换 则说明可以停止 减少运行时

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

//冒泡排序
public static void bubbleSort(int[] nums) {
    int size = nums.length;
    int temp;
    boolean flag = true;
    for (int i = 0; i < size - 1 && flag; i++) {
        flag = false;
        for (int j = 0; j < size -1 -i; j++) {
            if (nums[j] > nums[j+1]) {
                temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
                flag = true;
            }
        }
    }
}

时间复杂度O(n*n)