基数排序
定义0-9十个桶，先排序个数，在排序十位，依次向下（桶就是二维数组）
按照个位先排一次
个位已经有序了，桶内遵循先进先出
没有十位放到0里
取出
百位
这样排序就完成了。放进取出几次，取决于最大数一共有几位。
时间复杂度
按照个位：挨个遍历，挨个取出----O(n)
最大数k位 复杂度O(kn)
堆排序
1.利用完全二叉树构建大顶堆
2.堆顶元素和堆底元素进行交换，除堆底元素，剩余元素继续构建大顶堆。
3.不断重复2，直到排序完成
完全二叉树：要求数据必须从上到下，从左到右的顺序
这就是一个完全二叉树
什么是大顶堆：父节点的值大于或等于其左右节点的值
堆顶元素：arr[0] 堆底元素 arr[arr.length-1]
0的左右孩子 1 2 1的左右孩子 3 4 2的左右孩子 5 6
所有得出结论 arr[i]的左孩子是 arr[2i+1] arr[i]的右孩子是 arr[2i+2] arr[i]的父节点是 arr[(i-1)/2]
arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]
如何构建大顶堆？？？
从后往前检测每一个节点是否符合大顶堆，符合检测前一个，不符合对其进行维护，让其符合大顶堆
1.定义parent游标指向该节点
2.定义parent的左孩子 child=2*parent+1，判断有没有左孩子，没有则符合大顶堆，如果有左孩子，判断有没有右孩子。有右孩子，左右孩子进行比较，child指向左右孩子中最大的值
3.父子节点进行比较
4.父节点大，符合大顶堆，继续向前检测
5.子节点的值大，父子节点进行交换，交换完成，parent指向child,child指向左右孩子最大值,继续比较parent和child，直到parent的值大，或者child为空
6.重复以上操作
形成大顶堆，堆顶堆底交换，7不参与构建了
然后继续形成大顶堆，继续交换就好了
时间复杂度
1层 1个数据
2层 2
3层 4
4层 8
k层 2^(k-1)
2^k -1 =n
k=log2n
维护一个节点的时间复杂度O(logn)
维护N个节点 O(Nlogn)
初始化一个堆时间复杂度O(n)
整个堆排序时间复杂度 O（nlogn）
归并排序
合并有序序列
s1 s2不断比较谁小谁进去
归并排序： 先拆分在合并
拆分：从中间位置拆开，数据分左右两部分，继续拆分，直到拆成一个一个停止
然后在比较合并
时间复杂度：
第一次拆分 2个数组
2 4
3 8
k x
x=2^k k=log2x
合并 合并一次会把数据都遍历一边
时间复杂度 O(logn)*O(n)=O(nlogn)
