排序

对数器：
易写不出错的流程 + 随机生成的样例

插入排序

将一个新的数插入到一个有序数组中进行比较

public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}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);}}}

时间复杂度 O(n^2) 但存在好情况

插入，选择，冒泡，时O(n^2) 空O(1)
归并，快速，堆， 时O(N*log(N)) 空O(N)， O(log(N))， O(1)

归并排序

分治的思想 与 master公式

是一个递归过程（利用栈，先进后出）（即在方法中调用自身）

先自己调用自己将左边部分排好，再自己调用自己将右边部分排好
之后同意外排出来排好

	public static 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 m, int r) {int[] help = new int[r - l + 1];int i = 0;int p1 = l;int p2 = m + 1;while (p1 <= m && p2 <= r) {help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while (p1 <= m) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[l + i] = help[i];}}

时间复杂度分析: T(N) = T(N/2)+T(N/2)+O(N) 左+右+merge = 2*T(N/2)+O(N)

master公式 T() =a * T(n/b) + O(N^d)
logb(a)>d O(N^logb(a))
d>logb(a) O(N^d)
d=logb(a) O(N^d*logN)

a>>>1 高位补0的右移
a>>1 高位补符号位的值

求最小和问题 每一个左边数比它小的数累加 (逆序对问题)
4 1 3 5 0 6 1 3 4 (1+ ) 0 5 6

• 暴力解
• 归并排序方法改进 ：每一个左边数比它小的数累加 即为 每一个数乘右边比他大的个数 可在merge中 一段区域之间的比较只累加一次，之后与其它区域比较时不会累加

	public static int smallSum(int[] arr) {if (arr == null || arr.length < 2) {return;}return mergeSort(arr, 0, arr.length - 1);}public static int mergeSort(int[] arr, int l, int r) {if (l == r) {return;}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 m, int r) {int[] help = new int[r-l+1];int i=0;int p1=l,p2=m+1;int sum=0;while (p1 <= m && p2 <= r) {if(arr[p1]<arr[p2]){sum+=arr[p1]*(r-p2+1);help[i++]=arr[p1++];}else{help[i++]=arr[p2++];}}while (p1 <= m) {help[i++] = arr[p1++];}while (p2 <= r) {help[i++] = arr[p2++];}for (i = 0; i < help.length; i++) {arr[l + i] = help[i];}return sum;}

辅助空间：help数组 O(n)

快速排序

引入：荷兰国旗问题 要求空间复杂度O(1),时间O(N)

经典快排：将数组的最后一个数作为划分依据
改进：随机快排
核心代码：

	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) {swap(arr, l + (int) (Math.random() * (r - l + 1)), r);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]) {swap(arr, ++less, l++);} else if (arr[l] > arr[r]) {swap(arr, --more, l);} else {l++;}}swap(arr, more, r);return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

复杂度分析：时间 T(N) = T(N/2)+T(N/2)+O(N)
空间（随机快排） 断点的空间占用，即p[]

工程上要将递归函数改为非递归版本。

堆排序

堆的结构：完全二叉树（实际落地的是一个数组结构，这是脑补出来的）
i
2i+1 左 2i+2 右
(i-1)/2 父

大根堆 : 在这颗完全二叉树中任何一个子树的最大值都是根节点
小根堆 ：在这颗完全二叉树中任何一个子树的最小值都是根节点

