优先队列

定义：一种可以添加元素和删除最大/小元素的数据结构

难点：

如何高校地实现优先队列？使得删除最大/小元素能在常数时间内完成？

用二叉堆！

二叉堆是一组能用堆有序的完全二叉树表示的数组。数组的下标即元素在二叉树中的位置。
堆有序：父节点大于/小于子节点

怎么实现？

插入操作时，将元素插入到数组尾部，然后做上浮操作
删除最值时，先将数组最后一个元素与根元素（数组第一个元素）交换，删除根元素，再做下沉操作

效果：

对数级别的插入和删除最值

JAVA中用二叉小顶堆实现的优先队列

PriorityQueue （卧槽，这直译过来不就是优先队列吗……被自己蠢哭）

堆排序

如果用数组表示堆：

先从数组的中间位置开始，从后往前对每个元素做下沉操作，一遍下来数组就是一个堆有序数组
每次交换数组的首位元素后，将尾元素弹出（最值），然后对首元素做下沉操作。重复这个操作直到数组为空，即可完成对原数组的排序

选择排序

一次遍历，找到从当前位置开始到末尾的最小元素，与当前节点交换即可

插入排序

一次遍历，将当前节点放入从开头到当前节点范围内的正确的位置

希尔排序

1、h = a*n + 1；a和n可以自己设置
2、将数组分成h间隔的h个子数组，对子数组运用插入排序
3、如果h >1，h = h / a；
4、重复2
当完成h=1的排序后，排序完毕。h=1当然就是和插入排序一致

归并排序

0、当数组只含有一个元素，返回
1、将数组的左半边排序
2、将数组的右半边排序
3、将左半边与右半边原地归并

显而易见用递归
原地归并就是从两个已排序数组排序。

快速排序

1、将基准元素（头元素）放入到正确的位置（左边的元素都小于等于它，右边的元素都大于它）
i. 变量i指向最左边下标，变量j指向最右边下标，变量x保存基准元素
ii. a[j]>x，j– a[j]<x，a[i]=a[j]
iii. a[i]<x，i++ a[i]>x，a[j]=a[i]
重复ii和iii，直到i >= j
a[i]=x

2、分治，递归左子数组和右子数组

显而易见用递归