一、堆排序
所谓堆排序，就是在堆的基础上进行排序，那么如何建堆，就是堆排序的重点。
堆排序核心思想：
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 < len) { //1.找左右孩子最大的 if(child+1 < len && arr[child+1] > 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 < end) { //1.找左右孩子最小的一个.进入if说明第二个孩子比较大 if(child+1 < usedSize && elem[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 < len) { //1.找左右孩子最大的 if(child+1 < len && arr[child+1] > 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 < right) { while (left < right && array[right] >= tmp) { right--; } while (left < right && array[left] <= tmp) { left++; } //交换两个值 swap(array,left,right); } //3.交换相遇位置和基本位置的值 swap(array,l,right); //4.返回相遇位置，作为下一次的分割点 return right; } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
第一种快速排序完整代码：
public static void quick(int[] array,int start,int end) { if(start >= end) { return; } int pivot = partition(array,start,end);//记录每一轮基准的位置 //递归左边 quick(array,start,pivot-1); //递归右边 quick(array,pivot+1,end); } private static int partition(int[] array,int left,int right) { //1.确定基准 int tmp = array[left]; int l = left; //2.遍历数组，直到相遇 while (left < right) { while (left < right && array[right] >= tmp) { right--; } while (left < right && array[left] <= tmp) { left++; } //交换两个值 swap(array,left,right); } //3.交换相遇位置和基本位置的值 swap(array,l,right); //4.返回相遇位置，作为下一次的分割点 return right; } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
3.挖坑法找基准
挖坑法是最常用的一种，具体实现和Hoare版很相似。
（1）挖坑法思想
每一轮的结果：
（2）挖坑法代码
private static int partition(int[] array,int left,int right) { //1.将基准存入临时变量中，形成一个坑 int tmp = array[left]; //2.遍历数组，直到相遇 while (left < right) { while (left < right && array[right] >= tmp) { right--; } //3.放入left位置 array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } //4.放入right位置 array[right] = array[left]; } //5.补坑 array[right] = tmp; return right; } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
第二种快速排序完整代码：
public static void quick(int[] array,int start,int end) { if(start >= end) { return; } int pivot = partition(array,start,end);//记录每一轮基准的位置 //递归左边 quick(array,start,pivot-1); //递归右边 quick(array,pivot+1,end); } private static int partition(int[] array,int left,int right) { //1.将基准存入临时变量中，形成一个坑 int tmp = array[left]; //2.遍历数组，直到相遇 while (left < right) { while (left < right && array[right] >= tmp) { right--; } //3.放入left位置 array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } //4.放入right位置 array[right] = array[left]; } //5.补坑 array[right] = tmp; return right; } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
4.快速排序的优化
对于不同的数据，死板的写法不一定有其他排序快；但是根据不同的场景进行不同的优化，可以大大提高快速排序的效率。
下面介绍两种常见的优化方式
（1）三数取中法
思想：在一堆序列中，找到最左边的数、中间的数和最右边的数中 中间小的一个数与最左边的数进行交换，再以最左边的数为基准进行划分。可以防止升序或者逆序而造成的单分支情况。
应对情况：常见与已有序的序列（顺序或者逆序）
核心：找到三个数中排在中间的数
举例：下面为顺序的序列，当默认选择第一个数为基准时，右边都是比基准大的而不会交换；在递归过程中，就会形成单分支的二叉树，复杂度进而变大
三数取中，取的数为：
如何找中间值：
代码如下：
private static void quick(int[] array,int start,int end) { if(start >= end) { return; } //三数取中法（优化） int index = findMid(array,start,end); swap(array,index,start); int pivot = partition(array,start,end); //递归左边 quick(array,start,pivot-1); //递归右边 quick(array,pivot+1,end); } /* 找中间大的元素下标 */ private static int findMid(int[] array,int left,int right) { int mid = left+( (right - left) >> 1 ); if(array[left] > array[right]) { if(array[left] < array[mid]) { return left; }else if(array[right] > 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) < 5) { insertSort(array,start,end); return; } int pivot = partition2(array,start,end); //递归左边 quick(array,start,pivot-1); //递归右边 quick(array,pivot+1,end); } /** * 区间插入排序 */ private static void insertSort(int[] array,int start,int end) { for (int i = start+1; i <= end; i++) { int tmp = array[i]; int j = i-1; for (; j >= start ; j--) { if(array[j] > 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<Integer> 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+1<right) { stack.push(pivot+1); stack.push(right); } //3.栈不为空出栈 while (!stack.empty()) { right = stack.pop(); left = stack.pop(); pivot = partition2(array,left,right); //2.将基准左右两边存入栈中 if(pivot-1>left) { stack.push(left); stack.push(pivot-1); } if(pivot+1<right) { stack.push(pivot+1); stack.push(right); } } } private static int partition(int[] array,int left,int right) { //1.将基准存入临时变量中，形成一个坑 int tmp = array[left]; //2.遍历数组，直到相遇 while (left < right) { while (left < right && array[right] >= tmp) { right--; } //3.放入left位置 array[left] = array[right]; while (left < right && array[left] <= tmp) { left++; } //4.放入right位置 array[right] = array[left]; } //5.补坑 array[right] = tmp; return right; } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }
时间复杂度：nlogn
空间复杂度：longn
稳定性：不稳定
三、归并排序
下面的归并排序，我们注重介绍：归并排序的思路（包括文字思路，图片思路）、归并排序的代码和代码执行过程的讲解
归并排序和快速排序类型，使用了分治的思想，其中，也需要用到递归的。而归并排序的核心就是一分为二，再合并。
1.归并思路
（1）大致思想
（1）将数据不断平分为两段，直到不能再分解，形成一个单独的有序个体。
（2）然后在往回走的过程中，不断合并做到有序。
（2）具体图解：
分解思路：
并起思路：在合并的过程中就完成了排序
（3）如何分解：加入一点数学知识
下面是所有片段的left，mid和right位置
根据这里得出一个规律：当left>=right时，分解停止。
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<=e1 && s2<=e2) { if(array[s1] > array[s2]) { arrTmp[k++] = array[s2++]; }else { arrTmp[k++] = array[s1++]; } } //2.将未拷完的子序列继续拷入 while (s1<=e1) { arrTmp[k++] = array[s1++]; } while (s2<=e2) { arrTmp[k++] = array[s2++]; } //3.将排序好的临时数组中的数据拷回原数组 for (int i = 0; i < arrTmp.length; i++) { array[i+left] = arrTmp[i]; } } }
（2）数据拷贝回原数组部分
//3.将排序好的临时数组中的数据拷回原数组 for (int i = 0; i < arrTmp.length; i++) { array[i+left] = arrTmp[i]; }
3.代码分析
上面对代码的简述也只是一种简单的概述，下面详细介绍一下代码的执行过程，包括是如何递归，及如何并。
部分过程：
类似二叉树的递归，当递归到一定条件时，才会开始合并；并不是和前面的图片一样，要全部分解完才开始逐一递归。
部分合并过程：
总结：
（1）时间复杂度：O(N*logN)
（2）空间复杂度：O(logn)
（3）稳定性：稳定
（4）使用场景：在磁盘中的外排序问题
4.归并排序非递归
引入：非递归的归并排序，重点也在后面的合并方法上；递归法是先递归到最小单元才开始合并，而非递归是直接开始合并。
步骤分析：
（1）定义一个变量gap，用来标识最小的有序集；每次合并两个有序集，当gap>=数组长度一半时，代表排序完成。
（2）定义一个变量i，用来遍历数组中所有的有序集，每次跳过两个有序集
（3）我们只需要根据合并的方法拿到对应的下标即可
思路解析：非递归，我们使用直接从最小单元开始合并，也就是以一个数据作为最小单位。
需要拿到的下标：这是根据上面递归法写的合并方法，这里通用。
根据上面得到以下代码：
public static void mergeSortNor(int[] array) { int gap = 1;//一组的数据个数 //循环一次，完成一轮合并 while (gap < array.length) { //每循环一次，代表合并两个组 for (int i = 0; i < array.length; i = i+2*gap) { int left = i; int mid = left+gap-1; //两个if，防止数组越界 if(mid >= 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; } }
完整非递归代码：
public static void mergeSortNor(int[] array) { int gap = 1;//一组的数据个数 //循环一次，完成一轮合并 while (gap < array.length) { //每循环一次，代表合并两个组 for (int i = 0; i < array.length; i = i+2*gap) { int left = i; int mid = left+gap-1; //两个if，防止数组越界 if(mid >= 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<=e1 && s2<=e2) { if(array[s1] > array[s2]) { arrTmp[k++] = array[s2++]; }else { arrTmp[k++] = array[s1++]; } } while (s1<=e1) { arrTmp[k++] = array[s1++]; } while (s2<=e2) { arrTmp[k++] = array[s2++]; } for (int i = 0; i < arrTmp.length; i++) { array[i+left] = arrTmp[i]; } }
5.使用归并排序解决海量数据
当所排序的对象巨大时，需要使用外部排序，而归并排序就是外部排序的一种典型代表。
外部排序：排序过程需要在磁盘等外部存储进行的排序（不直接借助内存）
使用场景：内存只有1G，而排序的数据却有100G
所以我们需要使用归并排序去完成：
（1）先把文件切分成 200 份，每个 512 M
（2）分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
（3）进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了（这个时候不借助内存）
