归并排序和堆排序是十大排序算法里比较有意思的了，它们的时间复杂度不管是最好最坏还是平均都是O(nlog(n))。
归并排序
将长度为n的待排序数组看成n个有序长度为1的数组组成。两两合并得到长度为2的有序数组，再两两合并得到长度为4的有序数组，重复上述过程，直到整个数组有序。分为递归和迭代两种方法。递归的话就是二分，二分，二分，退出条件为左边界等于右边界，即一个元素时归并结果返回给两个元素的归并排序，俩个元素的归并排序返回给四个元素的归并。
稳定，利用空间换时间。时间复杂度，最好最坏平均都是O(nlog(n))。空间复杂度为O(n)。
// 递归
private void mergeSort(int[] nums, int left, int right){
// 结束条件为只有左右区间重合，只有一个数时，代表已经有序
if(left == right){
return;
}
// 找出他们的中位数
int mid = left + (right - left) / 2;
// 左半区间归并排序
mergeSort(nums, left, mid);
// 右半区间归并排序
mergeSort(nums, mid + 1, right);
// 将两有序区间合并，再次排序
merge(nums, left, mid, right);
}
//两有序区间合并，再次排序
private void merge(int[] nums, int left, int mid, int right){
// 构建一个辅助数组，用来保存排序后的结果
int[] tmp = new int[right - left + 1];
// 需要双指针，指向两个区间的位置。同时需要一个下标表示我们辅助数组的当前位置
int leftIndex = left;
int rightIndex = mid + 1;
int index = 0;
// 比较两有序区间元素大小，先将小的填充到我们的辅助数组里
while(leftIndex <= mid && rightIndex <= right){
if(nums[leftIndex] <= nums[rightIndex]){
tmp[index++] = nums[leftIndex++];
}else{
tmp[index++] = nums[rightIndex++];
}
}
// 两有序区间内有剩下元素，我们继续填充
while(leftIndex <= mid){
tmp[index++] = nums[leftIndex++];
}
while(rightIndex <= right){
tmp[index++] = nums[rightIndex++];
}
// 这时候辅助数组已经有序，我们把这些有序的元素放回我们的原数组
for(int i = 0; i < tmp.length; i++){
// 注意我们当前输入的数组的最左边left，不是从0开始。所以我们应该加上left，欢迎他们在原数组的位置
nums[i + left] = tmp[i];
}
}
堆排序
基础知识
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大的二叉树
堆是一种特殊的完全二叉树：每个结点的值都大于等于其左右孩子节点的值称为大顶堆， arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ；每个结点的值都小于等于其左右孩子节点的值，称为小顶堆。**arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 。
堆排序，使用数组构建的完全二叉树结构，满足堆的定义。
流程：整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。将数组元素，按照大顶堆方式来构建初始堆。这时候堆顶元素-即最大元素。交换堆顶元素和末尾元素，最大元素在末尾。同时我们调整堆，使它除去最后一个元素外仍然是大顶堆格式。依次重复。
其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度最好最坏平均都是O(nlog(n))。同时它是不稳定的。
private void heapSort(int[] nums){
int len = nums.length;
// 对于数组最后一个元素，由i = 2 * i + 1 和 i = 2 * i + 2
// 来说 (len - 1) = 2 * i + 2(或者1) 得出它的父节点下标索引 i = len 2 - 1;
// 给定一个父节点和末尾，我们从它来构建大顶堆。
// 从下到上，从右到左。
for(int i = len / 2 - 1; i >= 0; i--){
adjustHeap(nums, i, len);
}
// 然后从数组末尾开始，交换大顶堆顶点和末尾位置
for(int i = len - 1; i > 0; i--){
swap(nums, 0, i);
adjustHeap(nums, 0, i);
}
}
// 构建大顶堆，也可以用来调整堆数据是它成为大顶堆
private void adjustHeap(int[] nums, int parent, int len){
// 判断该父节点左子节点是否存在
int leftChildIndex = 2 * parent + 1;
int temp = nums[parent];
// 存在的话，我们把它和它子节点来变成一个大顶堆结构
while(leftChildIndex < len){
// 左子节点存在，看是否存在右子节点，同时两个子节点比较大小
if(leftChildIndex + 1 < len && nums[leftChildIndex] < nums[leftChildIndex + 1]){
// 使得索引指向子节点中比较大的元素
leftChildIndex++;
}
// 如果该父子节点满足大顶堆结构，结束，不用往下判断是因为我们的大顶堆构建是从后往前构建的。
// 当父子节点满足大顶堆结构，那么它的子节点、孙节点也是满足大顶堆结构的
if(nums[parent] > nums[leftChildIndex]){
break;
}
// 不满足时，调换元素位置
nums[parent] = nums[leftChildIndex];
// 将它的子节点作为父节点，再次判断
parent = leftIndex;
leftIndex = 2 * leftIndex + 1;
}
// 值赋予
nums[parent] = temp;
}
