此文章看B站左神视频所总结的。
左神视频传送门
目录
一、时间复杂度
二、空间复杂度
三、选择排序
四、冒泡排序
五、异或
六、插入排序
七、二分法
八、对数器
时间复杂度
时间复杂度: 时间复杂度是估计常数操作的一个指标。
常数操作：每次都是固定的时间，与样本数量无关。
常数操作的例子：
如数组操作 int a = al[i];
不是常数操作的例子：
如链表操作list.get(i);
这又是为什么呢？
因为他们的储存方式是不一样的，数组分配的是连续的空间，然而链表分配的空间是不连续的，数组可以根据偏移量直接计算出所需的地址，链表则计算不出来。
举例一个排序进行分析，每次都要检查各个数据的值，比较N次，每次新一次交换，将第一个换成最小的数据。
最终的和为一个等差数列，可以看作是aN^2+bN+c（a,b,c为常数）最后可知:
算法复杂度为O（n^2）
当连个算法复杂度一样时，可以简单的利用电脑跑一下来判断哪个算法好。
空间复杂度
如果只需要几个变量，则空间复杂度就是O(1)的。
如果算法执行的临时空间是不随 n 的值而变化为O(1)。
1、选择排序思想，每次选出数组中最小的数据，并将前面的换成最小的数据。
输入数组为a[]
第一次就是比较所有的数据，最小的放在数组第一个。
第二次就是比较a[1]到最后，最小的放在a[1]。
后面操作同上。
选择排序法
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] a = {1,4,3,2,7,2};
selectSort(a);
System.out.println(Arrays.toString(a));
}
public static void selectSort(int[] a){
if (a == null || a.length<2){ //排除无用的数组
return;
}
for(int i=0;ia[j]?j:temp; //得到最小值的下标
}
swap(a,i,temp);
}
}
public static void swap(int[] arr,int i,int temp){ //交换数值，并不破坏数组
int tem = arr[temp];
arr[temp] = arr[i];
arr[i] = tem;
}
}
2、冒泡思想，每次比较数组中的两个数据，并把较小的放前面。一轮下来，最后面的就是最大的了。重复几轮就排序完毕了。
冒泡排序法
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr={90,2,6,7,5,4,3};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr){
if(arr==null || arr.length<2){ //排除无效的数组
return;
}
for (int i = 0; i < arr.length-1; i++) { //每一次都循环都会把最后一位变成最小的数值
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j]>arr[j+1]){
swap(arr,j,j+1); //冒泡排序将大的数据放在后面
}
}
}
}
//抖机灵的写法，平时不要用
public static void swap(int[] arr,int a, int b){ //使用或运算去解决问题，但是会存在弊端，要防止数据的地址相同
arr[a] = arr[a]^arr[b];
arr[b] = arr[a]^arr[b];
arr[a] = arr[a]^arr[b];
}
}
异或运算
补充：异或运算（不进位加法运算）
性质1：异或自己为0，异或0为本身
性质2：满足交换律和结合律
交换两个数值的代码
a = a ^ b
b = a ^ b
a = a ^ b
或者
a=a-b
b=b+a
a=b-a
尽量就用平常的再定义一个变量来交换吧，上面的方法也有弊端。
异或运算的算法题目中的应用
题目1：一个数组其中的一个数字只出现了一次，其他的数字都出现了两次，如何找到出现了一次的数字？
题目2一个数组其中有两个数字只出现了一次，其他的数字都出现了两次，如何找到出现了一次的数字？
题目2代码
public class Two {
public static void main(String[] args) {
int[] arr = {1,1,3,4,4,6,6,7,7,99};
find(arr);
}
public static void find(int[] arr){
int xor = 0;
for (int i = 0; i < arr.length; i++) {
xor ^= arr[i];
} //xor=3^9
int temp = xor&(~xor+1); //得到最右边的1，temp=2
int a = 0;
for (int i = 0; i < arr.length; i++) {
if ((arr[i] & temp)!=0){ //得到第2位为1的部分
a^=arr[i];
}
}
System.out.println(a); //打印单独数字
System.out.println(a^xor);
}
}
题目1、利用性质1，从头到尾异或一下就可以了。
题目2、 利用性质1，从头到尾异或一下得c,c为两个不同的数字的异或的结果。提取出来c最右边的1，对数组进行遍历判断相同的位置是否存在1（通过&上一步的结果），如果存在则进行新一轮的异或，会得到两个数字中的一个。
插入排序
从0位置开始排序
第一次对0位置排序
第二次对0到1位置排序
第三次对0到2位置排序
第四次0到3…
代码如下：
import java.util.Arrays;
public class InsertSort {
public static void main(String[] args) {
int[] arr = {0,3,2,1,5,7,45,9,89};
insertSort(arr);
}
public static void insertSort(int[] arr){
if(arr.length<2 || arr==null){ //排除无用数组
return;
}
for (int i = 1; i < arr.length; i++) { //相当于是挪动一个数字加入已经排序好的数组
for (int j = i-1; j >= 0; j--) { //将新加入的数字与之前排序好的数组进行遍历
if(arr[j] > arr[j+1]){
swap(arr,j+1,j);
}
}
}
System.out.println(Arrays.toString(arr));
}
public static void swap(int[]arr,int a,int b){ //交换数字
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
二分法
1.在一个有序数组中找某个数是否存在
先找到中点的数与x是什么关系，x比中点大就可以砍掉一半在右边继续二分。小于就是在左边继续二分。时间复杂度为O(log2n)
2.在一个有序数组中，找>=某个数最左侧的位置
可用二分法，继续取中间一个数如果>=某个数，则在这个数的左侧继续二分直到找到。
对数器
假设自己现在有两个方法，一个效率高的方法a，一个原始的穷举一定正确的方法b。为确保方法a正确，我们就可以随机的生成数据，并对比两个方法的答案，在验证很多数据后答案依然一样，就可以认为方法a是正确的。
