- 加深下算法和数据结构能力，记录一下，Typora真好用，里面大多数代码都挺容易看懂，进似于伪代码了属于是，大多数都没套class，用的时候要写上。
认识时间复杂度
- 常数时间的操作
数组取数，读数等操作，其常数操作固定，与数据量无关（加减乘除等等都是常数操作）。
int a=arr[i];
- 不是常数操作
int b=list.get(i);
(链表找i位置的值，在内存位置不定，需要一个一个跳，与数据量有关)
-
时间复杂度
-
选择排序(SelectionSort)
在一个数组0 ~ N-1内，先找一个最小值，遍历一次将其放置在0的位置上（最小的叔与0位置的数做交换）->>再从1 ~ N-1的位置上遍历一遍，找到最小的数，将其放置在1的位置上->>…一次次压缩数据量寻找最小的数进行排序。
-
进行的常数操作次数
第一次时，对每个数遍历，是N次操作->>进行比较，N次操作->>最后进行一次swap（交换）
第二次时，对每个数遍历，是N-1次操作->>进行比较，N-1次操作->>最后进行一次swap（交换）
…
总计：
遍历进行的操作： N+N-1+N-2+N-3+… 比较进行的操作： N+N-1+N-2+N-3+… Swap进行的操作： N次 合计：=aN2+bN+c
快速排序代码示例：
public static void selectionSort(int[] arr){ for(int i=-;i<arr.length-1;i++){ int minIndex=i; for(int j=i+1;j<arr.length;j++){ minIndex=arr[j]<arr[minIndex] ? j:minIndex; } swap(arr,i,minIndex); } } public static void swap(int[] arr,int i,int j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; }
时间复杂度的表示：在常数操作数量集的表达式中，不要低阶项，忽略高阶项的系数。
则选择排序时间复杂度为O(N2),当算法时间复杂度表示一致时，只能对比常数项，最好的方法是实际跑代码测试。
评价一个算法流程的好坏，先看时间复杂度的指标，然后再分析不同的数据样本下的实际运行书简，也就是“常数项时间”。
-
-
冒泡排序(BubbleSort)
在一个数组0 ~ N-1内，对其相邻两个数进行大小比较，大的或者小的按需交换，一次遍历，确定末尾数，迭次减少所需遍历长度，交换排序。时间复杂度依旧是O(N2)。
冒泡排序代码示例：
public static void bubbleSort(int[] arr){ for(int e=arr.length-1;e>0;e--){ //大范围 for(int i=0;i<e;i++){ if(arr[i]>arr[i+1]){ swap(arr,i,i-1); } } } } //交换arr的i和j位置上的值 public static void swap(int[] arr,int i,int j){ arr[i]=a[i] ^ a[j]; arr[j]=a[i] ^ a[j]; arr[i]=a[i] ^ a[j]; }知识补充：异或运算，java中的异或运算符“ ^ ”，对两个数进行比较，相同输出0,不同输出1，在数据处理时，运用二进制，每个位比较，可理解为，无进位相加。
? 异或运算的性质：
-
0 ^ N=N N ^ N=0
-
满足交换律，结合律 。a ^ b=b ^ a , a ^ b ^ c=a^(b ^ c)
-
多个数进行异或操作，与顺序无关。
代码示范：
int a=12; int b=20; //进行a,b的值的交换操作 a=a^b;//a=a^b b=20 b=a^b;//a=a^b b=a^b^b=a a=a^b;//a=a^b^a=b //绝！注意，此操作仅限于该数据在内存中不同位置！
-
-
**例题：1.一个数组，里面的奇数次位置都是一个数，其余的数都在偶数位，如何分离。2.一个数组，里面的奇数次位置都是两种数，其余的数都在偶数位，如何分离。
public static void printOddTimes1(int[] arr){
int eor=0;
for(int cur:arr){
eor^=cur;
}
System.out.println(eor);
}//第一问
public static void printOddTimes1(int[] arr){
int eor=0;
for(int cur:arr){
eor^=cur;
}
//eor=a^b,eor!=0，eor必有一个位置上是1（二进制）
int rightOne=eor & (~eor+1);//提取最右侧的1
int onlyOne=0;
for(int cur:arr){
if((onlyOne&rightOne)==0){
onlyOne^=cur;
}
}
System.out.println(onlyOne+" "+(eor^onlyOne));
}
//位运算
? 插入排序（InsertionSort）：
? 时间复杂度：O(N2)
? tips:时间复杂度按最差情况估计
? **维护一个有序区，将数据一个一个插入到有序区的适当位置，直到整个数组都有序。**即每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
? 一个数组，对其规定一个插入位置进行比大小，交换，每次比完确定该区间有序且该区间前面的数也有序，以此到最后一位。
? 代码示范：
public static void insertionSort(int[] arr){
for(int i=1;i<arr.length;i++){
for(int j=i-1;j>=0 && arr[j]>arr[j+1];j--){
swap(arr,j,j+1);
}
}
}
public static void swap(int[] arr,int i,int j){
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
?二分法
? 二分法又可以被称为二分查找，它描述了在有序集合中搜索特定值的过程。广义的二分查找是将问题的规模尽可能的缩小到原有的一半。
? 时间复杂度：O(log2N)=O(logN)
-
在一个有序数组中，找某个数是否存在。
? 通过一个x，判断其与需要找的数的大小，在有序数组中向该方向中值再取值比较。
-
在一个有序数组中，找>=某个数最左侧的位置。
? 先取数组最中间，比较是否满足>=。满足则标记，向小于的那一侧取中间，比较，若不满足>=则标记x，向大于的右侧与第一次标记中取中值，直到结束。
-
局部最小值问题
? 在一个无序数组arr中，任何两个相邻的数不相等，求局部最小。（局部最小定义:在0位置上与1位置比较最小的，在N-1位置上与N-2位置上比较最小的，在i上比较i-1与i与i+1最小的，i要小于i-1与i+1，这几个最小的就是该位置的局部最小。），在arr数组中，只找一个局部最小，且时间复杂度需要满足O(N)。
? 箭头趋势是大小趋势，M点是中点，若有一部分是递减，而M-1到M是递增，那么在0~M区域必有一个局部最小，反之右边也一样。在进行找中值二分。二分不一定需要有序
优化一个流程，要考虑数据状况以及问题需要，这道题都满足。
-
对数器
? 对数器可以说是验证算法是否正确的一种方式。尤其是在笔试的时候，用贪心算法写出的程序，暂时无法用数学公式严格推导证明，只能通过大量的数据集验证算法的正确性。而大量的数据集当中要包括各种情况，各个方面都要考虑到，对我们自己来说，有时会考虑不周，而且又是在时间紧迫的情况下。所以对数器就派上了用场。
? 假设有一种方法a（想测试正确与否优秀的算法）和一种方法b（容易想的暴力算法），编写一个随机样本产生器进行数据提供。分别将数据带入方法a和方法b，产出两种结果，第一次可以让随机样本产生器产生较小的数据，对比a,b结果，若a有错，进行修改，在产生大量的数据，若a,b结果一样，那么方法a就无措可用。
假设，我们的插入排序为算法a：
public static void insertionSort(int[] arr){ for(int i=1;i<arr.length;i++){ for(int j=i-1;j>=0 && arr[j]>arr[j+1];j--){ swap(arr,j,j+1); } } } public static void swap(int[] arr,int i,int j){ arr[i]=arr[i]^arr[j]; arr[j]=arr[i]^arr[j]; arr[i]=arr[i]^arr[j]; }而系统提供的排序作为方法b（系统算法是正确的）：
public static void comparator(int[] arr){ Arrays.sort(arr); }对数器算法代码：
//随机生成数 public static int[] generateRandomArray(int maxSize,int maxValue){ //Math.random() ->[0,1) 所有小数，等概率返回一个 //Math.random()*N ->[0，N)所有小数，等概率返回一个 //(int)(Math.random()*N) ->[0,N-1)所有整数，等概率返回一个 int[] arr=new int[(int)((maxSize+1)*Math.random())];//长度随机 for(int i=0;i<arr.length;i++){ arr[i]=(int)((maxValue+1)*Mathrandom())-(int)(maxValue*Math.random()); } return arr; } //对数器 public static void main(String[] args){ int testTime=500000; int maxSize=100; int maxValue=100; bollean succeed=true; for(int i=0;i<testTime;i++){ int[]arr1=generateRandomArray(maxSize,maxValue); int[]arr2=copyArray(arr1); insertionSort(arr1); comparator(arr2); if(!isEqual(arr1,arr2)){ succeed=false; break; } } System.out.println(succeed ? "Nice":"fuck"); }