堆排序、快速排序和归并排序是所有排序中最重要的三个排序，也是难度最大的三个排序；所以本文单独拿这三个排序来讲解
目录
一、堆排序
1.建堆
2.堆排序
二、快速排序
1.思想解析
2.Hoare版找基准
3.挖坑法找基准
4.快速排序的优化
5.快速排序非递归
三、归并排序
1.归并思路
2.代码展示及步骤
3.代码分析
4.归并排序非递归
5.使用归并排序解决海量数据
一、堆排序
所谓堆排序，就是在堆的基础上进行排序，那么如何建堆，就是堆排序的重点。
堆排序核心思想：
1.建堆：排升序建大根堆，排降序建小根堆
2.在建好堆后，每次堆顶元素和最后一个位置的元素交换
3.每交换一次，就进行向下调整操作，使其满足堆的性质
4.交换后，最后一个位置向前走一步
1.建堆
堆有两种，大根堆和小根堆。
（1）排升序，建立大根堆
（2）排降序，建立小根堆
再利用大根堆或者小根堆进行排序
（1）建堆
我们建堆使用向下调整的方式，从最后一棵子树开始。每一棵子树都需要进行向下调整。
向下调整创建大根堆
核心：先将一维数组以层序遍历的方式创建成一棵完全二叉树，然后从最后一棵子树（最后一个父亲结点）开始，向下调整（从父亲到最后一个孩子）。每一轮结束，父亲结点减一。
回忆父亲结点和孩子结点的关系：假设知道父亲结点的下标为i，则左孩子的下标为：(2*i)-1；如果知道孩子结点的下标（左右都可）为i，则父亲结点为：（i-1）/2。
通过图示理解大根堆的向下调整创建:
有该数组：{27,15,19,18,28,34,65,49,25,37}
得到一棵逻辑上的完全二叉树：
然后从最后一棵子树开始向下调整：
调整的步骤：
（1）左右孩子比较，找出孩子大的下标（2）大孩子与父亲结点比较，大于父亲结点则交换（3）父亲结点下标走到孩子位置，孩子再等于新的下标
下面是调整的过程：
第一轮：调整最后一棵子树，p的开始位置为4
c=2*9+1=18，上面标错了
第二轮：p--，走到3的位置
c=2*7+1=15，上面标错了
第三轮：p--，走到2的位置
c=2*6+1=13，上面标错了
第四轮：p--，走到1的位置
第五轮：p--，走到0的位置
上面就是堆调整的全过程，我们总结一下：
p代表需要调整的子树，每调整完一轮，p--，直到p调整完；而在每一轮的调整中，交换完一小轮，p就要向下走，c也要继续往下走，直到不满足条件。
下面是建立大根堆的代码：
public void create(int[] arr) {
//从最后一棵子树向下调整
for (int parent = (arr.length -1-1)/2; parent >= 0 ; parent--) {
siftDown(arr,parent,arr.length);
}
}
/**
* 向下调整
*/
public void siftDown(int[] arr,int parent,int len) {
int child = parent*2 + 1;
while(child arr[child]) {
child = child + 1;
}
if(arr[child] > arr[parent]) {
swap(arr,child,parent);
parent = child;
child = parent*2 + 1;
}else {
break;
}
}
}
public void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
下面是建立小根堆的代码：
public void createminHeap() {
for (int parent = (usedSize-1)/2; parent >= 0 ; parent--) {
siftDown2(parent,usedSize);
}
}
private void siftDown2(int parent,int end) {
int child = parent*2+1;//找到左孩子下标
//循环结束，说明一棵子树调整完成
while (child elem[child+1]) {
child++;
}
//2.比较父亲结点和大孩子结点
if(elem[parent] > elem[child]) {
swap(parent,child);
parent = child;
child = parent*2+1;//找到左孩子下标
}else {
break;//满足则结束循环
}
}
}
public void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
2.堆排序
在学会如何建堆之后，才能进行堆排序操作，堆排序操作是比较简单的
思想：每次堆顶元素和最后一个元素交换，交换完进行一次向下调整，每次过后最后一个元素向前走
大根堆可以保证堆顶元素是最大的，每次和最后一个位置交换；不断交换，就会形成升序。
堆排序部分代码：
public void headSort(int[] arr) {
//1.排升序，建大根堆
create(arr);
int end = arr.length - 1;
while(end > 0) {
//2.每次交换堆顶和最后一个元素
swap(arr,0,end);
//3.交换完调整
siftDown(arr,0,end);
end--;
}
}
堆排序完整代码：
public class heapSort {
public void headSort(int[] arr) {
//1.排升序，建大根堆
create(arr);
int end = arr.length - 1;
while(end > 0) {
//2.每次交换堆顶和最后一个元素
swap(arr,0,end);
//3.交换完调整
siftDown(arr,0,end);
end--;
}
}
/**
* 交换
*/
public void swap(int[] arr,int i,int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public void create(int[] arr) {
//从最后一棵子树向下调整
for (int parent = (arr.length -1-1)/2; parent >= 0 ; parent--) {
siftDown(arr,parent,arr.length);
}
}
/**
* 向下调整
*/
public void siftDown(int[] arr,int parent,int len) {
int child = parent*2 + 1;
while(child arr[child]) {
child = child + 1;
}
if(arr[child] > arr[parent]) {
swap(arr,child,parent);
parent = child;
child = parent*2 + 1;
}else {
break;
}
}
}
}
总结：
（1）时间复杂度：O(n*logn)
（2）空间复杂度：O(1)
（3）稳定性：不稳定
二、快速排序
快速排序是一种基于二叉树形式的交换数据排序，快听名字就知道他很快
下面介绍的快速排序，我们会介绍：快排的思想、Hoare版分割法、挖坑法分割法、如何优化快速排序和快速排序的非递归写法
1.思想解析
（1）官方概念
在待排序的 N个记录中任意取一个记录，把该 记录放在最终位置后， 数据序列被此记录分成两部分。 （如何分成两个部分：所有关键字比该记录关键 字小的放在前一部分, 所有比它大的放置在后一部分, 并把该记录排在这两部分 的中间，这个过程称作一次快速排序）之后重复上述过程， 直到每一部分内只有 一个记录为止。
（2）简述概念
（1）每次找一个基准，再定义两个指针（分别指向数据序列的两头），遍历该数据序列。（2）遍历时，满足一定的条件，就交换指针所指向的值或者其他操作，直到两个指针相遇。
（3）指针相遇的位置就将该序列分成左右两部分
（4）左右两个部分再重复（1）-（3）的操作，直到不能再分解，排序完成
我们这里暂时称（1）（2）两个步骤为：寻找基准法
上面的都是干巴巴的概念，很难理解，下面结合图解。
（3）图解如何完成排序
下面第一步到找到下一个基准的过程称为：找基准法（官方概念为Hoare版）；找基准法还有另一种称为：挖坑法
使用Hoare找基本法的每一轮：
（4）部分代码
根据上述的图解，我们得出，每次结束，就会将数组分成两个部分，然后每个部分再重复步骤，可以想到使用递归的方式完成。
partition2方法就是找基准法，具体实现下面介绍
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
int pivot = partition2(array,start,end);//记录每一轮基准的位置
//递归左边
quick(array,start,pivot-1);
//递归右边
quick(array,pivot+1,end);
}
找基准法一共有三种：Hoare版、挖坑法、前后指针法，其中最常用的是：挖坑法；不常见的是：前后指针法
2.Hoare版找基准
根据Hoare版的思想完成的代码，具体思想不再重复
private static int partition1(int[] array,int left,int right) {
//1.确定基准
int tmp = array[left];
int l = left;
//2.遍历数组，直到相遇
while (left = tmp) {
right--;
}
while (left = tmp) {
right--;
}
while (left = tmp) {
right--;
}
//3.放入left位置
array[left] = array[right];
while (left > 1 );
if(array[left] > array[right]) {
if(array[left] array[mid]) {
return right;
}else {
return mid;
}
}else {
if(array[mid] > array[right]) {
return right;
}else if(array[left] > array[mid]) {
return left;
}else {
return mid;
}
}
}
（2）递归到小区间时，使用插入排序
思想：结合插入排序
应对情况：一棵二叉树的结点，一般2/3都集中在最后面的几层；如果一直递归下去，计算量是非常大的。
核心：会使用插入排序
private static void quick(int[] array,int start,int end) {
if(start >= end) {
return;
}
//递归到一定的区间，使用插入排序(优化)
if((end-start+1) tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
总结：针对递归法
（1）时间复杂度：O(N*logN)
（2）空间复杂度：O(logN)
（3）稳定性：不稳定
（4）使用场景：数据较乱，不适合趋于有序或者已有序的
5.快速排序非递归
思想：
（1）先找一次基准（借助挖坑法）
（2）（判断：如果基准的左边：pivot-1>left不成立，则不放入栈；右边：pivot+1>right不成立也不放入）放入基准左边头跟尾的两个元素，再放入基准右边的头跟尾两个元素。
（3）栈不为空，取fenbuie除两个元素，分别赋值给右跟左
（4）以左跟右的区间继续找基准
（5）重复（2）-（4）
图解：
判断是否入栈：
代码：
public static void quickSortNor(int[] array) {
Stack stack = new Stack();
int left = 0;
int right = array.length - 1;
//1.找第一次基准
int pivot = partition(array,left,right);
//2.将基准左右两边存入栈中
if(pivot-1>left) {
stack.push(left);
stack.push(pivot-1);
}
if(pivot+1left) {
stack.push(left);
stack.push(pivot-1);
}
if(pivot+1= tmp) {
right--;
}
//3.放入left位置
array[left] = array[right];
while (left
2.代码展示及步骤
代码中的注释很全面的介绍了每个步骤
（1）代码展示
public class mergeSort {
public static void mergeS(int[] array){
mergeF(array,0,array.length-1);
}
//一.分解的方法（归）
private static void mergeF(int[] array,int left,int right){
//1.停止分解的条件
if(left>=right) {
return;
}
//2.记录拆分的位置
int mid = left + ((right - left)>>1);
//3.拆成的左半部分（使用递归）
mergeF(array,left,mid);
//4.拆成的右半部分（使用递归）
mergeF(array,mid+1,right);
//5.开始合并
merge(array,left,mid,right);
}
//二.合并的方法（并）
private static void merge(int[] array,int left,int mid,int right) {
int[] arrTmp = new int[right-left+1];
int s1 = left;//遍历第一个子序列
int e1 = mid; //记录第一个子序列末端位置
int s2 = mid+1;//遍历第二个子序列
int e2 = right;//记录第二个子序列末端位置
int k = 0;//遍历临时数组
//1.将其中一个序列的数据全部拷入临时数组中
while (s1= array.length) {
right = array.length-1;
}
merge(array,left,mid,right);
}
gap = gap*2;
}
}
完整非递归代码：
public static void mergeSortNor(int[] array) {
int gap = 1;//一组的数据个数
//循环一次，完成一轮合并
while (gap = array.length) {
mid = array.length-1;
}
int right = mid+gap;
if(right >= array.length) {
right = array.length-1;
}
merge(array,left,mid,right);
}
gap = gap*2;
}
}
private static void merge(int[] array,int left,int mid,int right) {
int[] arrTmp = new int[right-left+1];
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
int k = 0;
while (s1 
