参考视频bilibil fjnuzs
文章目录 一、归并排序其实很简单二、Java实现三、时间复杂度
一、归并排序其实很简单
根据分治法的思想，我们先把他拆成多个子问题，然后递归求解子问题。最后把子问题合并。归并排序其实是在合并的时候才真正排序了的。假设我们对84571362排序，那么子问题变为对8457和1362分别排序，一直递归下去，直到变成两个数间的排序。合并就是合并两个有序子序列。
二、Java实现 /** * 归并排序 * 速度赶上快排 */public class Merge {public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length-1, temp);}public static void mergeSort(int[] arr, int left, int right, int[] temp) {if(left < right) {int mid = (left+right)/2;mergeSort(arr, left, mid, temp); //分解子问题mergeSort(arr, mid+1, right, temp);merge(arr, left, mid, right, temp); //组合子问题的解//八个数输出7次System.out.println(Arrays.toString(arr));}}public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int t = 0;//左右两边比较后填充temp数组while(i <= mid && j<= right) {if(arr[i] <= arr[j]) {temp[t] = arr[i];t++;i++;}else {temp[t] = arr[j];t++;j++;}}//有一遍处理完了，另一边剩下的还得填充过去while(i <= mid) {temp[t] = arr[i];t++;i++;}while(j <= right) {temp[t] = arr[j];t++;j++;}t = 0;int tempLeft = left;while(tempLeft <= right) {arr[tempLeft] = temp[t];t++;tempLeft++;}}} 三、时间复杂度赋值运算是基本运算
C ( n ) = { 0 n = 1 2 C ( n / 2 ) + n n > 1 C(n)= begin{cases} 0&n=1 \ 2C(n/2)+n&n>1 \ end{cases} C(n)={02C(n/2)+nn=1n>1
解出来是 Θ ( n l o g 2 n ) Theta (nlog_2n) Θ(nlog2n)解法参考