（6）归并排序
（1）递归
正式学习归并排序之前，我们得先学习一下递归算法。
定义：
定义方法时，在方法内部调用方法本身，称之为递归.
public void show(){ System.out.println("aaaa"); show(); }
作用：
它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量的 程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意事项：
在递归中，不能无限制的调用自己，必须要有边界条件，能够让递归结束，因为每一次递归调用都会在栈内存开辟 新的空间，重新执行方法，如果递归的层级太深，很容易造成栈内存溢出。
需求：
请定义一个方法，使用递归完成求N的阶乘；
分析： 1!: 2!: 3!: 4!: ... n!: 1 2*1=2*1! 3*2*1=3*2! 4*3*2*1=4*3! n*(n-1)*(n-2)...*2*1=n*(n-1)! 所以，假设有一个方法factorial(n)用来求n的阶乘，那么n的阶乘还可以表示为n*factorial(n-1)
代码实现：
package cn.itcast.algorithm.test; /** * @author ：caizhengjie * @description：TODO * @date ：2021/1/31 1:54 下午 */ public class FactorialTest { public static void main(String[] args) { int result = factorial(5); System.out.println(result); } public static int factorial(int n){ if (n == 1){ return 1; } return n*factorial(n-1); } }
（2）归并排序
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序 表，称为二路归并。
需求：
排序前：{8,4,5,7,1,3,6,2}
排序后：{1,2,3,4,5,6,7,8}
排序原理：
尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止。
将相邻的两个子组进行合并成一个有序的大组；
不断的重复步骤2，直到最终只有一个组为止。
归并排序 API设计：
归并原理：
归并排序代码实现：
package cn.itcast.algorithm.sort; /** * @author ：caizhengjie * @description：归并排序 * @date ：2021/1/31 2:00 下午 */ public class Merge { /** * 归并所需要的数组 */ private static Comparable<Integer>[] assist; /** * 对数组arr中的元素进行排序 * @param arr */ public static void sort(Comparable<Integer>[] arr){ // 初始化辅助数组 assist = new Comparable[arr.length]; // 定义一个lo变量，和hi变量，分别记录数组中最小索引和最大索引 int lo = 0; int hi = arr.length - 1; // 调用sort重载方法完成数组arr中从索引lo到索引hi的元素排序 sort(arr,lo,hi); } /** * 对数组arr中从lo到hi的元素进行排序 * @param arr * @param lo * @param hi */ public static void sort(Comparable<Integer>[] arr,int lo,int hi){ // 安全性比较 if (lo == hi){ return; } // 对lo到hi之间的数据进行分为两个组 int mid = lo + (hi - lo) / 2; // 分别对每一组数据进行排序 sort(arr, lo, mid); sort(arr, mid+1, hi); // 在把两个数组中的数据进行归并 merge(arr,lo,mid,hi); } /** * 对数组中从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并 * @param arr * @param lo * @param mid * @param hi */ public static void merge(Comparable<Integer>[] arr,int lo,int mid,int hi){ // 定义一个指针，指向assist数组中开始填充数据的索引 int i = lo; // 定义一个指针，指向第一组数据的第一个元素 int p1 = lo; // 定义一个指针，指向第二组数据的第一个元素 int p2 = mid + 1; // 遍历，移动p1指针和p2指针，比较对应索引的值，找出小的那个，放到辅助数组对应的索引 while (p1 <= mid && p2 <= hi){ // 比较对应索引处的值 if (less(arr[p1],arr[p2])){ assist[i++] = arr[p1++]; } else { assist[i++] = arr[p2++]; } } // 遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引 while (p1 <= mid){ assist[i++] = arr[p1++]; } // 遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引 while (p2 <= hi){ assist[i++] = arr[p2++]; } // 把辅助数组中的元素拷贝到原数组中 for(int index = lo;index<=hi;index++){ arr[index] = assist[index]; } } /** * 比较v元素是否小于w元素 * @param v * @param w * @return */ public static boolean less(Comparable<Integer> v,Comparable<Integer> w){ return v.compareTo((Integer) w)<0; } /** * 数组元素i和j交换位置 * @param arr * @param i * @param j */ public static void exch(Comparable<Integer>[] arr,int i,int j){ Comparable<Integer> comparable = arr[i]; arr[i] = arr[j]; arr[j] = comparable; } }
package cn.itcast.algorithm.test; import cn.itcast.algorithm.sort.Merge; import java.util.Arrays; /** * @author ：caizhengjie * @description：TODO * @date ：2021/1/31 3:10 下午 */ public class MergeTest { public static void main(String[] args) { Integer[] arr = {8,4,5,6,2,3,7,9,1}; Merge.sort(arr); System.out.println(Arrays.toString(arr)); } }
归并排序时间复杂度分析：
归并排序是分治思想的最典型的例子，上面的算法中，对a[lo…hi]进行排序，先将它分为a[lo…mid]和a[mid+1…hi] 两部分，分别通过递归调用将他们单独排序，最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果 一个数组不能再被分为两个子数组，那么就会执行merge进行归并，在归并的时候判断元素的大小进行排序。
用树状图来描述归并，如果一个数组有8个元素，那么它将每次除以2找最小的子数组，共拆log8次，值为3，所以 树共有3层,那么自顶向下第k层有2 ^ k个子数组，每个数组的长度为2 ^ (3-k)，归并最多需要2^(3-k)次比较。因此每层的比较次数为 2 ^ k * 2 ^ (3-k)=2 ^ 3,那么3层总共为 3*2 ^3。
假设元素的个数为n，那么使用归并排序拆分的次数为log2(n),所以共log2(n)层，那么使用log2(n)替换上面32^3中 的3这个层数，最终得出的归并排序的时间复杂度为：log2(n) 2^(log2(n))=log2(n)*n,根据大O推导法则，忽略底 数，最终归并排序的时间复杂度为O(nlogn);
归并排序的缺点：
需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。
归并排序与希尔排序性能测试：
之前我们通过测试可以知道希尔排序的性能是由于插入排序的，那现在学习了归并排序后，归并排序的效率与希尔 排序的效率哪个高呢？我们使用同样的测试方式来完成一样这两个排序算法之间的性能比较。
在资料的测试数据文件夹下有一个reverse_arr.txt文件，里面存放的是从1000000到1的逆向数据，我们可以根据 这个批量数据完成测试。测试的思想：在执行排序前前记录一个时间，在排序完成后记录一个时间，两个时间的时 间差就是排序的耗时。
通过测试，发现希尔排序和归并排序在处理大批量数据时差别不是很大。
（7）快速排序
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一 部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序 过程可以递归进行，以此达到整个数据变成有序序列。
需求：
排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}
排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}
排序原理：
首先设定一个分界值，通过该分界值将数组分成左右两部分；
将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；
然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。
快速排序 API设计:
切分原理：
把一个数组切分成两个子数组的基本思想：
找一个基准值，用两个指针分别指向数组的头部和尾部；
先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
交换当前左边指针位置和右边指针位置的元素；
重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。
快速排序代码实现：
package cn.itcast.algorithm.sort; /** * @author ：caizhengjie * @description：快速排序 * @date ：2021/2/1 3:23 下午 */ public class Quick { /** * 对数组arr中的元素进行排序 * @param arr */ public static void sort(Comparable<Integer>[] arr){ // 定义一个lo变量，和hi变量，分别记录数组中最小索引和最大索引 int lo = 0; int hi = arr.length - 1; // 调用sort重载方法完成数组arr中从索引lo到索引hi的元素排序 sort(arr,lo,hi); } /** * 对数组arr中从lo到hi的元素进行排序 * @param arr * @param lo * @param hi */ public static void sort(Comparable<Integer>[] arr,int lo,int hi){ // 安全性比较 if (hi <= lo){ return; } // 需要对数组中lo索引到hi索引之间的元素进行分组（左子组和右子组） int partition = partition(arr, lo, hi); // 对左边分组中的元素进行排序 sort(arr, lo, partition-1); // 对右边分组中的元素进行排序 sort(arr, partition+1, hi); } /** * 对数组arr中从lo到hi的元素进行分组，并返回分组界限对应的索引 * @param arr * @param lo * @param hi * @return */ public static int partition(Comparable<Integer>[] arr,int lo,int hi){ //把最左边的元素当做基准值 Comparable<Integer> key = arr[lo]; // 定义一个左侧指针，初始指向最左边的元素 int left = lo; // 定义一个右侧指针，初始指向左右侧的元素下一个位置 int right = hi + 1; // 进行切分 while (true){ // 先从右往左扫描，找到一个比基准值小的元素,循环停止，证明找到了一个比基准值小的元素 while (less(key,arr[--right])){ if (right == lo){ // 已经扫描到最左边了，无需继续扫描 break; } } // 再从左往右扫描，找一个比基准值大的元素,循环停止，证明找到了一个比基准值大的元素 while (less(arr[++left],key)){ if (left == hi){ // 已经扫描到了最右边了，无需继续扫描 break; } } //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可 if (left>=right){ break; }else{ exch(arr,left,right); } } // 交换最后rigth索引处和基准值所在的索引处的值 exch(arr,lo,right); // right就是切分的界限 return right; } /** * 比较v元素是否小于w元素 * @param v * @param w * @return */ public static boolean less(Comparable<Integer> v,Comparable<Integer> w){ return v.compareTo((Integer) w)<0; } /** * 数组元素i和j交换位置 * @param arr * @param i * @param j */ public static void exch(Comparable<Integer>[] arr,int i,int j){ Comparable<Integer> comparable = arr[i]; arr[i] = arr[j]; arr[j] = comparable; } }
package cn.itcast.algorithm.test; import cn.itcast.algorithm.sort.Quick; import java.util.Arrays; /** * @author ：caizhengjie * @description：TODO * @date ：2021/2/1 4:26 下午 */ public class QuickTest { public static void main(String[] args) { Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8}; Quick.sort(arr); System.out.println(Arrays.toString(arr)); } }
快速排序和归并排序的区别：
快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。快速排序和归并排序 是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的 方式则是当两个数组都有序时，整个数组自然就有序了。在归并排序中，一个数组被等分为两半，归并调用发生在 处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。
快速排序时间复杂度分析：
快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n),但整个 快速排序的时间复杂度和切分的次数相关。
最优情况：每一次切分选择的基准数字刚好将当前序列等分。
如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);
最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总 共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);
平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证 明，快速排序的时间复杂度为O(nlogn),由于数学归纳法有很多数学相关的知识，容易使我们混乱，所以这里就不对 平均情况的时间复杂度做证明了。
（8）排序的稳定性
稳定性的定义：
数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保 证A元素依然在B元素的前面，可以说这个该算法是稳定的。
常见排序算法的稳定性：
冒泡排序：
只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序 算法。
选择排序:
选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍选择到的最小元素为2， 所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
插入排序：
比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其 后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等 元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序 是稳定的。
希尔排序：
希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在 不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不 稳定的。
归并排序：
归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它 并不会破坏稳定性，归并排序是稳定的。
快速排序：
快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素， 然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。
