Java使用JNI调用动态链接库

项目中有个需求,需要根据用户上传的图片分析出用户的一些面部特征,血压,血氧等用户体征数据,Java层接收用户上传图片,保存,然后将图片地址传递给C++算法去处理,算法层计算出结果并返回给Java层一个对象。这里做个简单的demo模拟这个需求,大概需要的技术有C++,JNI Java等。

阅读更多

各种排序的比较

排序从数据结构上讲分为插入排序,交换排序,选择排序,归并排序,如下图

排序的类型和方法

排序分为内部排序和外部排序,内部排序是排序过程中所有数据是放入内存进行处理的,外部排序是排序期间全部对象个数太多,不能同时放入你内存进行处理,需要不断在内外存进行移动的序列,下面讨论的是内部排序。

插入排序

插入排序的丝线格式将对象插入到前面已经排好序的子序列中。直到全部对象插入完成为止。

直接插入排序是初始化两个数组,一个数组的元素为原始序列,一个数组的元素为null ,引用arr[0]作为监视哨。直接插入排序是一种稳定的排序算法,时间复杂度为O(n^2)

public class InsertSort {

    public static void main(String []args){
        int []arr={1,45,767,879,45,788,443 ,545,4,6,7,85};
        int i,j;
        for(i=2;i<arr.length;i++){
            arr[0]=arr[i];
            j=i-1;
            while (arr[0]<arr[j]) {
                arr[j+1]=arr[j];
                        j--;
                
            }
            arr[j+1]=arr[0];
        }
        for (int j2 = 1; j2 < arr.length; j2++) {
            System.out.print(arr[j2]+" ");
        }
        
    }
}

希尔排序

希尔排序又称为缩小增量排序,它是一种对直接插入排序的改进,将整个子序列分成若干子序列分别进行直接插入排序。待整个序列基本有序后再对全部序列进行一次直接插入排序。

public class ShellSort {

public static void  main(String []args) {
    int  []arr={1,23,435,657,87,5,5,768,4453,778,32};
    int i,j,d ,n=arr.length;
    for ( d = n/2; d >0; d=d/2) {
        for ( i = d+1; i <=n; i++) {
            arr[0] = arr[i];
            j=i-d;
            while (j>=0&&arr[0]<arr[j]) 
                arr[j+d]=arr[j];
                j=j-d;
                arr[j+d]=arr[0];
        }
    }
    
for (int k = 1; k < arr.length-1; k++) {
    System.out.print(arr[k]+" ");
}

}
}
##交换排序
冒泡排序

冒泡排序是一种最直观的排序方法,排序过程中,将相邻的元素进行比较,若前面的元素大于后面的元素,则将他们进行交换。冒泡排序是一种稳定的排序算法。时间复杂度为O(n^2).

public void sort(char arr[]){
int exchange=0;  
char temp='a';  
for(int c=0;c<length;c++) 
 {  
for(int ch=0; ch<arr.length()-1;ch++){  
   if(arr[ch]>arr[ch+1]){  
   temp=arr[ch];  
   arr[ch]=arr[ch+1];  
   arr[ch+1]=temp;  
   exchange=1;  
}  
}  
if(exchange==0) break;  
}  
for (int d = 0; d < arr.length(); d++)
     {  
   System.out.print(arr[d]);  
 }  
}

快速排序

快速排序是对冒泡排序的一种改进,,在冒泡排序中,数据的移动是在相邻的两个元素之间,所以造成了移动次数较多。快速排序是从两端向中间进行的。其基本做法是选择排序中的一个元素为基准,一般选取第一个元素。通过一趟排序将带排序的记录分为左右两个子序列。左边的所有元素均小于或等于关键字,右边的所有元素均大于或等于关键字。

public class QuickSort {
    static int []arr={1,223,65,44,2,5,3,64,2,5};
    static int high = arr.length;
    public static int Partition(int arr[],int low,int high){
        arr[0] = arr[low];
        while (low<high) {
            while (low<high&&arr[high]>=arr[0])
                --high;
                arr[low]=arr[high];
            while (low<high&&arr[low]<=arr[0])
                arr[high]=arr[low];
            
        }
        arr[low]=arr[0];
        return low;
        
    }
    public static void Quicksort(int arr[],int low,int high){
        int loc;
        if(low<high){
            loc = Partition(arr,low,high);
            Quicksort(arr, low, loc-1);
            Quicksort(arr, loc+1, high);
    }
    }
    public static void main(String []args) {
        Quicksort(arr, 0, high);
        for (int i = 0; i < args.length; i++) {
            System.out.print(arr[i]);
        }
            
        }
}

选择排序

简单选择排序

简单选择排序也称直接选择排序,它先选出关键字最小的元素放在第一个位置,然后选出关键字第二小的元素放在第二个位置,依次….简单选择排序是一种不稳定的算法,时间复杂度为O(n^2)

