归并排序：
image.png
归并所用到的思想是分治思想，何为分治，就是分而治之，大问题分解为小问题，让后把小问题的解合并在一起就是大问题的答案，归并可以理解为递归和合并，归并排序是稳定的，但是不是原地排序。
时间复杂度：
O（nlogn）
空间复杂度：
O（n）
原因是每次合并所用到的额外空间都会释放，而不是累加
归并排序的实现
利用递归
1、递归的终止条件为
p >= r （p、r分别为分解后的区域的头尾下标）
2、递归公式：
mergeSort(p....r) = mergeSort(p...q),mergeSort(p+1....r)
public void mergeSort(int[] a){
mergeSort(a,0,a.length-1);
}
private static void mergeSort(int[] a , int p,int r){
//终止条件
if (p >= r){
return;
}
//递归
int q = (p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a , p ,r,q); //合并
}
merge() 合并方法
//合并函数（无哨兵版）
private static void merge(int[] a, int p, int r,int q) {
int i = p ; int j = q+1; int k = 0;
int[] tmp = new int[r-p+1];
while (i <= q && j <= r){
if (a[i] <= a[j]){
tmp[k++] = a[i++];
}
else {
tmp[k++] = a[j++];
}
}
int start = i;
int end = q;
if (j <= r){
start = j;
end = r;
}
//将剩余的元素拷贝到临时数组
while (start <= end){
tmp[k++] = a[start++];
}
//将tmp拷贝回原数组
for (int n = 0 ; n < tmp.length;n++){
a[p+n] = tmp[n];
}
}
添加了哨兵
//合并函数哨兵版
private static void merge2(int[] a, int p ,int r,int q){
int i = p ; int j = q+1 ; int k = p;
//将要合并的两个部分分别放入两个数组中
int[] r1 = new int[q-p+2];
int[] r2 = new int[r-q+1];
for (int n=0;n+i <= q ; n++){
r1[n] = a[n+i];
}
r1[r1.length-1] = Integer.MAX_VALUE;//在数组后面加个最大值 即添加哨兵
for (int n=0;n+j <= r ; n++){
r2[n] = a[n+j];
}
r2[r2.length-1] = Integer.MAX_VALUE;
//之后就无需判断哪个数组没有清空，直接清空完两个临时数组
for (k = p ,i = 0 ,j = 0; k <=r ;k++){
if (r1[i] < r2[j]){
a[k] = r1[i];
i++;
}
else {
a[k] = r2[j];
j++;
}
}
}
快速排序：
不稳定、原地排序
时间复杂度：
O(nlogn) 平均
O(n^2) 最坏
先进行分区，然后再处理子问题。先以数组最后一个元素作为分区点，将大于分区点的元素放在分区点右边，反之放左边。
例如：
8 10 2 3 6 1 5
选取 5
分区后
2 3 1 5 8 10 6
继续对两个区域进行快速排序，直到不可分解为止 即（p>=r）
//快速排序
public void quickSort(int[] a){
quickSort(a , 0 , a.length-1);
}
private void quickSort(int[] a, int p, int r) {
//递归终止条件
if (p >= r) return;
//分区 返回分开两个部分的下标 ，左边的都比q小，右边都比q大
int q = partition( a, p, r);
//递归
quickSort(a , p , q-1);
quickSort(a , q+1 ,r);
}
为了使排序是原地的，通过交换元素解决。
//分区函数
private static int partition(int[] a, int p, int r) {
int pivot = a[r];//以所传入的区域的最右边的元素作为分区点
int i=p ;
for (int j = p ; j <= r-1 ; j++){
if (a[j] < pivot){
swap(a,j,i);//交换j、i
i++;
}
}
swap(a,i,r);//所有的元素都处理过了（处理的区域为【p，r-1】)，让分区点换到自己的真正的位置
return i;//返回分区点下标
}
private static void swap(int[] a, int b ,int c){
int temp = a[b];
a[b] = a[c];
a[c] = temp;
}
