归并排序解读
网络异常，图片无法展示
|
网络异常，图片无法展示
|
归并过程
就是将两个有序数组合并为一个有序数组。
每次都比较两个数组中第一个元素的大小，然后取出最小的元素。直到两个数组没有元素。
实现的时候需要注意：我们需要复制一份数组，用复制的数组比较，然后将值写入原数组。所以，归并排序过程无法原地完成。
private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) { // 1. 先复制一下数组。arr E[] copyArr = Arrays.copyOfRange(arr, l, r + 1); // 2. 分割两个数组。开始的下标 int i = l, j = mid + 1; // 3. 循环，然后覆盖元素组的值 for(int k = l; k <= r; k++) { if(i > mid) { // 判断左边数组是否越界 arr[k] = copyArr[j - l]; j++; }else if(j > r) { // 判断右边数组是否越界 arr[k] = copyArr[i - l]; i++; }else if(copyArr[i - l].compareTo(copyArr[j - l]) >= 0) { // 下面两个判断都是正常的比较。 arr[k] = copyArr[j - l]; j++; }else { arr[k] = copyArr[i - l]; i++; } } }
算法实现
import java.util.Arrays; /** * @author zhanghao * @create 2022-05-17 21:08 */ public class MergeSort { public static <E extends Comparable<E> > void sort(E[] arr) { sort(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) { if(l >= r) { return; } int mid = l + (r - l) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); merge(arr, l, mid, r); } private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) { // 1. 先复制一下数组。arr E[] copyArr = Arrays.copyOfRange(arr, l, r + 1); // 2. 分割两个数组。开始的下标 int i = l, j = mid + 1; // 3. 循环，然后覆盖元素组的值 for(int k = l; k <= r; k++) { if(i > mid) { // 判断左边数组是否越界 arr[k] = copyArr[j - l]; j++; }else if(j > r) { // 判断右边数组是否越界 arr[k] = copyArr[i - l]; i++; }else if(copyArr[i - l].compareTo(copyArr[j - l]) >= 0) { // 下面两个判断都是正常的比较。 arr[k] = copyArr[j - l]; j++; }else { arr[k] = copyArr[i - l]; i++; } } } }
递归算法的微观解读
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
时间复杂度分析
网络异常，图片无法展示
|
对于有序数组进行归并
他就不需要去merge合并两个有序数组了。
// 将前一个数组最后一个元素大于后一个数组第一个元素时，将不会触发合并操作 public static <E extends Comparable<E> > void sort2(E[] arr) { sort2(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort2(E[] arr, int l, int r) { if(l >= r) { return; } int mid = l + (r - l) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); if(arr[mid].compareTo(arr[mid + 1]) >= 0) { merge(arr, l, mid, r); } }
网络异常，图片无法展示
|
网络异常，图片无法展示
|
使用插入排序算法来优化归并排序
我们知道，当对于小规模的数据来说，因为可能会出现局部有序，所以时间复杂度是o(n)。
插入排序对部分内容进行排序
public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) { for(int i = 0; i < arr.length; i++) { E cur = arr[i]; int j; for(j = i; j - 1 >= 0; j--) { if(cur.compareTo(arr[j - 1]) < 0) { arr[j] = arr[ j - 1]; }else { break; } } // 交换两个位置元素 arr[j] = cur; } }
修改的源码
// 使用插入排序算法优化归并排序 public static <E extends Comparable<E> > void sort3(E[] arr) { sort3(arr, 0, arr.length - 1); } private static <E extends Comparable<E>> void sort3(E[] arr, int l, int r) { // if(l >= r) { // return; // } if(r - l < 15) { InsertSort.sort(arr, l, r); } int mid = l + (r - l) / 2; sort(arr, l, mid); sort(arr, mid + 1, r); if(arr[mid].compareTo(arr[mid + 1]) > 0) { merge(arr, l, mid, r); } }
自底向上归并算法的实现
- 先将两个元素进行合并，合并成两个元素的数组。
- 然后在对合并的两个元素数组进行合并。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