public class SelectSort {

    public static void  main(String []args) {
        int []arr = {1,3234,6788,7,66,89,57,5,6,95,3,6};
        int n = arr.length-1;
        int i,j,min;
        for ( i = 1; i < n; i++) 
        {
            min = i;
            for ( j = i+1; j <=n; ++j) 
                if (arr[min]>arr[j]) 
                    min= j;
                if(min!=i)
                {
                    arr[0]=arr[min];
                    arr[min]=arr[i];
                    arr[i]=arr[0];
                }
            }
        for (int k = 1; k < arr.length; k++) {
            System.out.print(arr[k]+" ");
        }
    }
}

堆排序

public class HeapSort {
private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
public static void main(String[] args) {
    buildMaxHeapify(sort);
    heapSort(sort);
    print(sort);
}
 
private static void buildMaxHeapify(int[] data){
    //没有子节点的才需要创建最大堆,从最后一个的父节点开始
    int startIndex = getParentIndex(data.length - 1);
    //从尾端开始创建最大堆,每次都是正确的堆
    for (int i = startIndex; i >= 0; i--) {
        maxHeapify(data, data.length, i);
    }
}
 
/**
 * 创建最大堆
 * @param data
 * @param heapSize需要创建最大堆的大小,一般在sort的时候用到,因为最多值放在末尾,末尾就不再归入最大堆了
 * @param index当前需要创建最大堆的位置
 */
private static void maxHeapify(int[] data, int heapSize, int index){
    // 当前点与左右子节点比较
    int left = getChildLeftIndex(index);
    int right = getChildRightIndex(index);
 
    int largest = index;
    if (left < heapSize && data[index] < data[left]) {
        largest = left;
    }
    if (right < heapSize && data[largest] < data[right]) {
        largest = right;
    }
    //得到最大值后可能需要交换,如果交换了,其子节点可能就不是最大堆了,需要重新调整
    if (largest != index) {
        int temp = data[index];
        data[index] = data[largest];
        data[largest] = temp;
        maxHeapify(data, heapSize, largest);
    }
}
 
/**
 * 排序,最大值放在末尾,data虽然是最大堆,在排序后就成了递增的
 * @param data
 */
private static void heapSort(int[] data) {
    //末尾与头交换,交换后调整最大堆
    for (int i = data.length - 1; i > 0; i--) {
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        maxHeapify(data, i, 0);
    }
}
 
/**
 * 父节点位置
 * @param current
 * @return
 */
private static int getParentIndex(int current){
    return (current - 1) >> 1;
}
 
/**
 * 左子节点position注意括号,加法优先级更高
 * @param current
 * @return
 */
private static int getChildLeftIndex(int current){
    return (current << 1) + 1;
}
 
/**
 * 右子节点position
 * @param current
 * @return
 */
private static int getChildRightIndex(int current){
    return (current << 1) + 2;
}
 
private static void print(int[] data){
    int pre = -2;
    for (int i = 0; i < data.length; i++) {
        if (pre < (int)getLog(i+1)) {
            pre = (int)getLog(i+1);
            System.out.println();
        } 
        System.out.print(data[i] + " |");
    }
}
 
/**
 * 以2为底的对数
 * @param param
 * @return
 */
private static double getLog(double param){
    return Math.log(param)/Math.log(2);
}

}

##归并排序
下面图片和代码来自维基百科

public int[] Two_Way_Merge_Sort(int[] A, int[] B) {
    int[] C = new int[A.length + B.length];
    int k = 0;
    int i = 0;
    int j = 0;
    while(i < A.length && j < B.length) {
        if (A[i] < B[j])
            C[k++] = A[i++];
        else
            C[k++] = B[j++];
    }
    while (i < A.length) 
        C[k++] = A[i++];
    while (j < B.length) 
        C[k++] = B[j++];
    return C;
}
 
/**
 * one good implements. <br />
 *
 * 
 */
public class Sort {
 
public static final int CUTOFF = 11;
 
/**
     * merge sort algorithm.
     * 
     * @param arr an array of Comparable item.
 * 1.here only use one temp array (think about it). <br />
 * 2.copy the element back after the sub merge operation. @see merge(T, T, int, int);
 * the above two points make it more efficient. <br />
     */
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> void mergeSort( T[] arr ) {
//you may use insertionSort instead when the arr.length is not that large.
        /*if ( arr.length < CUTOFF ) {
            insertionSort( arr );
            return;
        }*/
 
        T[] tmpArr = (T[]) new Comparable[arr.length];
 
        mergeSort(arr, tmpArr, 0, arr.length - 1);
    }
 