• 建立大根堆：
  2 1 3 6 0 4
  0 1 2 3 4 5

	public static void heapSort(int[] arr){if(arr==null||arr.length<2){return;}for(int i=0;i<arr.length;i++){heapInsert(arr,i);}}public static void heapInsert(int[] arr,int index){while(arr[intdex]>arr[(index-1)/2]){  //(0-1)/2=0 swap(arr,index,(index-1)/2);index=(index-1)/2;}}

复杂度分析：
时间： 每次heapInsert每次比较的总次数就是完全二叉树的高度，即O（log N）。 而整个建立过程是log 1 + log 2 + log 3 + …+ log N-1 即 O（N）

• heapify 已经形成好的大根堆，其中某值发生变化，将其再调整为大根堆
  找到他的左右节点，最大的与其比较，找出最大的（更直观的理解，换为三个数的最大值）

public static void heapify(int[] arr,int index,int heapSize){int left = 2*index+1;while(left<heapSize){int largest = left + 1 <heapSize && arr[left+1]>arr[left]?left+1:left;largest = arr[largest]>arr[index]?largest:index;if(largest==index){break;}swap(arr,index,largest);index=largest;left=2*index+1;}}

优先级队列就是堆

例子：不断给你数，不断让你求中位数

已经形成的堆，怎样弹出堆顶（即堆结构的减小） ： 最后一个数与堆顶的值交换，heapSize-1

一个大根堆，一个小根堆，将给定的数进行比较（）进入堆，若两个堆的数量相差大于1，则将数量多的堆的堆顶弹出进入另一个堆

堆排序：
先将数组变成大根堆，将头部与末尾进行交换，heapSize-1，进行heapify，重复过程

public static void heapSort(int[] arr){if(arr==null||arr.length<2){return;}for(int i=0;i<arr.length;i++){heapInsert(arr,i);}int heapSize = arr.length;swap(arr,0,--heapSize);while(heapSize>0){heapify(arr,0,heapSize);swap(arr,0,--heapSize);}}public static void heapInsert(int[] arr,int index){while(arr[intdex]>arr[(index-1)/2]){  //(0-1)/2=0 swap(arr,index,(index-1)/2);index=(index-1)/2;}}public static void heapify(int[] arr,int index,int heapSize){int left = 2*index+1;while(left<heapSize){int largest = left + 1 <heapSize && arr[left+1]>arr[left]?left+1:left;largest = arr[largest]>arr[index]?largest:index;if(largest==index){break;}swap(arr,index,largest);index=largest;left=2*index+1;}}

排序的稳定性：排完序后仍能保持原来的次序

• 可以实现：冒泡（相等的情况下也交换就不是了），插入，归并，桶，计数，基数

• 不可实现：选择，快速，堆

• 意义 ：排序之前的信息很重要，不能删去

有关排序问题的补充：

1. 归并排序的额外空间复杂度可以变为O（1），但是非常难，不需要掌握，可以搜“归并排序 内部缓存法”
2. 快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
3. 有一道题目，是奇数放在数组左边，偶数放在数组右边，空O（1），时O（N），还要求原始的相对次序不变，碰到这种问题，看可以怼面试官。

工程中的综合排序算法

若给定数组很长，先判断给定类型（基础类型用快排，自己定义的比较器用归并排序，原因是稳定性），若很短用插入排序（小样本常数量很低，插入排序很快（<60））
递归的部分一旦小于60，直接插排

比较器

p  s  c  xxx implements Comparator<T>{public int compare(T1  ,  T2){return xxx;}
}Array.sort(arr,new xxx);PriorityQueue<T> heap = new PriorityQueue<>(new xxx);
heap.add(T3);
...TreeMap<>红黑树

return
负数 第一个数放在前面
正数 后面的数放在前面
零 一样大
（升序 return T1-T2 降序 return T2-T1）

桶排序，计数排序，基数排序

1. 非基于比较的排序，与被排序的样本的实际数据状况黑有关系，所以实际中并不经常使用。
2. 时间复杂度O(N)，额外空间复杂度O(N)
3. 稳定的排序

补充问题：给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序
N个数，准备N+1个桶，遍历求出最大值和最小值，分别放在最前最后两个桶中，后各个桶平均装入数，根据鸽笼原理，一定一个桶是空的，（只存bool是否进入数，min，max）·，找它左边离他最近的非空桶的最大值和它当前非空桶的最小值
为什么不直接找空桶，19 空 30 49，即答案不一定来自空桶左右，上述做法只是否定非空桶内部的情况

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;}boolean[] hasNum = new boolean[len + 1];int[] maxs = new int[len + 1];int[] mins = new int[len + 1];int bid = 0;for (int i = 0; i < len; i++) {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;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;
}
public static int bucket(long num, long len, long min, long max) {return (int) ((num - min) * len / (max - min));
}