时间复杂度

什么是时间复杂度？
       答:算法中基本操作的执行次数。

异或运算

       异或运算，即无进位相加，满足交换律和结合律。（不适应于浮点型！）
       两个二进制数进行异或运算，对应位置的数，相同为0，不同为1。
       异或运算语法:a^a =0; a^0=a;
小技巧:swap函数可以用"异或运算"实现
Code：

//局限性在于:使用异或运算来交换两个数时，需要的是不同的引用，否则无效。且不适用于浮点型。
public  static void swap(int[] arr,int i,int j){//此处用到了结合律和交换律//a^a=0;  a^0=a;arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}

冒泡排序

时间复杂度为:O(N^2),额外空间复杂度为:O(1),可以实现稳定性!
稳定性:数组在排序前后值相同的数的相对顺序不变。
Code：

public static void bubbleSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int e = arr.length - 1; e>0; e--){//最外层的for循环，用来表示，我们要将数放到最后一个位置，倒数第二个位置，...for(int i = 0; i<e; i++){/*是否会越界？答:必然不会越界!首先 e = arr.length - 1;，其次i<e，也就是说，i小于n-1,那么i+1就必然不越界。*/if(arr[i]>arr[i+1]){swap(arr,i,i+1);}}}
}public static void swap(int[] arr,int i,int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

插入排序

时间复杂度为:O(N^2),额外空间复杂度为O(1),可以实现稳定性;
因为只有待插入元素的前一个元素大于待插入元素时，二者才进行交换，小于等于都不交换，因此相对位置不会改变，可以实现稳定性。
我们默认数组0位置上的元素是有序的，之后将数组剩余的(n-1)个元素插入到有序序列中，最终使得数组有序。
Code：

public static void insertSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = 1; i<arr.length; i++){//i从1开始，代表待插入元素的索引;for(int j = i-1; j>=0 && arr[j]>arr[j+1]; j--){swap(arr,j,j+1);}}
}

选择排序

时间复杂度为:O(N^2),额外空间复杂度为O(1),不可以实现稳定性
"快些选一堆"，都是不稳定的排序.
选择数组中最小的元素与数组0位置的元素进行交换，选择数组中第二小的数与数组1位置上的元素进行交换，如此往复直到整个数组有序。
Code：

