归并排序和快速排序是面试常考的两大排序，两者平均时间复杂度均可以达到O(nlogn)。接下来将记录一下这两种排序的动图原理显示以及代码的记忆方式。
归并排序
一、动图展示
动图原文链接：https://blog.csdn.net/qq_36442947/article/details/81612870
二、做法及思路
在Java中，万物皆对象。因此我们可以尝试以面向对象的思想来进行编写。
- 定义一个类MergeSort，并为其添加私有成员变量arr数组和数组长度arrayLength，当然，也需要添加必要的getset方法;
- 定义public的mergeSort方法作为向外提供的排序接口，这个方法主要实现：判断数组是否为空，以及MSort函数的调用；
- 定义一个private的mSort方法作为正式开始，这个方法主要实现：将数组不断拆分到不可拆为止，最后再将拆完的单个元素数组合并为两个元素、四个元素等等。。。从动图可以看到这个过程是循环往复的，因此可以考虑采用递归来实现，边界条件就是开始角标小于结束角标；
- 定义一个merge方法专门用来将两个小单元进行合并，合并的思路就像上面图片那样，这里我们需要新建一个中间数组用来存放合并后的结果：
- 一前一后有两个指针，分别指向待合并两部分的开头；
- 当前一个指向的元素更小时，令前一个元素赋值给中间数组tmp，前一个的指针向后移动；
- 同样的，当后一个指向的元素更小时，令后一个元素赋值给tmp，后一个指针也++；
- 我们知道，这样做并不能保证两个数组同时完成自己的任务，因此最终一定会剩下左右其中一个数组还没有全部放入tmp，这个时候就对没有操作完的数组的剩余部分全部放到tmp中；
- 最后，我们并不想直接返回这个中间数组，因此需要将中间数组赋值给我们类中的arr数组。
过程还是较多的，但其中很大部分都是很容易想到的。上面说的难免有遗漏，可以看注释：
1 public class MergeSort { 2 private int[] arr; 3 4 private int arrayLength; 5 6 public MergeSort(int arr[]){ 7 this.arr = arr; 8 setArrayLength(); 9 }10 public void setArr(int[] arr) {11 this.arr = arr;12 setArrayLength();13 }14 15 public int[] getArr() {16 return arr;17 }18 19 public void setArrayLength() {20 if(arr!=null)21 this.arrayLength = arr.length;22 }23 24 public void mergeSort(){25 if(arr!=null){26 int[] temp = new int[arrayLength];27 mSort(0, arr.length-1, temp);28 }29 else{30 // throw new RuntimeException();31 System.out.println("待排序数组为空");32 }33 }34 /*保证共用一个temp，节省内存*/35 private void mSort(int start, int end, int[] temp){36 int center;37 if(start 可以看到除了我们自己添加的一些非重要代码，正式的归并排序代码仅有三十行左右。
快速排序
一、动图展示
二、做法及思路
当然，现在图文还不符。图示标准快排，文是变化版快排，特点是代码短一点。
1 public void quickSort_2(int[] data, int start, int end) { 2 if (data == null || start >= end) return; 3 int i = start, j = end; 4 int pivotKey = data[start]; 5 while (i < j) { 6 while (i < j && data[j] >= pivotKey) j--; 7 if (i < j) data[i++] = data[j]; 8 while (i < j && data[i] <= pivotKey) i++; 9 if (i < j) data[j--] = data[i];10 }11 data[i] = pivotKey;12 quickSort_2(data, start, i - 1);13 quickSort_2(data, i + 1, end);14 }