最近学习了归并排序和快速排序，在这里写一篇博客用于复习并且检验自己是否有遗漏知识点的情况。
归并排序的思想
归并排序使用的思想为分治法。分治思想分为两部分第一部分为：分解，第二部分为合并。
首先，将待排序的序列分成若干个子序列，每个子序列都是有序的。然后，再将这些有序的子序列合并成一个大的有序序列。其中合并过程是重点，需要使用额外的空间。合并过程可以借助两个指针和一个辅助数组，将两个有序的子序列合并成一个有序的序列。
归并排序的基本思想是，在进行排序的过程中，先将数据分成两个部分，然后对这两部分分别进行排序，最后将这两个已经有序的部分合并成一个有序的整体。这种分治思想的好处是，可以将一个大的复杂问题分解成多个小的简单问题来解决，使得算法的实现更加容易，也更加高效。
如果这里有一个无序的数组那么归并排序首先就会将整个数组分成一个一个单独的有序序列，然后将这些有序序列合并到一起，这也就是归并排序的大体思路。
这是图解
那么下面来写代码
归并函数1：分割
首先归并排序要完成的函数有两个函数1的功能为不断地分割元素，函数2的功能为合并有序的区间
归并函数二：合并
执行结果：
快速排序的思想
快速排序（QuickSort）是一种高效的排序算法，基于分治的思想。具体实现思路如下：
- 选择一个基准元素，将待排序序列分成两部分，使基准元素左边的所有元素都比基准元素小，右边的所有元素都比基准元素大。
- 对左右两部分递归地进行快速排序，直到序列只剩一个元素或为空。
在实现上，一般选择待排序序列的第一个元素作为基准元素，通常称之为“枢轴值”（pivot）。然后从序列的两端开始向中间扫描，找到一个比枢轴值大的元素和一个比枢轴值小的元素，将它们交换位置。不断重复这个过程，直到两个指针相遇，此时将枢轴值和相遇的位置的元素进行交换。这个过程称为一次划分（Partition），划分后基准元素在序列中的最终位置也就确定下来了。然后对划分出来的左右子序列进行递归处理，直到整个序列有序。
而寻找枢轴值的方法也有三种。
寻找枢轴值的方法
方法一：挖坑法
挖坑法首先就要确定一个key值，一般是拿无序数组的第一个数当作key值，然后定义一个begin等于数组第一个元素的下标，一个end等于数组最后一个元素的下标，再定义一个pivot当作坑所在的下标，默认key所在的位置也就是第一个坑。然后从右端开始从右往左寻找小于key的值，找到之后赋值给坑，然后这个右端end的位置也就成为了新坑，再从左往右寻找大于key的值，找到之后赋值给新坑，然后这个位置再次新成新的坑。最后当begin和end相等的时候这个位置也就是key的位置，那么此时key的左端全部都是小于它的元素，右端全部是大于key的元素，这样key就待在了正确的位置。
下面是代码实现：
那么接下来要怎么让整个数组都变成有序呢？那么就将左半部分再次使用挖坑法，让左半的有一个元素变得有序，最后和归并一样让整个数组变得有序。下面便是图解。
代码实现：
下面是运行结果：
方法二：左右指针法
此方法和挖坑法的思路很相似，也是先找到基准值，然后定义一个right，一个left，让right从右端开始寻找小于right的值，然后让right停止在小于基准值的那个位置，再让left从左端开始从左往右寻找大于基准值的位置，再让left和right所在的元素交换，这样不断继续，直到最后当left和right指向同一个位置的时候，让left或是right和基准值交换，这样也就完成了基准值左端为小于它的元素，右端为大于它的元素。下面是代码实现
方法三：前后指针法
首先依旧是找到一个基准值
使用一个prev，一个cur，让cur等于left（最左端的下标）prev等于left+1，然后prev往右，当遇到小于基准值的元素时，先让cur向前进一位，再让cur和prev所在的元素交换，直到最后prev超出范围的时候cur所在的位置也就是基准值应该在的位置。画图表示
这里cur遇到的值为1的时候先让prev加1让其指向了8，然后交换这两个元素。按照这个规则不断进行下去直到最后当cur超出范围之后就会出现下面的情况
最后交换基准值和prev也就完成了第一躺快排，之后思路同上。
代码实现：