Android 算法篇（java）手写

1. 二分查找（手写）

public static int binarySearch(int[] a, int key){
    int low, mid, high;
    low = 0;
    high = a.length - 1; //最大下标
    while (low <= high){
        mid = (high + low) / 2; //折半下标
        if (key > a[mid]){
            low = mid + 1;    //关键字比折半值大，则最小下标调成折半下标的下一位
        }else if (key < a[mid]){
            high = mid - 1;    //关键字比折半值小，则最大下标调成折半下标的前一位
        }else{
            return mid;
        }
    }
    return -1;
}

2. 反转链表（手写）

//节点类
public class ListNode{
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val = val;
    }
}

//方法1
public ListNode reverseLinkedList(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode p = new ListNode(-1);  //拟1个头节点
    p.next = head;
    ListNode nextNode = head.next;
    while (nextNode != null){
        //后一个节点调整到最前
        head.next = nextNode.next;
        nextNode.next = p.next;
        p.next = nextNode;
        nextNode = head.next;
    }
    return p.next;
}

//方法2，递归
public ListNode reverseLinkedList(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode pNode = reverseLinkedList(head.next);
    head.next.next = head;
    head.next = null;
    return pNode;
}

3. 冒泡排序

package totoSort;
 
import java.util.Arrays;
 
public class TotoSort {
    public static void main(String[] args) {
        int[] arrays = new int[] {6,5,4,3,2,1};
        System.out.println(Arrays.toString(arrays));
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }
    public static void sort(int[] arrays) {
        int temp = 0;
        //比较几轮
        for(int i = 0; i < arrays.length - 1; i++) {
            for(int j = 0; j < arrays.length - 1 - i; j++) {
                if(arrays[j] > arrays[j + 1]) {
                    temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
    }
}

4. 判断数组中是否有重复元素

选择排序：从头选择元素作为索引，选出往后未排序元素中最大或者最小的元素值与索引值置换，依次类推，直至所有元素均排序完成。

//先选择排序，再判断相邻元素是否有重叠
public static boolean judge(int[] a){
    for (int j=0;j<a.length-1;j++){
         int temp=j;
         for (int k=j+1;k<a.length;k++){
             if (a[k]<a[temp]){
                 temp=k;
             }
         }
         int t=a[j];
         a[j]=a[temp];
         a[temp]=t;
     }
     boolean result=false;
     for (int j=0;j<a.length-1;j++){
         if (a[j+1]==a[j]){
             result=true;
             break;
         }
     }
     return result;
 }