二.查找算法：

    1.顺序查找

    2.二分查找

    需要数组/链表有序，永远折半，直到找到目标。

    int BinarySearch(int a[], int value, int low, int high)

    {

    int mid = low+(high-low)/2;

    if(a[mid]==value)

    1.  return mid;

    if(a[mid]>value)

    1.  return BinarySearch(a, value, low, mid-1);

    if(a[mid]<value)

    1.  return BinarySearch(a, value, mid+1, high);

    }
    3.插值查找：

    把二分查找中的 mid=low+1/2(high-low) ，改为 mid=low+(key-a[low])/(a[high]-a[low])(high-low)一.排序算法：

    排序名称 时间复杂度 是否稳定 额外空间开销
    插入排序 O(n^2) 稳定 O(1)
    冒泡排序 O(n^2) 稳定 O(1)
    选择排序 O(n^2) 不稳定 O(1)
    希尔排序 O(n^2) 不稳定 O(1)
    归并排序 O(nlogn) 稳定 O(n)
    快速排序 O(nlogn) 不稳定 O(1)

    插入排序：双循环，外部指针不断右移，内部指针在外部指针已经移动过的部分中从右向左插入它的排序位置。

    1. public static int[] sort(int[] ins){
    2.     for(int i=1; i<ins.length; i++){
    3.         int temp = ins[i];
    4.         int j;
    5.         for(j=i; j>0&&ins[j-1]>temp; j--){
    6.             ins[j] = ins[j-1];
    7.         }
    8.         ins[j] = temp;
    9.     }
    10.     return ins;
    11. }

    image.pngimage.png
    冒泡排序：双循环，外部指针不断右移，内部指针通过遍历外部指针未移动部分找到极值放入外部指针所在位置。找极值方法为相邻比较，如需要则交换。

    1. public static void BubbleSort(int[] arr) {
    2.   int temp;
    3.   for(int i=0;i<arr.length-1;i++){
    4.     for(int j=0;j<arr.length-i-1;j++){
    5.       if(arr[j+1]<arr[j]){
    6.         temp = arr[j];
    7.         arr[j] = arr[j+1];
    8.         arr[j+1] = temp;
    9.       }
    10.     }
    11.   }
    12. }

    image.pngimage.png
    选择排序：双循环，外部指针不断右移，内部指针通过遍历外部指针未移动部分找到极值放入外部指针所在位置。找极值方法为记录当前极值，直到完成一轮遍历。

    1. public static void selectSort(int[] arr){
    2.     for(int i = 0; i < arr.length-1; i++){
    3.         int min = i;
    4.         for(int j = i+1; j <arr.length ;j++){
    5.             if(arr[j]<arr[min]){
    6.                 min = j;
    7.             }
    8.         }
    9.         int temp = arr[a];
    10.         arr[a] = arr[b];
    11.         arr[b] = temp;
    12.     }
    13. }

    image.pngimage.png
    希尔排序：三重循环。最外层控制步长，内部两个循环是对步长间隔的元素做插入排序。

    1. public static void shellSort(int[] arr) {
    2.   for (int step = arr.length / 2; step > 0; step /= 2) {
    3.     for (int i = step; i < arr.length; i++) {
    4.       int value = arr[i];
    5.       int j;
    6.       for (j = i - step; j >= 0 && arr[j] > value; j -= step) {
    7.         arr[j + step] = arr[j]; 
    8.       }
    9.       arr[j + step] = value;  
    10.     }
    11.   }
    12. }

    归并排序：分治思想，先分成多块排好序的，再合并成一块排好序的，只要定义好单块合并的规则就可以，出口就是已经分成仅一个对象的块。
    算法基础 - 图7

    1. public void merge(int []a,int left,int mid,int right){
    2.   int []tmp=new int[a.length];
    3.   int p1=left,p2=mid+1,k=left;
    5.   while(p1<=mid && p2<=right){
    6.     if(a[p1]<=a[p2])
    7.        tmp[k++]=a[p1++];、
    8.     else
    9.        tmp[k++]=a[p2++];
    10.   }
    12.   while(p1<=mid) tmp[k++]=a[p1++];
    13.   while(p2<=right) tmp[k++]=a[p2++];
    15.   for (int i = left; i <=right; i++) 
    16.      a[i]=tmp[i];
    17. }
    19. public void mergeSort(int [] a,int start,int end){
    20.   if(start<end){
    21.     int mid=(start+end)/2;
    22.     mergeSort(a, start, mid);
    23.     mergeSort(a, mid+1, end);
    24.     merge(a, start, mid, end);
    25.   }
    26. }

    快速排序：选一个需要被排序的数作为基数，大于这个基数的放到右边，小于这个基数的放到左边，一趟结束后，将基数放到中间分隔的位置。第二趟将数组从基数的位置分成两半，分割后的两个的数组继续重复以上步骤，直到数组不能再分为止，排序结束。
    算法基础 - 图8

    1. public static void sort(int[] arr,int start,int end){
    2.   //直到start>=end时结束递归
    3.   if(start<end){
    4.     int left = start;
    5.     int right = end;
    6.     int temp = arr[start];
    8.     while(left<right){
    10.       //右面的数字大于标准数时，右边的数的位置不变，指针向左移一个位置
    11.       while(left<right && arr[right]>temp){
    12.         right--;
    13.       }
    16.       //右边的数字及下标小于或等于基本数，将右边的数放到左边
    17.       if(left<right) {
    18.         arr[left] = arr[right];
    19.         left++;
    20.       }
    21.       //左边的数字小于或等于标准数时，左边的数的位置不变，指针向右移一个位置
    22.       while(left<right && arr[left]<=temp){
    23.         left++;
    24.       }
    25.       //左边的数字大于基本数，将左边的数放到右边
    26.       arr[right] = arr[left];
    27.     }
    29.     //一趟循环结束，此时left=right，将基数放到这个重合的位置，
    30.     arr[left] = temp;
    32.     //将数组从left位置分为两半，继续递归下去进行排序
    33.     sort(arr,start,left);
    34.     sort(arr,left+1,end);
    35.   }
    36. }

    image.pngimage.png二.查找算法：
    1.顺序查找
    2.二分查找
    需要数组/链表有序，永远折半，直到找到目标。

    1. int BinarySearch(int a[], int value, int low, int high)
    2. {
    3.   int mid = low+(high-low)/2;
    4.   if(a[mid]==value)
    5.      return mid;
    6.   if(a[mid]>value)
    7.      return BinarySearch(a, value, low, mid-1);
    8.   if(a[mid]<value)
    9.      return BinarySearch(a, value, mid+1, high);
    10. }

    3.插值查找：
    把二分查找中的 mid=low+1/2(high-low) ，改为 mid=low+(key-a[low])/(a[high]-a[low])(high-low)