归并排序效率很高，时间复杂度能达到O(nlogn)，但是依赖额外的内存空间，而且这种分而治之的思想很值得借鉴，很多场景都是通过简单的功能，组成了复杂的逻辑，所以只要找到可拆分的最小单元，就可以进行分而治之了。
快速排序
快速排序，和二分查找的思想很像，都是先将数据一份为二然后再逐个处理。快速排序也是最常见的排序算法的一种，面试被问到的概率还是比较大的。
主要步骤：
从数据中挑选出一个元素，称为 "基准"（pivot），一般选第一个元素或最后一个元素。
然后将数据中，所有比基准元素小的都放到基准元素左边，所有比基准元素大的都放到基准元素右边。
然后再将基准元素前面的数据集合和后面的数据集合重复执行前面两步骤。
动图演示
代码模板
/**
* 快速排序
* @param array 数组
* @param begin 0
* @param end array.length-1
*/
public static void quickSort(int[] array, int begin, int end) {
if (end <= begin) return;
int pivot = partition(array, begin, end);
quickSort(array, begin, pivot - 1);
quickSort(array, pivot + 1, end);
}
/**
* 分区
* @param array
* @param begin
* @param end
* @return
*/
public static int partition(int[] array, int begin, int end) {
// pivot: 标杆位置，counter: 小于pivot的元素的个数
int pivot = end, counter = begin;
for (int i = begin; i < end; i++) {
if (array[i] < array[pivot]) {
// 替换，将小于标杆位置的数据放到开始位置算起小于标杆数据的第counter位
int temp = array[counter];
array[counter] = array[i];
array[i] = temp;
counter++;
}
}
// 将标杆位置的数据移动到小于标杆位置数据的下一个位。
int temp = array[pivot];
array[pivot] = array[counter];
array[counter] = temp;
return counter;
}
快速排序总结
我找的快速排序的模板代码，是比较巧妙的，选择了最后一个元素作为了基准元素，然后小于基准元素的数量，就是基准元素应该在的位置。这样看起来是有点不好懂，但是看明白之后，就会觉得这个模板写的还是比较有意思的。
堆排序
堆排序其实是采用的堆这种数据结构来完成的排序，一般堆排序的方式都是采用的一种近似完全二叉树来实现的堆的方式完成排序，但是堆的实现方式其实不止有用二叉树的方式，其实还有斐波那契堆。
而根据排序的方向又分为大顶堆和小顶堆：
大顶堆：每个节点值都大于或等于子节点的值，在堆排序中用做升序排序。
小顶堆：每个节点值都小于或等于子节点的值，在堆排序中用做降序排序。
像Java中的PriorityQueue就是小顶堆。
主要步骤：
创建一个二叉堆，参数就是无序序列[0~n]；
把堆顶元素和堆尾元素互换；
调整后的堆顶元素，可能不是最大或最小的值，所以还需要调整此时堆顶元素的到正确的位置，这个调整位置的过程，主要是和二叉树的子元素的值对比后找到正确的位置。
重复步骤2、步骤3，直至整个序列的元素都在二叉堆的正确位置上了。
动图演示
模板代码
/**
* 堆排序
* @param array
*/
public static int[] heapSort(int[] array){
int size = array.length;
// 先将数据放入堆中
for (int i = (int) Math.floor(size / 2); i >= 0; i--) {
heapTopMove(array, i, size);
}
// 堆顶位置调整
for(int i = size - 1; i > 0; i--) {
swapNum(array, 0, i);
size--;
heapTopMove(array, 0,size);
}
return array;
}
/**
* 堆顶位置维护
* @param array
* @param i
* @param size
*/
public static void heapTopMove(int[] array,int i,int size){
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < size && array[left] > array[largest]) {
largest = left;
}
if (right < size && array[right] > array[largest]) {
largest = right;
}
if (largest != i) {
swapNum(array, i, largest);
heapTopMove(array, largest, size);
}
}
/**
* 比较交换
* @param array
* @param left
* @param right
*/
public static void swapNum(int[] array,int left,int right){
int temp = array[left];
array[left] = array[right];
array[right] = temp;
}
堆排序总结
