排序算法https://www.runoob.com/data-structures/insertion-sort.html

(1)冒泡排序:
a.原理:(以从小到大为例)1)比较数组中两个相邻元素,如果第一个数比第二个数打,我们就交换他的位置
2)每一轮比较中都会选出一个最大的数放在数组尾部
3)一共要进行n-1轮排序
4)每轮排序要进行n-1-i次比较
b.优化:对于冒泡排序有一个小小的优化,就是如果数组中的几个数已经排好序了就没必要再去全部比较新一轮了,就是可以在外层循环内设置一个标志位,flag=false,如果在一轮比较中没有一次交换就说明已经排好序了就不需要进行下一轮了,如果有一次交换就将标志位置为true,继续进行

(2)快速排序https://blog.csdn.net/shujuelin/article/details/82423852
原理:比如说有个数组,长度为10,先以第一个元素为基数,然后再创建两个指针分别是指针i,指针j,一个指向i=0,一个指向i=9,然后两个指针双向奔赴,但是这时候一定要要让非指向基数的指针j先走至于原因等我说完全部流程再说,j遇见比基数小的数就停下歇会,让指针i先走,等他遇到比基数大的时候停下歇会,这时候他们就把停的位置指向的数交换,然后j再继续走,重复上述过程,直到两个指针相遇,相遇之后就把相遇位置的数与基数互换位置,此时基数右侧都是比他小的,左侧都是比他大的然后对两侧数组再进行上述操作,一直到排序完成(先让指针j走原因就是:如果指向基数的指针i先走的话,最后相遇的地方一定是大于基数的,因为牵扯到与基数交换位置,如果大于基数的放在数组头,可能会导致数组排序失败)
优点:快速排序之所以比较快,是因为他相比冒泡排序,每次交换都是跳跃式的,其实就是基于二分的思想每次交换不会像冒牌一样每次只排序相邻的数,交换距离大了,因此交换次数就少了,但是也有坏情况比如指向的基数就是最小的,呢么他就跟冒泡差不多了,
代码:

  1. public class QuickSort {
  2.     public static void quickSort(int[] arr,int low,int high){
  3.         int i,j,temp,t;
  4.         if(low>high){
  5.             return;
  6.         }
  7.         i=low;
  8.         j=high;
  9.         //temp就是基准位
  10.         temp = arr[low];
  12.         while (i<j) {
  13.             //先看右边，依次往左递减
  14.             while (temp<=arr[j]&&i<j) {
  15.                 j--;
  16.             }
  17.             //再看左边，依次往右递增
  18.             while (temp>=arr[i]&&i<j) {
  19.                 i++;
  20.             }
  21.             //如果满足条件则交换
  22.             if (i<j) {
  23.                 t = arr[j];
  24.                 arr[j] = arr[i];
  25.                 arr[i] = t;
  26.             }
  28.         }
  29.         //最后将基准为与i和j相等位置的数字交换
  30.          arr[low] = arr[i];
  31.          arr[i] = temp;
  32.         //递归调用左半数组
  33.         quickSort(arr, low, j-1);
  34.         //递归调用右半数组
  35.         quickSort(arr, j+1, high);
  36.     }
  39.     public static void main(String[] args){
  40.         int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
  41.         quickSort(arr, 0, arr.length-1);
  42.         for (int i = 0; i < arr.length; i++) {
  43.             System.out.println(arr[i]);
  44.         }
  45.     }
  46. }

