定义方法时，在方法内部调用方法本身，称为递归。
递归能够将一个大型复杂的问题，转换为一个与原问题相似的，规模较小的问题来求解。
注意：在递归中，不能无限制地调用自己，必须要有边界条件，能够让递归结束，因为每一次递归调用都会在栈内存开辟新的空间，重新执行方法，如果递归的层级太深，很容易造成栈内存溢出。
归并原理：
定义三个指针，其中指针index1指向左子组第一个元素，指针index2指向右子组第一个元素，指针index3指向辅助数组assist。
package sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[]{12,2,2,323,42,342,341};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static int[] assist;
public static void sort(int[] arr) {
//1.初始化辅助数组assist
assist = new int[arr.length];
//2.定义一个low变量和一个high变量分别记录数组中最小的索引和最大的索引
int low = 0;
int high = arr.length-1;
//3.调用sort重载方法完成数组中从low索引到索引high的元素的排序
sort(arr,low,high);
}
private static void sort(int[] arr,int low,int high) {
//安全性校验
if(high <= low) {
return;
}
//对low到high之间的数据分为两个组
int mid = low + (high - low)/2;
//分别对每一组数据进行排序
sort(arr,low,mid);
sort(arr,mid+1,high);
//再把两个组中的数据进行归并
merge(arr,low,mid,high);
}
//对数组中从low到mid为一组，从mid+1到high为一组的两组数据进行归并
private static void merge(int[] arr,int low,int mid,int high) {
//定义三个指针
int index1 = low;
int index2 = mid+1;
int index3 = low;
//遍历，移动index1指针和index2指针，比较对应索引处的值，找出小的那一个，放到对应辅助数组的对应索引处
while(index1 <= mid && index2 <= high) {
if (arr[index1] <= arr[index2]) {
assist[index3++] = arr[index1++];
} else {
assist[index3++] = arr[index2++];
}
}
//遍历，如果index1处的指针没有走完，将对应元素放到辅助索引数组的对应索引处
while(index1 <= mid) {
assist[index3++] = arr[index1++];
}
//遍历，如果index2处的指针没有走完，将对应元素放到辅助索引数组的对应索引处
while(index2 <= high) {
assist[index3++] = arr[index2++];
}
//将辅助数组中的元素拷贝到原数组中
for (int i = low;i <= high;i++) {
arr[i] = assist[i];
}
}
}
时间复杂度分析
因此其时间复杂度为：O(nlogn)
需要申请额外的数组空间，空间复杂度为O(n)
快速排序快速排序是对冒泡排序的一种改进。
通过一趟排序将待排序的数据分割成独立的两个部分，其中一部分的所有数据都比另一部分的所有数据都要小。再根据这样的方法对这两部分数据做同样的操作，最后达到整个数据有序的情况。
package sort;
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{2,34,235,52};
quickSort(arr,0,arr.length-1);
for (int i = 0;i < arr.length;i++) {
System.out.println(arr[i]);
}
}
public static void quickSort(int[] arr,int low,int high) {
if (low > high) {
return;
}
int i = low,j = high;
// int tmp = arr[(int)(Math.random()*arr.length)];
int tmp = arr[low];
while(i < j) {
while(i < j && tmp <= arr[j]) {
j--;
}
while(i < j && tmp >= arr[i]) {
i++;
}
if (i < j) {
int tempNum = arr[i];
arr[i] = arr[j];
arr[j] = tempNum;
}
}
arr[low] = arr[i];
arr[i] = tmp;
quickSort(arr,low,i-1);
quickSort(arr,i+1,high);
}
}
2.
package sort;
import java.util.Arrays;
public class QuickSort2 {
public static void main(String[] args) {
int[] arr = new int[]{12,45,342,42,424,342};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int low = 0;
int high = arr.length-1;
sort(arr,low,high);
}
public static void sort(int[] arr,int low,int high) {
//安全性校验
if (high <= low) {
return;
}
int partition = partition(arr, low, high);
sort(arr,low,partition-1);
sort(arr,partition+1,high);
}
public static int partition(int[] arr,int low,int high) {
//确定分界值
int key = arr[low];
//定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
int left = low;
int right = high+1;
//切分
while (true) {
//先从右向左扫描，移动right指针，找到一个比分界值小的元素，停止
while (arr[--right] > key) {
if (right == low) {
break;
}
}
//再从左向右扫描，移动left指针，找到一个比分界值大的元素，停止
while (arr[++left] < key) {
if (left == high) {
break;
}
}
//判断left >= right，如果是，则证明元素扫描完毕，就要结束循环；如果不是，交换元素即可
if (left >= right) {
break;
} else {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
}
//交换分界值 和 两指针指向的元素
int tmpNum = arr[low];
arr[low] = arr[right];
arr[right] = tmpNum;
//返回分界值所在索引，即left或者right
return right;
}
}
快速排序时间复杂度分析
快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n)，但整个快速排序的时间复杂度和切分的次数相关。
最优情况：每一次切分选择的基准数字刚好将当前序列等分，因此最优情况下快速排序的时间复杂度为O(nlogn)。
最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以最坏情况下，快速排序的时间复杂度为O(n^2)。
平均情况：每一次切分选择的基准数字不是最大值和最小值，也不是中值。时间复杂度为O(nlogn)。
快速排序是另外一种分治的排序算法，它将一个数组分为两个子数组，将两部分独立地排序。
快速排序和归并排序是互补的：
1.归并排序是将数组分成两个子数组分别进行排序，并将有序的子数组归并，从而将整个数组排序（分别排序然后归并）；快速排序是当两个数组都有序的时候，整个数组就有序了（没有归并动作）。
2.在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前；在快速排序中，切分数组的位置取决于数组的内容，递归调用发生在处理整个数组之后。
