对于归并排序，重点是要理解分治算法和递归处理的思想。如果要排序一个数组，那么我们首先要把数组从中间分成两段，然后对这两段分别进行排序，最后将排序好的两部分进行性别，这样整个数组就是一个有序的了。首先看一个图进行理解。
归并排序使用的是分治算法的思想。分治，就是分而治之，将一个大问题分解成一个小问题来进行解决。分治算法的思想与之前提到的递归很是相似，分治算法就是通过递归来进行实现的，分治是一种解决问题的思想，递归是一种编程技巧。
下面来看看代码
class Test{
public void mergeSort(int[] a,int start,int end){
if(start < end){
int mid = (start + end)/2;
mergeSort(a,start,mid);//左侧序列进行排序
mergeSort(a,mid + 1,end);//右侧序列进行排序
merge(a,start,mid,end);//合并
}
}
public void merge(int[] a,int left,int mid,int right){
//设置临时数组
int[] temp = new int[a.length];
//设置指针
int p1 = left;
int p2 = mid + 1;
int k = left;//这个k指向temp数组的第一个位置
while(p1 < mid && p2 < right){
if(a[p1] < a[p2]){
temp[k++] = a[p1++];
} else {
temp[k++] = a[p2++];
}
}
//如果左边的序列还有元素没有处理完，直接加到末尾
while(p1 < mid) temp[k++] = a[p1++];
while(p2 < right) temp[k++] = a[p2++];
//将temp的元素复制回a
for(int i : temp){
a[i] = temp[i];
}
}
@Test
public void test(){
int[] a = {2,3,4,5,6,2,4,5,7};
mergeSort(a, 0, a.length-1);
System.out.println("排好序的数组：");
for (int e : a)
System.out.print(e+" ");
}
}
}
归并排序是稳定排序算法
时间复杂度O(nlogn)
空间复杂度O(n)
快速排序
快速排序的原理和实现快速排序也用到了分治算法思想，下面来看看原理。
如果要排序数组中下标从p到r的数据。那么，我们选择p到r之间的任意一个数据作为pivot（分区点），然后遍历从p到r的数据，将小于pivot的数据放到左边，将大于或等于pivot的数据放到右边，将pivot放到中间。
经过处理，从p到r的数据就被分成3个部分。假设pivot目前所在的地方为q，那么p到q - 1的部分都小于pivot，q + 1到r的部分都大于pivot。如图。
根据分治的处理思想，分区完成之后，我们递归地排序下标从p到q - 1地数据和下标从q+1到r地数据，直到待排序区间大小缩小为１，这说明数组中所有地数据都有序了，下面用递推公式来表示。
quick_sort(p,r) = partition(p,r) + quick_sort(p,q-1) + quick_sort(q+1,r).
终止条件：ｐ＞＝ｒ
下面用伪代码来编写
quick_sort(A,n){
//A代表数组，ｎ代表大小
quick_sort_c(A,0,n-1)
}
//快速排序递归函数，ｐ，ｒ为下标
quick_sort_c(A,p,r){
if p >= r then return
q = partition(A,p,r)//分区
quick_sort(A,q+1,r)
}
partition()所做地工作就是随机选择一个元素作为pivot（一般选择p到r区间中地最后一个元素），然后基于pivot对A[p,r]分区。分区函数返回分区之后pivot地下标。
下面来看看快排实现原地分区函数
partition(A,p,r){
pivot := A[r]
i := p
for j := p to r do{
if A[j] < pivot{
swap A[i] with A[j]
i := i + 1
}
}
swap A[i] with A[j]
return i;
}
这里的处理有点类似选择排序。我们通过游标 i 把 A[p…r-1] 分成两部分。A[p…i-1] 的元
素都是小于 pivot 的，我们暂且叫它“已处理区间”，A[i…r-1] 是“未处理区间”。我们
每次都从未处理的区间 A[i…r-1] 中取一个元素 A[j]，与 pivot 对比，如果小于 pivot，则
将其加入到已处理区间的尾部，也就是 A[i] 的位置。
数组的插入操作还记得吗？在数组某个位置插入元素，需要搬移数据，非常耗时。当时我们
也讲了一种处理技巧，就是交换，在 O(1) 的时间复杂度内完成插入操作。这里我们也借助
这个思想，只需要将 A[i] 与 A[j] 交换，就可以在 O(1) 时间复杂度内将 A[j] 放到下标为 i
的位置。
如图：
归并排序的处理过程是
由下到上
的，先处理子问题，然后再合并。而快排正好相
反，它的处理过程是
由上到下
的，先分区，然后再处理子问题。归并排序虽然是稳定的、时
间复杂度为 O(nlogn) 的排序算法，但是它是非原地排序算法。我们前面讲过，归并之所以
是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分
区函数，可以实现原地排序，解决了归并排序占用太多内存的问题。
private void swap(int[] nums, int i, int j) {
int temp = nums [i];
nums [i] = nums [j];
nums [j] = temp;
}
private void quickSort(int[] nums, int left, int right) {
// 递归返回条件，和分区排序结束
if (right-left <=0) {
return;
}
// 选择数组右边界值作为分区节点
int pivot = nums[right];
// 从数组左边界值开始维护分区
int partition=left-1;
// 遍历当前分区内元素
for (int i = left; i <= right-1; i++) {
if ((nums [i] < pivot) ) {
// 将小于pivot的值交换到partition左边
// 将大于等于pivot的值交换到partition右边
partition++;
swap(nums, partition, i);
}
}
// 将分区节点插入到数组左右分区中间
partition++;
swap(nums, partition, right);
// 分区节点排序完成
// 左分区继续排序，右分区继续排序
quickSort(nums,left, partition-1);
quickSort(nums,partition+1, right);
}
public int[] sortArray(int[] nums) {
if (nums == null || nums.length ==0) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}
快速排序不是稳定性排序算法
时间复杂度O(nlogn)
空间复杂度O(n)