    /**
     * internal method to make a recursive call to merge. <br />
     * 
     * @param arr an array of Comparable items. <br />
     * @param tmpArr temp array to placed the merged result. <br />
     * @param left left-most index of the subarray. <br />
     * @param right right-most index of the subarray. <br />
     */
    private static <T extends Comparable<? super T>> 
    void mergeSort( T[] arr, T[] tmpArr,
            int left, int right ) {
        //recursive way
        if ( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort(arr, tmpArr, left, center);
            mergeSort(arr, tmpArr, center + 1, right);
            merge(arr, tmpArr, left, center + 1, right);
        }
 
        //loop instead,not working, do it youself.
/*
int n = 0, j;
        while ( true ) {
            int step = ( int ) Math.pow(2, ++n);
            int len = step / 2;
            int count = arr.length / step;
            int rpos;
 
            //previous pow(2, k) elements
            for ( j = 0; j < count; j++ ) {
                rpos = j + len;
                System.out.println(j+", "+rpos);
                merge( arr, tmpArr, j, rpos, rpos + len - 1);
            }
 
            //the rest elements
            //for () ;
 
            if ( step * 2 >= arr.length ) break; 
        }
 */
    } 
 
    /**
     * internal method to merge the sorted halves of a subarray. <br />
     * 
     * @param arr an array of Comparable items. <br />
     * @param tmpArr temp array to placed the merged result. <br />
     * @param leftPos left-most index of the subarray. <br />
     * @param rightPos right start index of the subarray. <br />
     * @param endPos right-most index of the subarray. <br />
     */
    private static <T extends Comparable<? super T>> void merge( T[] arr, T[] tmpArr,
            int lPos, int rPos, int rEnd ) {
        int lEnd = rPos - 1;
        int tPos = lPos;
        int leftTmp = lPos;
 
        while ( lPos <= lEnd && rPos <= rEnd  ) {
            if ( arr[lPos].compareTo( arr[rPos] ) <= 0 )
                tmpArr[ tPos++ ] = arr[ lPos++ ];
            else 
                tmpArr[ tPos++ ] = arr[ rPos++ ];
        }
 
        //copy the rest element of the left half subarray.
        while ( lPos <= lEnd ) 
            tmpArr[ tPos++ ] = arr[ lPos++ ];
        //copy the rest elements of the right half subarray. (only one loop will be execute)
        while ( rPos <= rEnd ) 
            tmpArr[ tPos++ ] = arr[ rPos++ ];
 
        //copy the tmpArr back cause we need to change the arr array items.
        for ( ; rEnd >= leftTmp; rEnd-- )
            arr[rEnd] = tmpArr[rEnd];
    }
}

欢迎长按下图 -> 识别图中二维码或者微信扫一扫关注我的公众号

排序算法

休息了一个月了,真真实实的睡过来的。主要是没想清楚前边该怎么走,现在稍微明白了。该继续工作,努力了。这几天闲来无事,就做了几件事,第一个是把博客迁移到了VPS上面,毕竟国内上Github还是有点慢,之前不上SS,博客就上不去。本来是想用Ghost搭博客系统的,不过单纯以技术博客来说,用Ghost有点大材小用了。最后还是回来用Hexo。不过没几个自己喜欢的主题。之前改了几个主题,都觉得改的不咋样,前端技术太烂加上超强的审美能力,尴尬。第二个是搭了个SS管理界面,当前只有日本和新加坡节点,反正用着玩。不过加用户就方便了。但个人用的话还是workers靠谱,随意上2w。第三就是学习了下算法,之前面试的面试题没看懂。心都碎了。下面是记录比较基础的几个算法。慢慢写吧。后面尽量多接触算法。毕竟哪儿都不缺码农。后面就做Java,完善算法,数据库能力。

阅读更多

求和算法

来北京半年年。天气好,空气差。还是觉得有些不自在。最近在学习前端,闲暇之余刷一下LeetCode,记得读大学的时候,很是讨厌算法这东西。咋看也不会,而且还觉得没什么卵用。昨天学习算法,竟然入迷了。感觉很是好玩。入了代码狗的门之后才明白,写出代码容易,写出好的代码不容易。能写出好代码的才叫程序员。写的烂的那就码农。后面一些列文章都是算法和一些基本功。毕竟和别人差的太远。高调不起来。

阅读更多

编辑距离算法

前面一篇文章觉得不复杂,当选择Pick one的时候,整个世界都崩溃了。文章记录的是现在都两个字符串word1和word2,如何通过插入,删除,替换的方式将字符串从word1转换为word2.计算出这个转换过程的最小步骤。算出这道题后,后面我还在网上找了一道拓展的题。据说是来自*<<程序员编程艺术:面试和算法心得>>*。我也没有读过,并不确定,但是给出了解法。就这两个题,耗费了我整整一天,我已经是个废人了。欢迎读者给出更优秀的答案。该吐槽就吐槽,千万别犹豫。

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

阅读更多

链表相加算法

20170311804232017-03-12.jpg

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

}
}

题目是说给你两个存放正整数的链表,链表是倒序放的。让你将两个链表相加,然后返回。

阅读更多