public static void selectSort(int[] arr){if(arr == null || arr.length < 2){return;}for(int i = 0; i<arr.length-1; i++){//之所以，这里的i<arr.length-1;，是为了避免数组越界，因为下面的j = i+1;int minIndex =  i;for(int j = i+1; j<arr.length; j++){minIndex = arr[j] > arr[minIndex] ? minIndex : j;}swap(arr,minIndex,i);}
}

随机快排

常数项小,时间复杂度为O(N*logN)
分析:
①选取划分值:p; 花费O(1)
②划分 <p(小于区) =p(等于区) >p(大于区) ，也就是熟悉的partition过程，O(N)
③左侧 <p 和 右侧 >p，分别去递归，当划分值选的不好时，时间复杂度会升高，最差为O(N^2)
随机选择划分值可以在概率上避免数组本身的规律，也就尽可能避免了时间复杂度过高的情况。
空间复杂度为:O(logN),需要记录断点的位置。当额外空间复杂度为O(logN)时，快排做不到稳定性！
Code：

public static void quickSort(int[] arr){if(arr == null || arr.length < 2){return;}quickSort(arr,0,arr.length - 1);
}
public static  void quickSort(int[] arr,int l,int r){if(l < r){//首先我们随机选择划分值，之后将划分值与数组r位置的元素进行交换;/*此处，Math.random()函数返回的是浮点型的[0,1)的数；假设，l = 5,r = 10;则(r-l+1) = 6;于是 6 * [0,1) = [0,5];之后再用 l + [0,5] 就生成了 l到 r中的随机数;*/swap(arr,l+(int)((r-l+1)*Math.random()),r);//得到划分值以后，在整个范围内进行partition过程,//返回等于区的两个边界；int[] p = partition(arr,l,r);//对左右两端的数据进行递归。quickSort(arr,l,p[0]-1);quickSort(arr,p[1]+1,r);}
}public static int[] partition(int[] arr,int l,int r){int less = l-1;//初始化小于区的边界int more = r;//初始化大于区的边界while(l < more){if(arr[l] < arr[r]){//若当前数小于划分值时，则将小于区的下一个数与当前数进行交换，同时l++;swap(arr,++less,l++);}else if(arr[l] > arr[r]){//若当前数大于划分值时，则将大于区的前一个数与当前数进行交换，同时l不变，继续判断l位置上的数是大于or小于or等于划分值。swap(arr,--more,l);}else{//若当前数与划分值相等，则l++;l++;}}
//当执行到此处时，l==more,此时数组中为 <p  =p  >p p，需要将r处的p与大于区的第一个元素进行交换;swap(arr,more,r);return new int[]{less+1,more};//最后返回等于区的左右边界。
}

荷兰国旗问题

Code：

public class Code_NetherlandsFlag{public static int[] partition(int[] arr,int l,int r,int p){int less = l-1;int more = r+1;while(l<more){if(arr[l]<p){swap(arr,++less,l++);}else if(arr[l]>p){swap(arr,--more,l);}else{l++;}}return new int[]{less+1,more-1};}}

二分查找

二分查找的前提是:数组有序
题目:获取存在于数组B中但不存在于数组A中的元素
右移(位运算)：相当于除2操作，且比除快，但有局限性。
Code：

public static List<Integer> getAllNotIncluded(int[] A,int[] B){List<Integer> res = new ArrayList<Integer>();for(int i=0; i<B.length; i++){int l = 0;int r = A.length - 1;boolean contains = false;while(l<=r){int mid = l + ((r-l)>>1); //右移相当于除2，这样取中间值时，不会溢出。if(A[mid] > B[i]){r = mid - 1;}else if(A[mid] < B[i]){l = mid + 1;}else{contains = true;break;}}if(!contains){res.add(B[i]);}}return res;
}

归并排序

任何递归行为都可以改为非递归。
递归是系统帮你压栈保存了函数的信息，我们可以自己建立栈来保存信息。
时间复杂度为:O(N*logN),额外空间复杂度为:O(N)(因为merge的过程需要数组的辅助),可以实现稳定性
Code：

public staic void mergeSort(int[] arr){if(arr == null || arr.length < 2){return;}mergeSort(arr,0,arr.length-1);
}
public static void mergeSort(int[] arr,int l,int r){if(l==r){//当拆分到只剩一个元素时，停止拆分。return;}int mid = l + ((r-l)>>1);mergeSort(arr,l,mid);mergeSort(arr,mid+1,r);merge(arr,l,mid,r);//合并操作
}
public static void  merge(int[] arr,int l,int mid,int r){//合并过程需要一个辅助数组int[] help = new int[r-l+1];int p1 = l;//指针1int p2 = mid + 1;//指针2int i = 0;while(p1<=mid && p2<=r){//两个指针分别指向两个合并组的初始位置，//二者相比较，小的先放入数组中help[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];}while(p1<=mid){help[i++] = arr[p1++];}while(p2<=r){help[i++] = arr[p2++];}//最后将help数组中的元素拷贝到原数组中。for(i=0; i<help.length;i++){arr[l+i] = help[i];}
}

归并排序的扩展–小和问题、逆序对

什么是小和问题?
   每个位置的左边比它小的数都累加起来的和称为–小和。
什么是逆序对？
   逆序:若前面的数大于后面的数，则称为逆序;
小和问题Code：

public static int mergeSort(int[] arr){if(arr == null || arr.length < 2){return 0;}return mergeSort(arr,0,arr.length - 1);
}
public static int mergeSort(int[] arr){if(l == r){return 0;}int mid = l + ((r - l)>>1);return mergeSort(arr,l,mid) + mergeSort(arr,mid+1,r) + merge(arr,l,mid,r);
}
public static int merge(int[] arr,int l,int mid,int r){int[] help = new int[r - l + 1];int res = 0;int p1 = l;int p2 = mid + 1;int i = 0;while(p1<=mid && p2<=r){//此处，在合并时，比较左右两组的数据，若arr[p1]小于arr[p2]，则就存在(r-p2+1)个arr[p1]这样的小和。res += arr[p1]<arr[p2] ? (r - p2 +1) * arr[p1] : 0;help[i++] = arr[p1]<arr[p2] ? arr[p1++] : arr[p2];}while(p1<=mid){help[i++] = arr[p1++];}while(p2<=r){help[i++] = arr[p2++];}//最后将help数组中的元素拷贝到原数组中。for(i=0; i<help.length;i++){arr[l+i] = help[i];}
}

逆序对Code：

public static int mergeSort(int[] arr){if(arr == null || arr.length < 2){return 0;}return mergeSort(arr,0,arr.length-1);
}
public static  int mergeSort(int[] arr,int l,int r){if(l == r){return 0;}int mid = l + ((r - l)>>1);return mergeSort(arr,l,mid) + mergeSort(arr,mid + 1,r) + merge(arr,l,mid,r); 
}
public static int merge(int[] arr,int l,int mid,int r){int[] help = new int[r-l+1];int count = 0;int p1 = l;int p2 = mid + 1;int i = 0;while(p1<=mid && p2<=r){//此处，在合并时，比较两组的数据，由于都是升序排列，因此逆序对需要如下这样计算。count += arr[p1] > arr[p2] ? (mid - p1 + 1) : 0;help[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while(p1<=mid){help[i++] = arr[p1++];}while(p2<=r){help[i++] = arr[p2++];}//最后将help数组中的元素拷贝到原数组中。for(i=0; i<help.length;i++){arr[l+i] = help[i];}
}

堆排序

时间复杂度为:O(N*logN),额外空间复杂度为:O(1),不可以实现稳定性!
常数项大，堆在逻辑上是一棵完全二叉树，有如下公式:
index位置的父节点索引为:(index - 1)/2
index位置的左孩子索引为:(2 * index) + 1
index位置的右孩子索引为:(2 * index) + 2
大根堆:任何一个节点都是其下面那棵树中值最大的点。
堆排序的流程:首先将数组的所有位置建立大根堆(heapInsert过程),之后将大根堆的堆顶元素和数组最后一个位置的元素进行交换，在交换之后的堆不能保证依旧是大根堆，则需要重新调整为大根堆(heapify过程),之后继续交换堆顶元素和数组中倒数第二个元素，如此往复，直到数组有序为止。
Code：

public static void heapSort(int[] arr){if(arr == null || arr.length < 2){return;}//首先将数组建立为大根堆for(int i = 0; i<arr.length; i++){heapInsert(arr,i);}//借助变量size来确定堆的大小int size = arr.length;//之后交换堆顶元素和数组最末元素;swap(arr,0,--size);//在交换之后，重新调整为大根堆，如此往复直到排序完成。while(size > 0){//调整为大根堆，此时index为0，进行heapify下沉过程.heapify(arr,0,size);//调整完之后，交换swap(arr,0,--size);}
}
public static void heapify(int[] arr,int index,int size){int left = (2 * index) + 1;while(left < size){//若index位置存在左孩子//largest变量用来标识index位置的元素和其左右孩子中最大的那个元素的索引;int largest = left + 1 < size && arr[left+1] > arr[left] ? left +1 : left;largest = arr[largest] > arr[index] ? largest : index;//若比较来比较去，发现最大的元素的索引依旧是index,则不用调整;if(largest == index){break;}//若比较完之后，最大元素的索引不是index位置，则二者交换swap(arr,index,largest);//之后，更新index位置,继续进行下沉操作。index = largest;//同时更新left，进行下一轮循环。left = (2 * index) + 1;}
}public static void heapInsert(int[] arr,int index){/*从index位置开始，请你往上瞅，与其父比较，若比其父大，则二者交换，之后继续往上瞅，与其父比较，若依旧大于其父，则继续交换，直到不比其父大 或者 index为0时，停止;*/while(arr[index] > arr[(index - 1)/2]){swap(arr,index,(index - 1)/2);index = (index - 1)/2;}
}

基于桶排序思想的题目

非基于比较的排序，对数据的位数和范围有限制，可以优化，但是解决不了。
题目:在一个无序数组中，求如果有序之后，相邻元素之间最大差值。
思路:假设数组有N个数，我们需要准备N+1个桶，之后遍历数组，将数组中最小值min放在第一个桶中，数组中最大值max放在最后一个桶，之后将range = (max - min)/(N+1)均分，使得每个桶存放一定范围的数值;由于我们有N+1个桶，而只有N个数，再加上第一个和最后一个桶都有元素，则必然存在一个空桶位于第一个桶和最后一个桶之间，此时我们考虑，空桶左边第一个非空桶的最大值与空桶右边第一个非空桶的最小值，在排序之后一定是相邻的元素，且二者的差值必然 >= range,(其实每个桶内也有相邻的数据，但是它们之间的差值 <= range，由于我们要求最大差值，所以就不考虑这种情况),因此我们不用管桶内部的相邻数据，我们只用考虑桶与桶之间的相邻数，因此我们只用获取每个桶的最大值max与最小值min；每个桶只找它前面离它最近的非空桶，最大差值不一定来自于空桶两侧的非空桶，有可能来自于两个相邻的非空桶.
为什么要加入空桶?为什么要用N+1个桶？
    答:加入空桶，只是为了说明，我们不用考虑桶内相邻数据的差值，只是为了排除这种情况。
Code：

public static int maxGap(int[] nums){if(nums == null || nums.length < 2){return 0;}int len = nums.length;int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;//首选获取数组中最大值和最小值for(int i = 0; i<len; i++){min = Math.min(min,nums[i]);max = Math.max(max,nums[i]);}//若最大值 == 最小值，则表示数组中为同一个数，则直接返回if(min == max){return 0;}//之后，创建三个数组//1.表明每一个桶是否为空？boolean[] hasNum = new boolean[len + 1];//2.int[] maxs = new int[len + 1];//3.int[] mins = new int[len + 1];int bid = 0;//用来标识桶号for(int i=0; i<len; i++){//拿到数组中的每一个数，通过max与min等参数算出这个数应该进几号桶。//同时更新对应桶的最大值、最小值以及桶的状态。bid = bucket(nums[i],len,min,max);mins[bid] = hasNum[bid]?Math.min(mins[bid],nums[i]):nums[i];maxs[bid] = hasNum[bid]?Math.max(maxs[bid],nums[i]):nums[i];//此时该桶不为空.hasNum[bid] = true;}int res = 0;//上一个桶的最大值，初始值默认为0号桶的最大值int lastMax = maxs[0];int i = 1;for(;i<=len;i++){if(hasNum[i]){//后一个桶的最小值减去前一个桶的最大值,即为所求相邻元素的差值。res = Math.max(res,mins[i] - lastMax);lastMax = maxs[i];}}return res;	
}
//根据给定的min和max,算出每个数值num对应的桶号;
public static int bucket(long num,long len,long min,long max){return (int) ((num - min)*len/(max-min));
}

目前就更新到这里，若觉得文章存在问题，欢迎斧正~~