1.认识复杂度与排序算法
-
复杂度：认识时间复杂度就是看进行了多少次常数操作。（什么是常数操作？赋值、加减乘除运算等都是。调用API操作就不是如list.get(i)。）
- 时间复杂度：在常数操作的数量级表达式中不要低阶项，只要最高阶项，并忽略系数。
- 空间复杂度：系统需要额外空间去保存变量。
-
选择排序：
-
概念：一个n长度的数组，从0-n-1找最小的数，然后和第一个数交换，第一个数不动。再从1-n-1找最小的数，然后和第二个数交换，第二个数不动，依次查找。
-
时间复杂度分析：若时间复杂度指标相同，可以实际测试来看那个好。O(n^2)
-
空间复杂度分析：看代码，minIndex每次进入循环都重新申请，完了又释放，所以复杂度为O（1）
-
代码框架：
public static void selectionSort(int[] arr){ int len = arr.length(); if(arr == null || len < 2) return; for(int i=0;i<len-1;i++){ int minIndex = i; for(int j=i+1;j<len;j++){ minIndex = arr[j] < arr[minIndex] ? j : minIndex; } swap(arr,i,minIndex);//把找到的最小值和第一个数交换 } }
-
-
冒泡排序：
-
概念：相邻两个比较，大的往后排，第一轮找到最大的，第二轮找到次大的，依次.....
-
时间复杂度分析：O(n^2)
-
空间复杂度分析：对arr数组中的每个数进行比较，申请了空间为n的数组，则O(n)
-
代码框架：
public static void bubbleSort(int[] arr){ if(arr == null || arr.length() < 2) return; for(int i=0;i<n-1;i++){ for(int j=0;j<n-i-1;j++){ if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]); } } }
-
-
异或^
-
概念：相同的为0，不同的为1。也可理解为无进位相加，1+0=1，1+1=2，不进位后，1+1=0。
-
性质：
- a^a = 0，a^0 = a
- 满足交换律、结合律
-
举例运算：
public static void swap(int a,int b){ a = a^b; b = a^b; a = a^b; //完成交换 }
- 例子：可以求一个数组中出现奇数次的数。（全部异或）
-
-
插入排序
-
概念：一个数组a[n]，①先看0-0区间，已经排序；②看0-1区间，如果a[1]<a[0]，就交换两个数，排好序；③看0-2区间，a[2]依次与前面的那个数比较。
-
时间复杂度分析：最差情况下，如【1，2，3，4，5，6，7】每一次都要与前面交换i次，因此表达式为1+2+3+...+n，则时间复杂度为O(n2)。最好情况下，如【5，4，3，2，1】，每一次都只需要看前面一眼，因此为O(n)。所以插入排序时间复杂度为O（n2）
-
代码框架：
public static void insertSort(int[] arr){ if(arr == null || arr.length() < 2) 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,j+1); } } }
-
-
二分查找
-
时间复杂度：O(logN)，每一次都砍一半。
-
代码框架：
public static int twoSort(int[] arr,int i,int j){ int midIndex = (i+j)/2; if(arr[midIndex] == num) return midIndex; if(arr[midIndex] > num) twoSort(arr,midIndex+1,n); else twoSort(arr,0,midIndex-1); return midIndex; }
-
2.堆
-
上调：
-
应用：堆的初始化、向堆中添加一个元素
-
过程：
-
代码：
#include <iostream> #include <vector> using namespace std; vector<int> heap;//存储堆 vector<int> index; /**上调 **参数：位置i **/ void shiptUp(int i){ if(i==1) return ; int flag=0; //标记是否需要交换 while(i!=1 && flag==0){ if(heap[i] < heap[i/2]) swap(heap[i],heap[i/2]); else flag=1; i/=2; } } int main(){ //题目给出一个数组，要建成小顶堆 int n; for(int i=1;i<=n;i++){ cin>>heap[i]; shiftUp(i); } return 0; }
-
-
下调
-
应用：用某数替换最小值/最大值（根）。
-
过程：
-
代码：
//大顶堆 #include <iostream> #include <vector> using namespace std; vector<int> heap;//存储堆 vector<int> index; /**上调 **参数：位置i **/ void shiftDown(int i){ int flag=0,t; while(i*2<n&&flag==0){//如果有左孩子，左孩子比根大，则要考虑根左孩子换 if(heap[i]<heap[i*2]) t=i*2; else t=i; if(i*2+1<n){//如果有右孩子，右孩子比左孩子还大，则要根右孩子换 if(heap[t]<heap[i*2+1]) t=i*2+1; } //如果发现t不是自己 if(i!=t){ swap(heap[i],heap[t]); i=t; }else{ flag=1; //不用换 } } } int main(){ int n; shiftDown(0); //根节点位置为0 return 0; }注：小顶堆只需要将heap[i] < heap[i2] 改为heap[i] >heap[i2]（包含右孩子比较的）即可。
-