理解时间复杂度：

一个有序数组A，另一个无序数组B，请打印B中的所有不在A中的数，A数

组长度为N，B数组长度为M。

算法1：对于数组B中的每一个数，都在A中通过遍历的方式找一下；     

算法2：对于数组B中的每一个数，都在A中通过二分的方式找一下；

算法3：先把数组B排序，然后用类似外排的方式打印所有不在A中出现的数；

时间复杂度分别为： O(M*N)， O(M*log(N))，O(M*logM)+O(M+N)  （算法3：排序O(M*logM)，再加上两个有序数组各遍历一遍O(M+N)）

递归的算法的时间复杂度：

递归算法满足 master公式 ：T(N) = aT(N/b)+T(N^d)

其中N是问题的样本量，a是拆分成子问题的数量，N/b是子问题的样本量，N^d是拆分后常规操作的复杂度。

log(b,a)  > d ——> 时间复杂度: O(N^log(b,a))

log(b,a)  = d ——> 时间复杂度: O(N^d*logN)

log(b,a)  < d ——> 时间复杂度: O(N^d))

以归并排序为例，T(N)=2T(N/2)+T(N)，a=2，b=2，d=1；log(1,1)=1,时间复杂度O(N*logN)

排序算法：

1.冒泡排序: 时间复杂度O(N^2),空间复杂度O(1)

相邻两个数比较，大的放在后面。每次遍历把最大的数找出放在最后。

for(int end=arr.length-1; end > 0; end--){            for(int i=0;i
     
       arr[i+1]){                    swap(arr, i,i+1);                }            }        }
     

 

2.选择排序: 时间复杂度O(N^2),空间复杂度O(1)

选出当前最小的数，遍历数组，遇到更小的交换。每次遍历把最小的数找出放在最前面。

for (int cur = 0; cur

 

3.插入排序: 时间复杂度O(N^2)，最好情况O(N) 。空间复杂度O(1)

把当前数插入到前面的有序队列中(类似于玩扑克牌,每摸一张牌，排一次序)。(当原数组越接近所排顺序的时候，时间复杂度越低)

for (int i = 1; i < arr.length; i++) {            while (i>0 && arr[i]

 

4.归并排序：时间复杂度O(N*logN),空间复杂度O(N)

public static void mergeSort(int[] arr, int l, int r) {        if(l==r) {           return;        }        int mid = (l+r)>>1;        mergeSort(arr,l,mid);     //将左半部分排序        mergeSort(arr,mid+1,r); //将右半部分排序        merge(arr,l,mid,r);       //归并排好序的两部分    }        private static void merge(int[] arr, int l, int m,int r) {        int[] help = new int[r - l + 1];        int i = 0;        int p1 = l;        int p2 = m + 1;        //将两个队列依次插入到辅助数组,直到一个队列结束        while (p1 <= m && p2 <= r) {            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];        }        //右边队列已到末尾,将左边队列全部插入        while (p1 <= m) {            help[i++] = arr[p1++];        }        //左边队列已到末尾,将右边队列剩余元素全部插入        while (p2 <= r) {            help[i++] = arr[p2++];        }        //辅助数组是已排好序,拷贝到原数组        while(l<=r) {            arr[r--] = help[--i];        }    }

 

5. 快速排序：平均时间复杂度O(N*logN)，最差情况O(N^2)。空间复杂度O(logN)

public static void quickSort(int[] arr, int l, int r){        if(l>=r){            return;        }        //将数组分为3部分:小于区域,等于区域,大于区域        int[] point = partition(arr,l,r);        //将小于区域和大于区域排序        quickSort(arr,l,point[0]);        quickSort(arr,point[1],r);    }    private static int[] partition(int[] arr, int l, int r) {        //数组中随意取一个值,用来排序        int num = arr[l+(r-l+1)*(int) Math.random()];        int less = l-1;        int more = r+1;        while (l < more){            if (arr[l] < num){                swap(arr,l++,++less);            }else if(arr[l] == num){               l++;            }else {                swap(arr,l,--more);            }        }        return new int[]{less,more};    }

 

6. 堆排序：时间复杂度O(N*logN)，空间复杂度O(1)

 堆结构：把数组想象成完全二叉树的结构，完全二叉树一个节点下标为i，它的左右节点下标分别为2i+1,2i+2，它的父节点下标为(i-1)/2。大(小)根堆就是一棵完全二叉树中，任意一颗子树的最大(小)值都是这颗子树的头部。先建堆，再下沉构成了堆排序，建堆的过程时间复杂度为O(N)

public static void heapSort(int[] arr){        if(arr == null || arr.length<2){            return;        }        //先建堆,再下沉        heapBuild(arr);        heapSink(arr);    }    private static void heapBuild(int[] arr) {        for (int i = 0; i < arr.length; i++) {            //建堆时,要求满足非叶子节点小于父节点,否则交换位置            while (arr[i] > arr[(i - 1) / 2]) {                swap(arr,i,(i - 1) / 2);                i = (i - 1) / 2;            }        }    }    private static void heapSink(int[] arr) {        //下沉时每次把大根堆头部和数组末尾交换位置,heapSize-1        for (int size = arr.length-1; size>0; size--){            swap(arr,0,size);            int index = 0;            int left = 2*index+1;            while (left < size){                int bigger = left+1
     
       arr[left] ? left+1 : left;                if(arr[index] >= arr[bigger]){                   break;                }                swap(arr,index,bigger);                index = bigger;                left = 2*index+1;            }        }    }