3)插入排序:
插入排序简单来说就是:每一轮通过比较找到数组中最大数,然后将它排到最后,在下一轮中排除本轮最大的数,找到剩余数组最大的数,放在剩余数组的末尾,:
对于少量元素的排序,插入排序是一种有小的算法,
代码展示:

  1. /**
  2.  * 插入排序
  3.  */
  4. public class InsertionSort {
  5.     //核心代码---开始
  6.     public static void sort(Comparable[] arr){
  8.         int n = arr.length;
  9.         for (int i = 0; i < n; i++) {
  10.             // 寻找元素 arr[i] 合适的插入位置
  11.            for( int j = i ; j > 0 ; j -- )
  12.                 if( arr[j].compareTo( arr[j-1] ) < 0 )
  13.                     swap( arr, j , j-1 );
  14.                 else
  15.                     break;
  16.         }
  17.     }
  18.     //核心代码---结束
  19.     private static void swap(Object[] arr, int i, int j) {
  20.         Object t = arr[i];
  21.         arr[i] = arr[j];
  22.         arr[j] = t;
  23.     }
  25.     public static void main(String[] args) {
  27.         int N = 20000;
  28.         Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
  29.         InsertionSort.sort(arr);
  30.         for( int i = 0 ; i < arr.length ; i ++ ){
  31.             System.out.print(arr[i]);
  32.             System.out.print(' ');
  33.         }
  34.     }
  36. }

查找算法:

(1)二分查找:
a.原理:1)如果待查序列为空,呢么就返回-1,并退出算法
2)如果不为空,就将听得中间元素与要查找的目标元素进行匹配,看他们是否相等
3)如果相等就返回中间索引并退出
4)如果中间元素大于目标元素,就将当前序列的前半部分作为新的待查序列,
5)如果中间元素小于目标元素,就将当前序列后半部分座位新的待查序列,重复第一步
b.二分查找之所以掳爱苏,是因为他匹配不成功的时候,每次都能排除剩余元素的一半元素,,而不像顺序查找呢样每次只能排除一个元素.

  1.  // 二分查找递归实现   
  2.         public static int binSearch(int srcArray[], int start, int end, int key) {   
  3.             int mid = (end - start) / 2 + start;   
  4.             if (srcArray[mid] == key) {   
  5.                 return mid;   
  6.             }   
  7.             if (start >= end) {   
  8.                 return -1;   
  9.             } else if (key > srcArray[mid]) {   
  10.                 return binSearch(srcArray, mid + 1, end, key);   
  11.             } else if (key < srcArray[mid]) {   
  12.                 return binSearch(srcArray, start, mid - 1, key);   
  13.             }   
  14.             return -1;   
  15.         }

数组元素去重算法:

(1)java的话可以利用set集合记性去重,将数组依此添加到set集合中,然后再将set集合转为数组(但是此种方法改变了原来数组的顺序)
(2)想要保持原数组顺序就是用有顺序不重复的链表哈希集合
(3)创建一个list集合,然后用contains方法判断是否在集合中存在,存在就不插入,不存在就插入

递归算法

递归实现斐波那契数列

  1.  * @author rico
  2.  */
  3. public class FibonacciSequence {
  5.     /**
  6.      * @description 经典递归法求解
  7.      * 
  8.      * 斐波那契数列如下：
  9.      * 
  10.      *  1,1,2,3,5,8,13,21,34,...
  11.      * 
  12.      * *那么，计算fib(5)时，需要计算1次fib(4),2次fib(3),3次fib(2)，调用了2次fib(1)*，即：
  13.      * 
  14.      *  fib(5) = fib(4) + fib(3)
  15.      *  
  16.      *  fib(4) = fib(3) + fib(2) ；fib(3) = fib(2) + fib(1)
  17.      *  
  18.      *  fib(3) = fib(2) + fib(1)
  19.      *  
  20.      * 这里面包含了许多重复计算，而实际上我们只需计算fib(4)、fib(3)、fib(2)和fib(1)各一次即可，
  21.      * 后面的optimizeFibonacci函数进行了优化，使时间复杂度降到了O(n).
  22.      * 
  23.      * @author rico
  24.      * @created 2017年5月10日 下午12:00:42
  25.      * @param n
  26.      * @return
  27.      */
  28.     public static int fibonacci(int n) {
  29.         if (n == 1 || n == 2) {     // 递归终止条件
  30.             return 1;       // 简单情景
  31.         }
  32.         return fibonacci(n - 1) + fibonacci(n - 2); // 相同重复逻辑，缩小问题的规模
  33.     }