完成算法按最差表现需要执行的常数操作的次数，只留最高阶项并且去掉系数
二、冒泡排序、选择排序和插入排序最简单的三个排序算法，时间复杂度O(N^2)，空间复杂度O(1)
冒泡排序：public static void bubbleSort(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = a.length - 1; j > i; j--) {
if (a[j] < a[j - 1]) {
swap(a, j - 1, j);
}
}
}
}
选择排序：
public static void selectSort(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] > a[j]) {
swap(a, i, j);
}
}
}
}
插入排序：
相当于打牌摸牌的过程，比选择和冒泡稍快一些
public static int[] insertSort(int[] a){
for (int i = 0; i < a.length; i++){
for (int j = i; j > 0 && a[j-1] > a[j]; j--){
swap(a,j-1,j);
}
}
return a;
}
三、swap函数与亦或
swap函数
正常的swap函数：
public static void swap(int[] arr, int a, int b) {
int c = arr[a];
arr[a] = arr[b];
arr[b] = c;
}
利用亦或，可以不是用额外空间实现swap函数（前提保证a和b不能指向同一内存块，即a != b）：
public static void swap(int[] arr, int a, int b) {
array[a] = array[a] ^ array[b];
array[b] = array[a] ^ array[b];
array[a] = array[a] ^ array[b];
}
亦或
亦或是相同为0不同为1，两个二进制数亦或可以认为是无进位的加法。
亦或的性质：
1）0 ^ N=N; N ^ N=0
2) 满足交换律和结合律： a ^ b=b^ a; a ^ b ^ c=a ^ (b ^ c)
3) 一组数据亦或，与亦或的顺序无关
相关例题：
例1、一个数组，其中一个数字出现了奇数次其余的数字都出现了偶数次，求这个出现了奇数次的数字。
public static int method1(int[] arraylist){
int eor = 0;
//利用亦或的性质，将数组中的数亦或一遍即可
for (int i=0;i< arraylist.length;i++) {
eor ^= arraylist[i];
}
return eor;
}
例2、一个数组，其中两个数字出现了奇数次其余数字都出现了偶数次，求这两个出现了奇数次的数字。
public static int[] method2(int[] arraylist){
int eor = 0;
for (int i=0;i< arraylist.length;i++) {
eor ^= arraylist[i];
}
int rightone = 0;
//取出为1的最右边的一位
rightone = eor&(~eor+1);
int onlyone = 0;
for (int i=0;i< arraylist.length;i++) {
if ((arraylist[i] & rightone) == 0) {
onlyone ^= arraylist[i];
}
}
int[] b = new int[2];
b[0] = onlyone;
b[1] = eor^onlyone;
return b;
}
四、二分法
例1、一个有序数组，确定一个数是否存在数组中，若存在，返回数组下标，若不存在返回-1
public static int bisectionMethod1(int a[], int b){
int front = 0;
int end = a.length-1;
int mid = (front + end)/2;
while (front <= end){
if(a[mid] == b){
return mid;
}else if(a[mid] < b) {
front = mid+1;
mid = (front + end)/2;
}else {
end = mid-1;
mid = (front + end)/2;
}
}
return -1;
}
例2、一个有序数组，确定一个数是否存在数组中，若存在，返回这个数第一个存在的下标，若不存在返回-1
public static int bisectionMethod2(int a[], int b){
int front = 0;
int end = a.length-1;
int mid = (front + end)/2;
int tag = -1;
while (front <= end){
if(a[mid] > b){
end = mid-1;
mid = (front + end)/2;
}else if(a[mid] < b){
front = mid+1;
mid = (front + end)/2;
}else {
tag = mid;
end = mid-1;
mid = (front + end)/2;
}
}
return tag;
}
例3、求局部最小值，一个无序数组，相邻两个数必不相等，求此数组中一个比相邻的数都小的数，若存在返回下标，若不存在返回-1,要求时间复杂度在O(logN)以内（不一定有序数组才能用二分）
public static int bisectionMethod3(int a[]){
int front = 0;
int end = a.length-1;
int mid = (front + end)/2;
if(a.length == 1){
return 0;
}
if(a[front] < a[front+1]){
return front;
}else if(a[end] < a[end-1]){
return end;
}else {
while(front <= end){
if(a[mid] > a[front]){
end = mid -1;
mid = (front + end)/2;
}else if(a[mid] > a[end]){
front = mid +1;
mid = (front + end)/2;
}else {
if(a[mid] > a[mid-1]){
end = mid-1;
mid = (front + end)/2;
}
else if(a[mid] > a[mid+1]) {
front = mid + 1;
mid = (front + end) / 2;
}else {
return mid;
}
}
}
}
return -1;
}
五、 master公式
若一个递归算法可以表示为：
其中，T(N)为母问题的数据规模，T(N/b)为子问题的数据规模，a为子问题的执行次数，O(N^d)为剩余执行部分的时间复杂度。
则此算法的时间复杂度可直接计算
1） if log(b,a) > d -> 时间复杂度为 O(N^log(b,a))
2） if log(b,a) = d -> 时间复杂度为O((N^d)*logN)
3） if log(b,a) < d -> 时间复杂度为O(N^d)
流程：先上数组前一半和后一半分别有序，然后两半归并（递归）
归并排序是外排序（需要借助外部数组的排序算法）
public static void mergeSort(int[] arr, int front, int end){
if(end == front){
return ;
}
int mid = front + ((end - front)>>1);
mergeSort(arr, front, mid);
mergeSort(arr, mid + 1, end);
merge(arr, front,mid , end);
}
public static void merge(int[] arr, int front,int mid, int end){
int[] help = new int[end - front + 1];
int p = front;
int q = mid + 1;
int i = 0;
while (p <= mid && q <= end){
//用三元运算符代替if else
help[i++] = arr[p] > arr[q] ? arr[q++] : arr[p++];
}
while (p <= mid){
help[i++] = arr[p++];
}
while (q <= end){
help[i++] = arr[q++];
}
for(i = 0; i < help.length; i++){
arr[front + i] = help[i];
}
}
归并排序符合master公式，计算时间复杂度为O(NlogN)，额外空间复杂度为O(N)
归并排序之所以可以将时间复杂度降到O(NlogN)是因为它没有浪费比较过程，每一次比较会传递到下一次归并中去。而O(N^2)的排序浪费了N次比较机会才能搞定一个数，浪费了大量的比较次数。
归并排序的应用：
例1、小和问题：一个数组中每个位置的数字左边比它小的数字的和叫小和，求这些小和的总和
public static int smallSum(int[] arr){
if(arr == null || arr.length<2){
return 0;
}
return mergeSort2(arr, 0, arr.length-1);
}
public static int mergeSort2(int arr[], int front, int end){
if(front == end){
return 0;
}
int mid = front + ((end - front)>>1);
return mergeSort2(arr, front, mid) + mergeSort2(arr, mid + 1, end) + merge2(arr,front, mid, end);
}
public static int merge2(int[] arr, int front,int mid, int end){
int[] help = new int[end - front + 1];
int p = front;
int q = mid + 1;
int i = 0;
int sum = 0;
while (p <= mid && q <= end){
if (arr[p] < arr[q]){
sum += arr[p] * (end - q + 1);
help[i++] = arr[p++];
}else {
help[i++] = arr[q++];
}
}
while (p <= mid){
help[i++] = arr[p++];
}
while (q <= end){
help[i++] = arr[q++];
}
for (i = 0; i < help.length; i++){
arr[front+i] = help[i];
}
return sum;
}
例2、逆序对问题：一个数组中，若一个数字比他右边的大，这一对数字就叫逆序对，求所有的逆序对，和小和问题一个原理。
七、快速排序 1、 荷兰国旗问题 1） 指定一个num，使数组左边的数都小于等于num，数组右边的数都大于num，要求时间复杂度O(N)，空间复杂度O(1)步骤：数组左区指针最开始是-1，将遍历指针从0往右遍历，若此位置的数小于等于num，将其和左区右边的数互换，左区指针加一；若此位置的数大于num，则继续往下遍历。
public static void partition1(int[] arr, int num){
int L = -1;
for (int i = 0; i < arr.length; i++){
if(arr[i] <= num){
swap2(arr, ++L, i);
}
}
}
2） 指定一个num，使数组左边的数都小于num，数组中间的数都等于num，数组右边的数都大于num，要求时间复杂度O(N)，空间复杂度O(1)
1.0 小于区和等于区动：
public static void partition2(int[] arr, int num){
int L = -1;
int M = -1;
for (int i = 0; i < arr.length; i++){
if(arr[i] < num){
swap2(arr, ++L, ++M);
swap2(arr, L, i);
}else if(arr[i] == num){
swap2(arr, ++M, i);
}
}
}
2.0：小于区和大于区动
public static void partition2_2(int[] arr, int num){
int L = -1;
int R = arr.length;
int i = 0;
while (i num){
swap2(arr, --R, i);
}else {
i++;
}
}
}
2、快速排序算法
1.0：用数组的最后一位做划分值num，让数组左侧都为小于等于num的数，右侧都为大于num的数（最后一位不动），然后让最后一位和右侧第一位的数交换，将数组分成左右两侧，然后分别用两侧的最后一位做划分值递归调用，最终排好序。
2.0：利用荷兰国旗问题，将等于划分值的数都放在中间，然后递归调用两侧的数组。
2.0会比1.0稍快，但是两个算法的时间复杂度都是O(N^2),空间复杂度为O(N)，因为当数组本来就有序时，是最差情况，每一次递归只能解决一个数。
3.0：在数组中随机取一个数，将它与数组最尾端的数交换，然后用这个数作为划分值进行partition，这样所有的情况都为等概率事件，将这些概率事件求一个期望，最终算法时间复杂度为O(NlogN)，空间复杂度为O(logN)
public static void quickSort(int[] arr, int front, int end){
if(end > front){
swap2(arr, front + (int)(Math.random()*(end - front +1)), end);
int[] a = partition(arr, front, end);
quickSort(arr, 0, a[0]);
quickSort(arr, a[1], end);
}
}
public static int[] partition(int[] arr, int front, int end){
int L = front - 1;
int R = end;
int i = front;
while (i arr[end]){
swap2(arr, --R, i);
}else {
i++;
}
}
swap2(arr, end, R);
return new int[]{L, R+1};
}
八、堆和堆排序
1、完全二叉树：从左到右依次编满的二叉树叫做完全二叉树
2、大根堆和小根堆
大根堆：所有父节点都比子节点大的完全二叉树叫做大根堆
小根堆：所有父节点都比子节点小的完全二叉树叫做小根堆
一个数组从零开始的连续一段可以表示成一个堆，节点i的左孩子是2i+1，右孩子是2i+2，父节点是(i-1)/2。
4、heapinsert一个空的数组或一个大根堆，向数组内添加一个数，通过heapinsert操作使数组继续保持为大根堆。
步骤：将该位置的数和父节点比较，若大于父节点则和父节点交换，直到其不大于父节点或到0位置，时间复杂度O(logN)
//index位置的数是否需要向上移动而保持数组大根堆状态
public static void heapInsert(int[] arr, int index) {
while(arr[index] > arr[(index-1)/2]) {
swap2(arr, index, (index-1)/2);
index = (index-1)/2;
}
}
5、heapify：
一个大根堆，要求把它的最大值（即0位置的数）从堆中拿出来，剩下的数仍然保持大根堆。
步骤：将数组末位的数复制到0位置，然后将其和左右孩子的最大值比，若比孩子小则和孩子交换，直到其不比孩子小或其没有孩子为止，时间复杂度O(logN)
//从index位置开始往下做heapify
public static void heapIfy(int[] arr, int index, int heapsize) {
int left = 2*index+1;
//index下方还有孩子的时候
while(left < heapsize) {
//左孩子和右孩子哪个大
int largest = left + 1 < heapsize && arr[left] < arr[left+1] ? left+1 : left;
//父节点和最大孩子哪个大
largest = arr[largest] < arr[index] ? index : largest;
if(largest == index) {
break;
}
swap2(arr, largest, index);
index = largest;
left = 2*index+1;
}
}
如果将一个大根堆数组中的某一位置的值改掉，只需将该位置的数向上做一次heapinsert再向下做一次heapify即可将数组继续保持大根堆结构。
6、堆排序：步骤：初始heapsize为0，然后一个一个数做heapinsert，heapsize++，将数组变为大根堆，然后让数组首尾位置的数交换，heapsize–，做heapify操作将数组再变成大根堆，然后循环做heapify直到heapsize为0排序完成。时间复杂度O(NlogN),额外空间复杂度O(1)
//堆排序
public static void heapSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
int heapsize = 0;
//O(N)
while(heapsize < arr.length) {
//O(logN)
heapInsert(arr, heapsize++);
}
//O(N)
while(heapsize > 0) {
O(1)
swap2(arr, 0, --heapsize);
//O(logN)
heapIfy(arr, 0, heapsize);
}
}
更快的方法：
Heapinsert步骤用heapify替换，即通过从最下层结点往前依次调用heapify来一次性将整个数组变成大根堆。此方法的时间复杂度为O(N)比heapinsert的O(logN)好
改进后：
public static void heapSort2(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
for(int i = arr.length-1; i>=0;i--) {
heapIfy(arr, i, arr.length);
}
int heapsize = arr.length;
//O(N)
while(heapsize > 0) {
O(1)
swap2(arr, 0, --heapsize);
//O(logN)
heapIfy(arr, 0, heapsize);
}
}
7、堆的拓展题：
一个数组几乎有序，几乎有序是指数组中的数从无序到有序移动的距离不超过k，k是一个相对于数组长度很小的数，用最小的时间复杂度排序这个数组。
*注：
1、扩容：在往小根堆里添加数字的时候，小根堆每次扩容是成倍扩的，添加N个数扩容代价是O(N（最多N次拷贝）logN（最多扩容logN次）)，平均到每个数的扩容代价是O(logN)
2、系统内置堆和手写堆的区别：内置堆实际上是一个黑盒，我们只能通过add和poll函数和它进行交互，但当有其他需求时（如需要将堆中的某一位的数改变，让其继续保持为堆），内置堆的调整效率不如手写堆，这时就需要用手写堆
步骤：准备一个小根堆（在java中优先级队列PriorityQueue底层实现就是一个小根堆），将前数组中前k+1个数加入到小根堆中，由于数字移动的距离不超过k，所以前k+1个数中一定有最小值，因此将小根堆中堆顶的数弹出放在0位置上，然后将k+2位置的数加入到小根堆中，继续弹出堆顶的数即为1位置的数，一直循环到数组末尾，时间复杂度为O(Nlogk)。
九、比较器实现按不同标准排序。
比较器规则，两个参数A和B，若A要排在前面，返回一个负数，若B要排在前面，返回一个正数，若谁排前面无所谓，返回0。
应用，可以将优先级队列改为大根堆，或指定较为复杂的比较策略
public static class NodeComparator implements Comparator十、非比较排序{ @Override public int compare(Node o1, Node o2) { return o1.weight - o2.weight; } } PriorityQueue nodesqueue = new PriorityQueue (new EdgeComparator());
前面的排序算法都是基于比较的排序，理论时间复杂度下限是O(NlogN)，而非比较排序是可以根据数据状况进行的特殊的排序算法，可以突破O(NlogN)来到O(N)。
1、计数排序若一组数据中的数都在j-k区间内，那么我们可以准备一个大小为k-j+1的数组，然后遍历数组，将j~k每个个数出现的次数记录在准备的数组中，然后将记录数组还原回原数组完成排序，时间复杂度为O(N+k-j)，额外空间复杂度为O(k-j),但是这种算法只在k-j比较小的情况下适用，否则空间代价会很高。
2、基数排序准备十个桶（队列）0-9，将数字按照个位数字依次入桶，然后按照先进先出原则出桶，然后将数字按照十位数字依次入桶，以此类推，数组中为数最多的数字有多少位就循环几次，最后出桶排序完成。
十一、排序总结 1、 排序算法的稳定性：相同值的相对次序在排序完后不变。基础类型数据排序稳定性没用，但是对对象等复杂类型数据的排序有用。
| 算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | O(N^2) | O(1) | 不稳定 |
| 冒泡排序 | O(N^2) | O(1) | 不稳定 |
| 插入排序 | O(N^2) | O(1) | 稳定 |
| 归并排序 | O(NlogN) | O(N) | 稳定 |
| 快速排序（3.0） | O(NlogN) | O(logN) | 不稳定 |
| 堆排序 | O(NlogN) | O(1) | 不稳定 |
| 桶排序 | O(NlogN) | O(1) | 不稳定 |
| 桶排序（计数和基数排序） | 稳定 |
排序算法优先使用快速排序，因为快速排序的常数项经过实验证明是最小的，所以理论上是最快的；若有空间要求优先使用堆排序；若有稳定性要求优先使用归并排序；根据数据状况可以考虑使用桶排序。
注：
1）基于比较的排序时间复杂度最小O(NlogN)
2）基于比较的排序时间复杂度O(NlogN)，空间复杂度小于O(N)还稳定的排序算法目前不存在。
上图的第五点，相当于快排序，为01标准的partition，性质和快排序一样，想做到稳定很难。
2、 工程上对排序的改进
1） 充分利用O(NlogN)和O(N^2)排序的各自优势，如在小样本量（<=60）时使用插入排序，可以利用插入排序常数项小的优势，大样本量使用快速排序，可以利用快速排序时间复杂度低的优势。归并排序同理。
2） 稳定性考虑
